城市公共自行車高峰期需求不均衡的調度優化研究

胡列格，夏 云，王 佳，唐 量

(1.長沙理工大學交通運輸工程學院，湖南長沙410114;2.長沙大學，湖南 長沙410022)

國內公共自行車系統發展雖然相對較晚，但是通過政府高效推行及社會參與，城市的公共自行車系統得以快速發展。然而，在公共自行車運行過程中，存在明顯的高峰期需求不均衡性，并隨人們出行的潮汐方向表現得尤為嚴重。例如，杭州市自行車出行不均衡現象多出現在城市邊緣地區的大型居住區、工業園區、交通樞紐、商務集中區等功能復合度較低的區域，具體表現為:出行時間集中，短時間內對車輛的需求量大。目前，杭州的調度模式是區域內周轉調度，采用專用公共自行車配送車的方式調度，但系統覆蓋面大、服務網點多，目前的調度方法無法滿足調度需求［1－2］。武漢市辦公型租賃點的公共自行車使用數量最多，可見武漢市公共自行車使用人群以上班族為主［3］，且需求高峰主要集中在上下班時間，存在明顯的潮汐性。株洲自正式啟動運行公共自行車系統以來，為株洲市民帶來不少便利，但市民表示“部分站點無車可取，部分站點車子成堆”的情況時有發生，由此可見，株洲市公共自行車“調度情況很成問題”［4］。國內公共自行車系統在多個城市成功運營，并獲得巨大效益，但是從上述城市公共自行車的使用情況來看，國內公共自行車存在明顯的需求不均衡現象，公共自行車調度不準確、不及時，以及調配方式不合理的問題，嚴重影響公共自行車系統運行效益。為公共自行車系統發揮更好效益，必須加強公共自行車系統車輛調度問題研究。

隨著越來越多的公共自行車系統的投入運營，國內外學者的研究對象越來越傾向于公共自行車系統運行的問題，調度問題在運行中日漸突出，國內外學者們也越來越注重自行車調度方案的研究。Fricker等［5］針對公共自行車系統的租賃行為進行研究，提出對于布局合理且能自我調節的公共自行車系統的各個租賃點的公共自行車數量也有必要進行調配。Contardo等［6］針對公共自行車系統中的動態問題進行研究，建立了相關的可以應用于大型網絡的數學模型，并利用 Dantzig－Wolfe和Benders分解方法較快的獲得調配方案。秦茜［7］建立最大顧客滿意度、最小成本的多目標單調配中心的公共自行車調配問題，首先采用遺傳算法對靜態調度進行求解，再運用禁忌搜索算法對問題進行優化。劉臻［8］建立了租賃點間最短路徑的求解方法和多車場調配模型，再根據各路口簡單鄰接矩陣、各租賃點位置以及Floyd算法對模型進行求解。

本文在國內外研究基礎上，針對高峰期需求不均衡狀態下公共自行車調度優化展開研究，著重考慮時間成本，其中包括完成調度任務的行駛成本和因時間延誤產生的懲罰成本，從而有效解決高峰期“租車難，還車難”問題，實現公共自行車高峰期需求不均衡的車輛調度優化。

1 問題描述

公共自行車調度問題是指在調配頻率、調配量均不確定的情況下，確定運輸車輛進行車輛調配的路徑選擇，以及各個租賃點需要調出和調入自行車的規模，從而達到各個自行車租賃點車輛數在空間上的平衡，滿足市民的出行需求［9］。

公共自行車系統是通租通還的，市民可以在任意租賃點租借，任意租賃點歸還。公共自行車的調度是解決在時間和空間上的需求不均衡引發的問題，在時間上，公共自行車借還需求與城市居民出行規律和生活節奏密切相關;在空間上，公共自行車借還需求與租賃點用地性質及周圍交通發生源出行需求密切相關。在早晚高峰時段，各個租賃點自行車不斷流動，因此會導致一部分租賃點自行車飽和，即無車位停車，同時也會導致另一部分租賃點無車可租，早晚高峰時段以地區上下班工作時間為基礎進行確定。

由于公共自行車出行的需求不均衡性，單純的自然調配不能滿足公共自行車系統的正常運轉，需要及時、合理的人工調度。調度量的確定即為租賃點車輛配置問題，租賃點車輛配置量可以看成是各租賃點的庫存量，將調度運輸看成庫存補給，所以車輛配置問題類似庫存問題，決策者通過提供調度服務來控制租賃點的公共自行車數量，使得各租賃點的車輛配置量始終保持在一定范圍內，從而更好的滿足顧客的租還車需求。

車輛路徑問題［10］(Vehicle Routing Problem，VRP)是城市公共自行車運營中車輛調度問題的重要理論基礎之一，即對一系列已知的租賃點，從車場出發，有序的通過各租賃點，最后返回車場，并在滿足如車輛載運量、租賃點需求量、以及有無時窗限制等約束條件下，滿足如使用車輛數最少、行駛路程最短或者時間最短的總運輸成本最小的目標來確定運輸路線。如圖1所示。

圖1 VRP示意圖Fig.1 VRP schematic diagram

2 模型建立

公共自行車車輛調度模型描述為:在公共自行車系統服務范圍內，有M個車場，各自擁有容量為Q的運輸車輛H輛，負責對N個租賃點進行自行車調入與調出的運輸工作，租賃點i的調度量為di(i=1，2，…，n)，且0 ＜ di≤Q，每1 個租賃點可以由任意1個車場的運輸車輛服務，但只能由1輛運輸車服務1次，每輛運輸車完成任務后可以不返回車場或者沿原路返回車場。已知各個租賃點、車場的位置、每輛運輸車輛的載重量、每輛運輸車輛的最大行駛距離，要求在一定的約束條件下，滿足目標函數，合理的對各租賃點進行調配以及運輸車輛路線做出決策。

設M個車場的編號為 {n+1，n+2，…，n+m}，待服務的N 個租賃點編號為 {1，2，…，n}，為構造數學模型，定義以下變量的取值:

根據各租賃點需求總量估計所需車輛數的下限值:

［*］表示不大于括號內數值的最大整數。

符號說明:K為所需運輸車輛數;Q為運輸車輛的最大載運量;L為運輸車輛一次調度的最大行駛距離;N為待服務的租賃點集合，N={1，2，…，n};M 為車場的集合，M={n+1，n+2，…，n+m};i，j為待服務的租賃點集合和車場的集合(N∪M);dij為租賃點i到租賃點j的直接距離，假設dij=dji;di為租賃點i的需求量，di≤Q;wijk為運輸車輛k從租賃點i到租賃點j車上的載運量;ai為租賃點i的最早服務時間;bi為租賃點i的最晚服務時間;ti為運輸車輛到達租賃點i的時間;tj為運輸車輛到達租賃點j的時間;tij為運輸車輛從租賃點i到達租賃點j的時間;tui為運輸車輛在租賃點i的裝卸時間;si為租賃點i的服務時間;P1為早于ai到達租賃點i并開始服務的懲罰系數;P2為晚于bi到達租賃點i并開始服務的懲罰系數;C1為運輸車輛單位里程成本費用;C2為等待時間的成本費用。

2.1 目標函數

根據以上分析，調配模型的目標函數由式(1)和(2)構成。

式(1)為第1優化目標，表示調配車輛數最小化;式(2)為第2優化目標，表示成本最小化，右邊第1項是運輸車輛行駛成本，第2項是運輸車輛早于時間窗開始時刻到達租賃點的懲罰成本，第3項是運輸車輛晚于時間窗結束時刻到達租賃點的懲罰成本。

所使用的運輸車輛數最小化是第1層優化目標，具有較高的優先權。因此，所用運輸車輛數較少的解總是比所用運輸車輛數較多的解好，盡管由此可能引起運輸車輛的行駛成本增加。為了充分對解空間進行搜索，算法接受導致不可行解的變換。當違反了運輸車輛載運能力限制和最大行駛距離限制時，其不可行性的程度可以通過引入1個罰值而將該約束條件包含到目標函數中去進行度量，使得優化結果在所使用的運輸車輛數和行駛成本之間取得適當平衡［11］。即:

式中:K為該解中所使用的車輛數(線路數);Z21(k)為車輛k的行駛成本;EQ(k)為車輛k上超出車輛載運量的部分;EL(k)為車輛k上超出車輛行駛距離的部分;p為懲罰系數。

2.2 約束條件

為保證該調度模型符合實際運營情況，特作以下約束:

式(4)指運輸車輛在運輸過程中的載運量(公共自行車數量)不超過其最大載運能力;式(5)指路線長度不超過運輸車輛1次運輸的最大行駛距離;式(6)指運輸車輛均從車場出發;式(7)指每一個租賃點僅由一輛運輸車輛完成調度;式(8)指運輸車輛k完成調度任務后返回任意車場;式(9)指一租賃點的調度量不大于運輸車輛的最大載運能力;式(10)指運輸車輛經過租賃點時，其調入和調出自行車的總數加上運輸車輛上原有自行車數不小于0，且不大于運輸車輛的最大載運能力;式(11)指運輸車輛行駛過程中，在ti+tui+tij前不能達到租賃點j;式(12)指運輸車輛在某租賃點的等待時間si取決于運輸車輛到達該租賃點的時刻與該租賃點時間窗開始的時刻關系;式(13)指運輸車輛達到某租賃點的時刻必須小于(早于)該租賃點的時間窗結束時刻。

3 算法分析與設計

3.1 禁忌搜索算法概述

禁忌搜索算法 (Tabu search，簡稱TS)的思想最早是由Glover等在1986年提出，它是解決組合優化問題的另一種優化方法，是局部搜索算法的擴展，是一種全局逐步尋優算法［12－13］。TS算法的特點是采用禁忌技術，即用一個禁忌表記錄下已經到達過的局部最優點，在下一次搜索中，利用禁忌表中的信息不再或者有選擇地搜索這些點，以此來跳出局部最優點。在TS算法中，首先按照隨機方法產生一個初始解作為當前解，然后在當前解的鄰域中搜索若干個解，取其中的最好解作為新的當前解。為避免陷入局部最優解，這種優化方法允許一定的下山操作(使解的質量變差)。另外，為了避免對已搜索過的局部最優解的重復，TS算法使用禁忌表記錄已搜索的局部最優解的歷史信息，這可在一定程度上使搜索過程避開局部極值點，從而開辟新的搜索區域。

3.2 算法步驟

用TS算法求解組合優化問題時，其實現步驟如下(以目標函數求最小為例)。

第1步:選定一個初始解xnow;令禁忌表H=Φ。

第2步:若滿足終止準則，轉第4步;否則，在xnow的鄰域N(xnow)中選出滿足禁忌要求的候選集Can_N(xnow)，轉第3步。

第3步:在Can_N(xnow)中選1個評價值最好的解xbest。令xnow=xbest，更新禁忌表H=Φ，轉第2步。

第4步:輸出計算結果，停止。

TS算法基本流程如圖2所示。

圖2 TS算法流程圖Fig.2 TS algorithm flow chart

3.3 算法設計

本文分析的是公共自行車高峰期需求不均衡的問題，并且是對公共自行車的多車場車輛調度優化問題進行研究。本文對多車場的處理方法是:隨機從車場集合M中選取1個車場n+m，1輛運輸車輛從該選中的車場出發，然后根據各個租賃點的需求再去完成運輸任務，直到運輸車輛載到足夠滿為止，并且在完成最后1個租賃點的運輸任務以后，就近返回某個車場的1條巡回路線。如果租賃點還沒服務完，又隨機從M中選取1個車場，重復上述操作，如此循環，直到完成所有租賃點的運輸任務。

1)初始解

禁忌搜索算法是以1個初始解開始其局部搜索的過程，且該算法的計算效果與初始解的質量有很大關系，本文采用隨機方式產生初始解。

2)鄰域結構

鄰域結構是求解組合優化問題的一個重要組成部分，是影響解的質量和搜索速度的重要因素之一，它將指導如何由1個解來產生1個(組)新的解。鄰域構造方法的選擇主要依賴于解的表示。采用租賃點直接排列的解的表示方法時，可以采用換位法、逆轉法、插入法進行鄰域選點，本文采用換位法，即隨機選擇解中的若干個元素，并交換其位置的鄰域選點方法。

3)解的表示

采用租賃點直接排列的表示方法，用自然數集合M表示車場，自然數集合N表示租賃點，然后用租賃點和車場編號所組成的自然數序列表示車輛行駛路徑。

首先以隨機方式生成租賃點的排列，然后將租賃點分配給適當的運輸車輛，這一過程中，每次將租賃點排列中未分配的租賃點的最左側的租賃點在滿足載運量約束的條件下分配給當前車輛，如果不滿足約束條件則新開1輛運輸車，將該租賃點的運輸任務安排給新開的運輸車輛，新開的運輸車輛為當前車輛，直到所有的租賃點的運輸任務完成。

4)解的評價

本文采用租賃點與車場共同排列的解的表示方法對解進行評價，即:對某個解所對應的配送路徑方案，要對各條配送路徑逐一進行判斷，看其是否滿足約束條件，若不滿足，則將該條配送路徑定為不可行路徑，最后還要計算出該解對應的配送路徑方案的目標函數值。對于某個解，設其對應的配送路徑方案中的不可行路徑數為X(X=0表示該解為一個可行解)，該配送路徑方案的目標函數值為Z，并設對每條不可行路徑的懲罰權重為PW(該權重可根據目標函數的取值范圍取一個相對較大的正數)，則該解的評價值E可表示為:E=Z+X×PW，E值越小，表示解的質量越高。

5)禁忌表

禁忌表是禁忌搜索算法中的一個重要特征，是禁忌搜索算法的核心，是為防止搜索出現循環、避免陷入局部最優，在禁忌搜索算法中設置了動態更新的禁忌表，用來記錄禁忌對象和禁忌長度。

①禁忌對象

禁忌對象是指禁忌表中被禁的那些引起解狀態變化的元素，由于解狀態的變化可以分為解的簡單變化、解向量分量的變化和目標值變化3種情取，n為鄰域中鄰居的總個數，也就是問題的規模。這種方法容易在算法中實現。

(b)l∈［lmin，lmax］。此時，禁忌長度 l是依據被禁對象的目標函數值和鄰域的結構發生變化的數，lmin和lmax也可以是動態選擇，即限定變化區間，n為鄰域中鄰居的總個況，則在確定禁忌對象時也有3種方式:第1，解本身或者解的變化;第2，解的分量或者解的分量變化;第3，解的目標值變化。一般來說，第1種方式比其他2種方式禁忌的受禁范圍要小，因此可能造成計算時間增加，但提供了較大的搜索范圍。又由于禁忌范圍過大，將有可能陷入局部最優解;禁忌范圍過小，則容易陷入循環。所以，在實際應用中，要根據問題的規模，禁忌表的長度等具體情況確定禁忌對象。

②禁忌長度

禁忌長度是指被禁忌對象不允許被選取的迭代步數，也是禁忌對象的受禁時間，一般是給被禁忌對象x一個數l(稱為禁忌長度)，要求對象x在l步迭代內被禁，在禁忌表中采用Tabu(x)=l記憶，每迭代一步，該項指標做運算Tabu(x)=l－1，直到Tabu(x)=0時解禁。顯然，禁忌表的長度越小，計算的時間越短、存儲的空間越少，但是禁忌長度過短，則容易造成搜索的循環。所以，禁忌長度的設定也要依據問題的規模、特點，以及鄰域的大小來確定。關于禁忌長度l的選取，有以下方法:

(a)l可以取一些與問題無關的常數，也可以數，也就是問題的規模。

6)候選集合的確定

候選集合是由鄰域中的鄰居組成，也就是迭代中候選集合。常規的確定方法是從鄰域中選擇若干個目標函數值或最佳評價值的鄰居，但是這種方法的計算量太大，所以選擇在領域中的一部分鄰居中選擇若干目標值或評價值最佳的解，當然也可采用隨機選取的方法實現候選集和的確定。

7)終止準則

由于禁忌搜索算法與其他現代優化算法(如遺傳算法、模擬退火算法、蟻群算法等)一樣，并不能保證找到問題的全局最優解，而且也沒有判斷是否找到全局最優解，所以，需要另外給出終止條件來停止搜索。

①給定一定迭代步數。當迭代步數達到給定的最大迭代次數r時停止運算。

②頻率控制準則。在一定的迭代步數內，某個對象的禁忌頻率達到一個給定的閾值時終止運算。

③目標值變化控制準則。在算法迭代一定步數時目標值沒有變化，則終止運算［14－15］。

本文是采用第①個或者第③個終止準則對算法進行終止。

4 算例分析

4.1 算例構造

公共自行車系統的自行車車輛調度需要根據租賃點的鎖車樁的數量、自行車的數量和需求量，從而合理的確定需求高峰期內各個租賃點調入和調出的數量，最終確定調度路徑。本節通過構造一個簡單的算例，來說明上述車輛調度優化模型和禁忌搜法算法設計在公共自行車高峰期需求不均衡的調度問題中的應用，為便于計算，算例中的數據均為假定數據。

假設某區域擁有24個自行車租賃點，3個車場，各租賃點和車場的坐標如表1所示，并給出各個租賃點鎖車樁數量以及自行車使用者時間窗。假定本區域上班早高峰是7∶00－8∶00，本文以租賃早高峰時段的1 h(6∶30－7∶30)進行研究。

算例中只將有調度需求的租賃點納入考慮范圍，并對模型中相關參數做出估算和假設，確定以下數據:

運輸車輛從租賃點i到達租賃點j的時間tij=運輸車輛在租賃點i的裝卸時間(每輛自行車的裝卸時間為15 s);運輸車輛1 km的成本費用C1=0.6(元/km);個人每min的工資水平C2=0.3(元 /min);運輸車輛的最大載運量Q=30(輛)。

表1 某區自行車租賃點的基本情況Table 1 Basic situation of the bicycle rental points one district

4.2 算例求解

根據上述已知條件，建立該區域公共自行車的調度模型，并用禁忌搜索算法進行求解。本文的禁忌搜索算法采用C語言開發，程序的模塊結構如圖3所示。

圖3 車輛優化調度問題的禁忌搜索算法模塊結構Fig.3 Tabu search algorithm module structure chart of vehicle optimization scheduling problem

通過禁忌搜索的求解算法，對上述算例進行求解，其調度方案如表2所示，行車路線圖如圖4所示。

圖4 調配路徑圖Fig.4 Scheduling path graph

表2 某區公共自行車調配路徑方案表Table 2 Public bicycle allocate path plan table

5 結論

1)為解決公共自行車高峰期需求不均衡的車輛調度優化問題，建立了調配車輛數最小和調配總成本最小的雙目標規劃模型，采用禁忌搜索算法進行模型求解，通過算例的構造求解表明，設計的禁忌搜索算法能夠在調度優化問題的巨大搜索空間中可靠的找到最優解，可以實現公共自行車調度優化;

2)由于算例中數據是為方便計算給予的假定數據，這可能與實際情況有差距，高峰時段租賃點的調配量應根據租賃點歷史借還量進行分析;

3)還有一點需要注意的是公共自行車在實際調度過程中，運輸車輛的行駛時間不僅與租賃點的距離有關，還應考慮當時的道路交通條件等的動態影響，將作為今后進一步研究的重點。

［1］石曉風.基于杭州經驗的集約型城市公共自行車系統規劃發展思路［D］.杭州:浙江大學，2011.

SHI Xiaofeng.The development mentality of public bicycle system in intensive city based on the experience in Hangzhou［D］.Hangzhou:Zhejiang University，2011.

［2］石曉峰.杭州公共自行車系統規劃建設與使用調查研究［J］.城市發展研究，2011，18(10):105 －114.

SHI Xiaofeng.Hangzhou public bicycle system planning construction and use of research［J］.Urban Studies，2011，18(10):105 －114.

［3］戴菲.全國第一個設立免費公共自行車系統的城市——武漢市公共自行車系統研究［J］.建設科技，2010，9(17):42 －46.

DAI Fei.The first city in the country set up a free public bicycle system—Wuhan city’s public bike system research［J］.Construction Science and Technology，2010，9(17):42－46.

［4］宋騫.公共自行車的株洲模式——低碳時代的城市命題［J］.中華建設，2013，10(5):14 －16.

SONG Qian.Public bicycle model of Zhuzhou—Low carbon city proposition of the times［J］.Chinese Construction，2013，10(5):14 －16.

［5］Flicker，Gas.Incentives and regulations in bike － sharing systems with stations of finite capacity［J］.arXiv:1201，1178vl，2012.

［6］Contardo C，Morency C，Rousseau L M.Balancing a dynamic public bike－sharing system［R］.Technical Report 09，CIRRELT，2012.

［7］秦茜.公共自行車租賃系統調配問題研究［D］.北京:北京交通大學，2013.

QIN Qian.The research on repositioning in a bike－sharing system［D］.Beijing:Beijing Jiaotong University，2013.

［8］劉臻.城市公共自行車運營中的多車場車輛調配優化研究［D］.北京:北京交通大學，2013.

LIU Zhen.Study on multiple－depot scheduling optimization in urban public bicycle operation［D］.Beijing:Beijing Jiaotong University，2013.

［9］張建國.城市公共自行車車輛調配問題研究［D］.成都:西南交通大學，2013.

ZHANG Jianguo.Research on urban public bicycle vehicle allocation problem［D］.Chengdu:Southwest Jiaotong University，2013.

［10］段鳳華.帶軟時間窗約束的開放式車輛路徑問題及其應用［D］.長沙:中南大學，2009.

DUAN Fenghua.On open vehicle routing problem with soft time windows and its applications［D］.Changsha:Central South University，2009.

［11］符卓.開放式車輛路徑問題及其應用研究［D］.長沙:中南大學，2003.

FU Zhuo.The open vehicle routing problems and their aPPlications［D］.Changsha:Central South University，2009.

［12］魏曉明.基于禁忌搜索算法求解帶時間窗的定位路線研究［D］.西安:長安大學，2009.

WEI Xiaoming.Study on the location routing problem with time windows based on tabu search algorithm［D］.Xi’an:Chang’an University，2009.

［13］符卓.帶裝載能力約束的開放式車輛路徑問題及其禁忌搜索算法研究［J］.系統工程理論與實踐，2004，24(3):123－125.

FU Zhuo.The capacitated open vehicle routing problem and its tabu search algorithm［J］.Theory and Practice of Systems Engineering，2004，24(3):123 －125.

［14］郎茂祥，胡思繼.車輛路徑問題的禁忌搜索算法研究［J］.管理工程學報，2004，18(1):81 －84.

LANG Maoxiang，HU Siji.Study on the tabu search algorthm for vehicle routing problem［J］.Journal of Industrial Engineering and Engineering Management，2004，18(1):81－84.

［15］郎茂祥.配送車輛優化調度模型與算法［M］.北京:電子工業出版社，2009.

LANG Maoxiang.Study on the model and tabu search algorithm for vehicle routing problem［M］.Beijing:Electronic Industry Press，2009.