基于蟻群算法的公共自行車系統(tǒng)調(diào)度算法研究

，2，3，2，3

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

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

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

1 公共自行車調(diào)配路徑優(yōu)化模型

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

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

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

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

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

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

為便于計算，將調(diào)配區(qū)域劃分為m個子區(qū)域，每個子區(qū)域由1輛調(diào)度車調(diào)配，求解全局最優(yōu)問題就轉(zhuǎn)化為求解局部最優(yōu)問題。

1.1 不帶時間窗的公共自行車調(diào)配路徑優(yōu)化模型

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

考慮該問題的約束條件和優(yōu)化目標，車輛調(diào)配路徑的數(shù)學模型如下：

目標函數(shù)為

(1)

約束函數(shù)為

0≤dj+rj≤Q

(2)

(3)

(4)

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

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

1.2 基于滾動時域的公共自行車調(diào)配路徑優(yōu)化模型

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

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

圖1 軟時間窗

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

(5)

因此，該問題的數(shù)學模型如下：

目標函數(shù)為

(6)

其中

(7)

約束條件為：

0≤Qi≤Q

(8)

(9)

(10)

(11)

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

2 算法設(shè)計

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

運用蟻群算法求解模型的關(guān)鍵步驟設(shè)計如下。

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

圖2 公共自行車車輛調(diào)配路徑優(yōu)化蟻群算法構(gòu)造圖

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

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

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

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

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

(12)

(13)

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

2中ηij=1/tij；0≤?≤1表示τij、ηij在構(gòu)造解時的作用程度。當?shù)螖?shù)達到上限時，終止算法，輸出結(jié)果。算法流程如圖3所示。

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

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

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

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

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

step7：判斷是否滿足迭代條件。若是，則輸出最優(yōu)結(jié)果；若否，則轉(zhuǎn)到step2。

圖3 公共自行車車輛調(diào)配路徑優(yōu)化模型算法流程圖

3 算例分析

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

表1 各租賃點之間距離 m

表1(續(xù)) m

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

表2 各租賃點之間調(diào)度車的行程時間 min

1)平峰。

每個租賃點需要調(diào)配的自行車數(shù)量見表3。

表3 早高峰前每個租賃點需要調(diào)配的自行車數(shù)量

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

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

表4 早高峰前預調(diào)配路徑方案比較

圖4 早高峰前預調(diào)配路徑MATLAB軟件運算結(jié)果

2)早高峰。

假設(shè)根據(jù)早高峰期租賃點歷史借還需求規(guī)律以及信息管理系統(tǒng)采集的數(shù)據(jù)，得出早高峰期每個租賃點的需要調(diào)配量及調(diào)配時間窗，如表5所示。

表5 早高峰每個租賃點需要調(diào)配的自行車數(shù)量及調(diào)配時間窗

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

圖5 早高峰時調(diào)配路徑Matlab軟件運算結(jié)果

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

4 結(jié)束語

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

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

[1]王志高，孔喆，謝建華，等. 歐洲第三代公共自行車系統(tǒng)案例及啟示[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]耿雪，田凱，張宇，等. 巴黎公共自行車租賃點規(guī)劃設(shè)計[J]. 城市交通，2009，7(4)：21-29.

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

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

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

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

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

[11]龔迪嘉. 公共自行車交通系統(tǒng)在上海和長沙的應(yīng)用機制研究[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]董紅召，趙敬洋，郭海鋒，等. 公共慢行系統(tǒng)的動態(tài)調(diào)度建模與滾動時域調(diào)度算法研究[J]. 公路工程，2009，34(6)：68-75.

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

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

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

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