基于蟻群算法的公共自行車系統調度算法研究

，2，3，2，3

(1.西南交通大學交通運輸與物流學院,四川 成都 610031；2.綜合運輸四川省重點實驗室，四川 成都 610031；3. 交通運輸智能化國家地方聯合工程實驗室，四川 成都610031)

公共自行車系統是一種創新型自行車交通模式[1]。其目的是通過將自行車與其他幾種交通方式結合，使之成為城市公共交通的一部分，成為居民交通出行的重要選擇。公共自行車系統的實施不僅可以降低出行成本、提高道路資源利用效率、緩解交通擁堵，還能節能減排，提高城市的空氣質量。

圍繞公共自行車，學者們進行了大量的研究[2-14]。這些研究成果為公共自行車系統的實施與發展提供了有力的支撐，但是它們大多是對系統運營和租賃點位置確定的研究，對于不同租賃點之間公共自行車車輛調配路徑選擇沒有進行深入闡述和量化分析。文獻[15]雖然運用蟻群算法得到公共自行車最優調度回路，但是沒有考慮1d內不同時段公共自行車的借還需求情況。為得到符合實際需求的調配路徑方案，本文在考慮不同時段車輛借還特點條件下建立路徑優化模型。

1 公共自行車調配路徑優化模型

確定車輛調配的路徑，需分別考慮平峰時期租賃點自行車數量均衡和高峰時期租賃點租賃需求被拒絕率低的調配目標。在平峰時的車輛調配或早晚高峰前的預調配時，由于租賃點借還量較小，可以不考慮租賃點的自行車數量隨時間變化而變化，因此不考慮時間約束。在高峰期調配過程中，租賃點借還量大，借還速率快，租賃點的自行車數量隨時間變化而變化，租賃點在還未被調配之前可能就出現無車可借或者無停車樁可還車的情況，這時需求者借還車要求將會被拒絕，因此高峰期車輛調配路徑優化模型需要考慮時間因素。為此，建立以上2種模型，并作以下假設。

1)用有向圖G=(A,E)表示公共自行車車輛調配網絡。A={0,1,2,…,n}表示租賃點的集合，0點表示調度中心；E={(i,j)|i,j∈A,i≠j}表示相連租賃點的邊集；V={0,1,2,…,m}表示調度車的集合。

2)調度車均從調度中心出發，并且最終回到調度中心，出發時調度車上公共自行車數量為0(實際中若調度中心儲備有公共自行車，可以將調度中心看作由虛擬的一個調度中心與幾個租賃點組成，調度中心與這幾個租賃點間距離及費用均為0)。

3)lij表示租賃點i到租賃點j之間的距離。如果2個租賃點之間無法直接到達，其值為無窮。由于城市道路通行條件限制租賃點i到租賃點j的距離lij不等于租賃點j到租賃點i的距離lji，即lij≠lji。

4)xij為調度車路線安排。當調度車經由租賃點i到租賃點j時，xij取1；否則，xij取0。

5)租賃點i的車輛調配需求為di(i=1，2，…，n)，且diQ，可將租賃點i視作由幾個租賃點組成，這幾個租賃點間距離及費用均為0)。d0=0表示調配中心的需求。

為便于計算，將調配區域劃分為m個子區域，每個子區域由1輛調度車調配，求解全局最優問題就轉化為求解局部最優問題。

1.1 不帶時間窗的公共自行車調配路徑優化模型

由于平峰時車輛調配不考慮時間約束，因此以調配成本最小化為目標，建立不帶時間窗的公共自行車車輛調配路徑優化模型，對平峰時車輛調配或早晚高峰前預調配的調配路徑進行優化。

考慮該問題的約束條件和優化目標，車輛調配路徑的數學模型如下：

目標函數為

(1)

約束函數為

0≤dj+rj≤Q

(2)

(3)

(4)

式中：Z為車輛調配的費用；co、ct、cb、cv分別為調度車每千米損耗費用、每千米時間費用、每千米油耗費用、調度車的固定費用；rj(1

式(2)保證調度車不超載，并且在服務下一個租賃點時車上有足夠的自行車對其進行服務；式(3)保證從調度中心出發的調度車回到調度中心；式(4)保證調度車只對租賃點服務1次。

1.2 基于滾動時域的公共自行車調配路徑優化模型

與平峰時段借還需求不同，高峰時段需求量大， 此時將以滿足需求者要求為目標，車輛調度問題的優化目標中費用問題就不是考慮的重點。由于需求者在高峰時借還車要求可能會被拒絕，因此，為使租賃點拒絕需求者借還要求次數最低，設定一個調配時間窗。在這時間窗內租賃點不會出現無車可借或者無停車樁可還車的情況，調度車對其進行車輛調配就不會有需求者借還要求被拒絕的情況。為使需求者借還的要求拒絕率最低，調度車盡可能地在租賃點所要求的時間窗內對其進行車輛調配。這個時間窗是租賃點最佳調配時間。實際車輛調配過程中，租賃點所要求的最佳時間窗可能無法滿足，因此將最佳調配時間窗擴大為可接受調配時間窗。若調度車在此時間范圍內對其進行調配，只有少數需求者借還要求被拒絕，租賃點對此可以接受。本文通過引入租賃點滿意度對需求者借還要求被拒絕率進行定量表達。租賃點滿意度越大，需求者借還要求被拒絕率越低，因此高峰時公共自行車車輛調配路徑優化模型是以租賃點滿意度最大為目標建立的。

滿意度函數是用來衡量租賃點對調度車調配工作的滿意程度。如圖1所示，(Ci,Di)代表租賃點最佳調配時間范圍，(Ai,Bi)代表租賃點可接受的調配時間范圍。

圖1 軟時間窗

當調度車到達租賃點i的時間ti∈(Ci,Di)時，租賃點i對此次的調配服務滿意度fi(ti)最大，且fi(ti)=1；當達到時間ti∈(Ai,Ci)或者(Di,Bi)時，租賃點i對此次的調配服務滿意度fi(ti)介于0與1之間；當到達時間tiBi時，租賃點i對此次的調配服務滿意度fi(ti)最小，且fi(ti)=0。租賃點滿意度函數可以表達為

(5)

因此，該問題的數學模型如下：

目標函數為

(6)

其中

(7)

約束條件為：

0≤Qi≤Q

(8)

(9)

(10)

(11)

式中：Z為最大滿意率；T為時間軸；N(t)為t時刻，所有未被調配租賃點、新增需要服務的點和停車場的集合；M(t)為t時刻，所有調配完成的租賃點的集合；tiv為調度車v到達租賃點i的時間；Qi為調度車在租賃點i服務后車上裝載的自行車的數量；v0為調度車的行駛速度，高峰時不同道路服務水平存在差異(道路擁堵情況不同)，因此每段道路調度車的行駛速度不一致，行駛速度為2個阻力點的行程速度，在實際情況中，調度車每條路段行程速度可以根據歷史行程速度回歸分析確定。式(8)保證調度車都不超載，并且在服務下一個租賃點時車上有足夠的自行車對其服務；式(9)保證任意從調度中心出發的車都要回到調度中心；式(10)保證對任意由調度車調配的租賃點j必定有另一個(而且只有一個)租賃點(包括調配中心)i；式(11)保證對任意由調度車調配的租賃點i必定有另一個(而且只有一個)租賃點(包括調配中心)j。

2 算法設計

公共自行車車輛調配路徑優化問題屬于圖論問題，也是組合優化問題，無法準確的求解，只能采用近似算法求得近似解。一般用于解決此類問題的方法有蟻群算法、禁忌搜索算法和遺傳優化算法等[16]。雖然這幾種現代優化算法均可用于求解；但由于城市公共自行車租賃點數量規模大，采用禁忌搜索方法求解時，計算機運算時間將較長，因此蟻群算法與遺傳算法較為合適求解調配路徑優化問題。由于本問題屬于帶容量約束的旅行商問題，而蟻群算法在旅行商問題中的應用較為廣泛，并且不帶時間窗的公共自行車車輛調配路徑優化模型和基于滾動時域的公共自行車車輛調配路徑優化模型均可采用蟻群算法求全局近似最優解；因此，本文采用蟻群算法作為求解算法。

運用蟻群算法求解模型的關鍵步驟設計如下。

1) 解構造圖。蟻群算法的關鍵問題之一是如何將要解決的問題映射為解構造圖，通過人工螞蟻在該圖從起點上行走到終點的路線從而得到問題可行解。

圖2 公共自行車車輛調配路徑優化蟻群算法構造圖

圖2是公共自行車車輛調配路徑優化蟻群算法構造圖。其中：實數1、2、3表示調度車所行使的區間步驟；Di表示租賃點i；dij表示租賃點Di與租賃點Dj之間的距離；虛線框中的租賃點表示在確定前一個租賃點后，調度車在現有可調出公共自行車能力及現有可調入公共自行車能力條件下，滿足各項約束后可選擇的租賃點去向集合；黑實線表示調度車行走路徑。

3)信息素的表示、初始化及更新的原則。信息素τij是指調度車去往租賃點Di的期望度。

(1)信息素的初始化。為在迭代的初期擴大螞蟻在解空間的搜索范圍，解構造圖中所有的實邊上的信息素均被初始化為τmax，即τij(0)=τmax。圖中所有的虛邊為輔助邊，不起決策作用，因此虛邊上沒有信息素。

(2)信息素更新原則。信息素的更新原則為：

τij(t+1)=(1-ρ)τij(t)+Δτij

(12)

(13)

式中：ηij是啟發式信息，是指調度車自租賃點Di至租賃點Dj的期望度，在模型1中ηij=1/dij，在模型

2中ηij=1/tij；0≤?≤1表示τij、ηij在構造解時的作用程度。當迭代次數達到上限時，終止算法，輸出結果。算法流程如圖3所示。

step1：初始化參數，如輸入租賃點距離dij、租賃點間行程時間、租賃點自行車數qi等基礎數據，初始化螞蟻數目K、迭代次數M、參數Q、?、η、τ、ρ等蟻群算法參數。

step2：在0點放置m只螞蟻。

step4：判斷是否走完所有租賃點。若是，則轉到step5；若否，則此轉到step3。

step5：判斷m只螞蟻是否都走完所有租賃點。若是，則轉到step6；若否，則轉到step3。

step6：根據信息素更新原則更新信息素矩陣，即每條邊上信息素的量。

step7：判斷是否滿足迭代條件。若是，則輸出最優結果；若否，則轉到step2。

圖3 公共自行車車輛調配路徑優化模型算法流程圖

3 算例分析

以成都市金牛區的公共自行車租賃點為對象進行算例分析。金牛區15個自行車租賃點之間行駛的最短距離如表1所示。

表1 各租賃點之間距離 m

表1(續) m

假設考慮道路交通條件等影響因素，調度車的行程速度為20 km/h，則每個租賃點之間行程時間如表2所示。

表2 各租賃點之間調度車的行程時間 min

1)平峰。

每個租賃點需要調配的自行車數量見表3。

表3 早高峰前每個租賃點需要調配的自行車數量

根據確定的租賃點調配量，首先采用貪婪算法，求得早高峰前車輛調配的初始可行路徑為0-2-1-8-10-6-9-5-3-4-7-13-14-15-11-12-0，初始行駛路程為20.4 km。假設調度車每千米損耗費用co為0.26元，每千米時間費用ct為0.1元，每千米油耗費用cb為調度車每千米消耗燃油費用，一般按照汽車每百千米油耗計算，如調度車油耗為8.5 L/100 km，0號柴油價格為7.4元/km，則

為cb為0.629元/km，調度車的固定費用cv為49.1元[17]。此時車輛調配費用為69.3元。運用模型1對調配路徑進行優化，采用蟻群優化算法求解，利用MATLAB軟件編程運算，如圖4所示。優化后行駛路徑為0-13-10-7-5-6-1-2-4-8-9-11-12-3-14-15-0，優化后行駛路程為10.5 km，車輛調配費用為59.5元，優化后行駛路程比初始行駛路程減少了48.5%，費用減少14.1%，如表4、圖4所示。

表4 早高峰前預調配路徑方案比較

圖4 早高峰前預調配路徑MATLAB軟件運算結果

2)早高峰。

假設根據早高峰期租賃點歷史借還需求規律以及信息管理系統采集的數據，得出早高峰期每個租賃點的需要調配量及調配時間窗，如表5所示。

表5 早高峰每個租賃點需要調配的自行車數量及調配時間窗

假設調度車對每個租賃點自行車調配時間均為2 min，則根據早高峰時租賃點需要調配的量，首先采用貪婪算法，求得早高峰期初始可行路徑為0-7-8-9-10-5-4-3-2-6-11-13-15-14-1-0，租賃點滿意度為5.03。運用模型2對調配路徑進行優化，采用蟻群優化算法求解，利用MATLAB軟件編程運算，如圖5所示。優化后行駛路徑為0-8-9-5-2-3-11-12-13-15-10-14-6-7-4-1-0，租賃點滿意度為8.165，優化后滿意度比初始滿意度提高了62.3%。

圖5 早高峰時調配路徑Matlab軟件運算結果

將不帶時間窗的調配路徑優化模型與基于滾動時域的調配路徑優化模型進行比較發現：采用滾動時域的優化模型得到的調配總路徑為14.78 km，比采用不帶時間窗模型的最優路徑增加28.9%；但是將不帶時間窗模型的最優路徑運用于基于滾動時域的優化模型，其滿意度為5.382，比基于滾動時域模型的最優滿意度減少34.1%。可見，為滿足不同時刻的最大需求，應采用不同的模型，才能使利益最大化。同時考慮使調配費用最小與滿意度最高，建立公共自行車調配路徑優化模型，使該模型均適用于平峰和高峰，是本文下一步研究的問題。

4 結束語

本文從高峰時段和平峰時段的調配需求出發，分別建立不同目標的優化模型，并運用蟻群算法對其求解。通過算例分析表明，該模型具有良好的適用性。在實際公共自行車調配中，調度車的行程時間不僅與租賃點之間的距離有關，還受道路交通條件影響，本算例采用的是較為理想狀態；因此在實際調配中應根據實際路況調整調配路徑。

公共自行車產生調配問題的一個原因就是租賃點規劃布設不合理。目前缺乏科學系統的理論指導租賃點的規劃與建設，導致租賃點建成后借還量與規劃時預測量存在較大差距，使得后期調配工作任務繁重；因此，把公共自行車租賃點規劃布設與路徑調配問題統一研究仍需進一步研究討論。

[1]王志高，孔喆，謝建華，等. 歐洲第三代公共自行車系統案例及啟示[J]. 城市交通，2009，7(4)：7-12.

[2]Demaio Paul. Smart Bikes:Public Transportation for the 21 Century [J]. Transportation Quarterly，2003, 57(1):9-11.

[3]Pinand Antoine, Santos Canals Mare. Copenhagen: How Bicycles can Become an Efficient Means of Public Transportation[EB/OL].[2013-08-10].http://hdl.hand le.net/1800/2122.

[4]Andreas Kaltenbrunner, Rodrigo Meza, Jens Grivolla, et al. Urban Bicycles and Mobility Patterns: Exploring and Predicting Trends in a Bicycle-based Public Transport System[J]. Pervasive and Mobile Computing，2010(4):455-466.

[5]耿雪，田凱，張宇，等. 巴黎公共自行車租賃點規劃設計[J]. 城市交通，2009，7(4)：21-29.

[6]韓惠敏，張宇，喬偉. 里昂公共自行車系統[J]. 城市交通，2009，7(4)：13-20.

[7]何流，陳大偉，李旭宏，等. 城市公共自行車租賃點布局優化模型[J]. 武漢理工大學學報：交通科學與工程版，2012，35(1)：129-134.

[8]李婷婷. 城市公共自行車租賃點選址規劃研究[D]. 北京：北京交通大學, 2010.

[9]何博. 城市公共自行車系統的應用研究[D]. 成都：西南交通大學， 2012.

[10]龔迪嘉，朱忠東. 城市公共自行車交通系統實施機制[J]. 城市交通，2008，6(6)：27-32.

[11]龔迪嘉. 公共自行車交通系統在上海和長沙的應用機制研究[D]. 長沙：湖南大學，2009.

[12]Parkin J, Wardman M, Page M. Estimation of the Determinants of Bicycle Mode Share for the Journey to Work Using Census Data[J]. Transportation，2008, 35(1):93-109.

[13]董紅召，趙敬洋，郭海鋒，等. 公共慢行系統的動態調度建模與滾動時域調度算法研究[J]. 公路工程，2009，34(6)：68-75.

[14]劉登濤，方文道，章堅民，等. 公共自行車交通系統調度算法[J]. 計算機系統應用，2011，20(9)：112-116.

[15]柳祖鵬，李克平，朱曉宏. 基于蟻群算法的公共自行車站間調度優化[J]. 交通信息與安全，2012，30(4)：71-74.

[16]陳文蘭，戴樹貴.旅行商問題算法研究綜述[J]. 滁州學院學報， 2006,8(3)：1-6.

[17]張建國. 城市公共自行車車輛調配問題研究[D]. 成都：西南交通大學，2013.