基于蟻群算法的城市公共自行車調(diào)度研究

張輝++鄭彭軍

摘要：由于城市公共自行車存在供需時空分布的不均衡性，因而進行公共自行車的調(diào)度是十分必要的。通過分析現(xiàn)階段我國城市公共自行車調(diào)度方式特性，為充分滿足租賃者的需求，提出了一種帶模糊時間窗的城市公共自行車調(diào)度路徑優(yōu)化模型。以租賃點滿意度最大化為目標函數(shù)，同時將基本蟻群算法進行改進后應用于求解最優(yōu)調(diào)度路徑模型。最后，以寧波市公共自行車區(qū)域調(diào)度為例，運用Matlab進行仿真實驗，證明了該模型及求解算法的有效性和可行性。

關(guān)鍵詞：公共自行車調(diào)度；蟻群算法；模糊時間窗

DOI：10.16315/j.stm.2015.06.006

中圖分類號：U491.1+7

文獻標志碼：A

公共自行車系統(tǒng)可有效緩解公共交通末端“最后一公里”出行難題，從而成為城市公共交通的重要輔助形式。然而各城市在逐步推進公共自行車系統(tǒng)建設(shè)的同時，也伴隨著不少問題，其中共性又極具代表性的是公共自行車的“租還車難”問題。由此引發(fā)的公共自行車調(diào)度是以滿足租賃者的租還需求為目的，為了提高公共自行車周轉(zhuǎn)率的特殊的物流活動?，F(xiàn)階段我國各城市的公共自行車調(diào)度工作主要以人工調(diào)度為主，信息化水平不高，調(diào)度人員多以歷史或?qū)崟r公共自行車租借數(shù)據(jù)憑主觀經(jīng)驗通過巡邏的方式安排車輛調(diào)度路徑，尚未形成科學系統(tǒng)的調(diào)度模式，時效性不高，不乏出現(xiàn)公共自行車車輛到位時租賃者轉(zhuǎn)而選擇其他交通方式的現(xiàn)象。

對于城市公共自行車調(diào)度，現(xiàn)有的研究主要分為靜態(tài)跟動態(tài)調(diào)度兩方面。在靜態(tài)調(diào)度方面：劉登濤等以運輸成本最小化為目標建立了公共自行車系統(tǒng)的調(diào)度模型，并運用模擬退火算法求解該模型，得到了公共自行車系統(tǒng)的靜態(tài)調(diào)度計劃。Benchimol[4]和Chemla假設(shè)城市公共自行車系統(tǒng)中各租賃點自行車庫存量已給定，即在調(diào)度需求己知的情況下，以運輸費用最小化為目標，進行公共自行車的調(diào)度。Gune等研究了公共自行車系統(tǒng)的靜態(tài)再平衡分配問題，以實現(xiàn)最低調(diào)度成本為目標確定調(diào)度序列站，由一輛調(diào)度車輛將公共自行車收集起來并交付到各個站點。但由于現(xiàn)實中公共自行車的流動性，公共自行車調(diào)度問題應隸屬動態(tài)調(diào)控，采用靜態(tài)模式研究無法更精準的預估結(jié)果，研究也具有一定的滯后性。因此衍生出了一系列公共自行車動態(tài)調(diào)度研究：董紅召等針對公共慢行系統(tǒng)中存在的公共自行車在時間和空間上分布不均衡的問題，研究了公共慢行系統(tǒng)調(diào)度過程中租賃點需求的動態(tài)特性及其模糊時間窗的約束，以最大化租賃點的滿意度為目標建立了公共慢行系統(tǒng)調(diào)度的模型，動態(tài)的獲取調(diào)度計劃，進而實現(xiàn)公共慢行系統(tǒng)的動態(tài)調(diào)度。Leonardo C提出了一種動態(tài)自行車再分配仿真模型，模型的目的在于盡量減少自行車運營商的調(diào)度成本，同時兼顧用戶滿意度。吳滿金等對公共自行車調(diào)度過程中自助服務點調(diào)度的優(yōu)先級、動態(tài)需求特性、服務時間窗等進行了研究，建立了統(tǒng)籌用戶滿意度與企業(yè)調(diào)度成本的公共自行車系統(tǒng)動態(tài)調(diào)度多目標優(yōu)化模型，并設(shè)計了一種禁忌遺傳混合算法對動態(tài)調(diào)度模型進行了求解。張建國等建立了基于滾動時域的公共自行車調(diào)度路徑優(yōu)化模型，但該模型沒有考慮到裝卸自行車的服務時間等對整個調(diào)度時間的影響，結(jié)果并不完全可靠。

鑒于城市公共自行車調(diào)度的時效性，在既有研究的基礎(chǔ)上，本文通過構(gòu)建帶模糊時間窗的調(diào)度模型，提出了一種區(qū)域單調(diào)度中心多調(diào)度車輛的調(diào)度模式，并將基本蟻群算法進行改進后運用于求解該模型，最后通過真實數(shù)據(jù)進行案例分析，從而驗證模型及算法的合理性和科學性。

1 問題分析

城市公共自行車系統(tǒng)通常都具備相應的調(diào)度中心，其功能為實時掌握各個公共自行車租賃點的車輛運營狀況，一旦租賃點的公共自行車在樁數(shù)量未在有效安全閥值以內(nèi)，一般為租賃點20%-80%的公共自行車在樁率，就該對該租賃點的車輛進行調(diào)度，從而避免出現(xiàn)空樁或滿樁現(xiàn)象。當然，更完善的調(diào)度系統(tǒng)同時具備了預調(diào)度功能，即根據(jù)歷史經(jīng)驗數(shù)據(jù)對重點觀察的租賃點在公共自行車數(shù)量未報警時就提前展開調(diào)度工作。

根據(jù)實際城市公共自行車調(diào)度狀況，本文所要解決的是帶模糊時間窗的公共自行車調(diào)度問題：即在某一特定時段，若干個公共自行車租賃點同時產(chǎn)生調(diào)度需求時，在現(xiàn)有調(diào)度資源有限的情況下，引入時間懲罰的概念，以各個公共自行車租賃點的滿意度最大化為目標，調(diào)度車在既定的時間窗內(nèi)將過剩的公共自行車收集起來，合理有效得分配到各個車輛不足的公共自行車租賃點。2模型描述

以公共自行車租賃點滿意度最大化為目標函數(shù)所建立的調(diào)度模型與調(diào)度車輛抵達租賃點的調(diào)度時間密切相關(guān)。在實際公共自行車系統(tǒng)的調(diào)度過程中，特別在早晚高峰期間，調(diào)度中心都會根據(jù)各個租賃點的歷史租還車輛數(shù)據(jù)，在租賃點公共自行車數(shù)量未報警時就提前安排調(diào)度工作。一旦租賃點的公共自行車數(shù)量未在安全閥值以內(nèi)，各個租賃點更傾向于在一開始即最佳的時間窗內(nèi)就能接受調(diào)度，只有這樣才可能百分百得滿足租賃者的租還需求。然而在實際調(diào)度過程中，在某一特定的時間范圍內(nèi)通常會出現(xiàn)若干個租賃點自行車數(shù)量同時報警，由于調(diào)度車輛有限部分租賃點很有可能被延遲服務，但在被延遲的這一段時間范圍內(nèi)，由于租賃點自身仍有自行車可以被租賃者租還，起到了緩沖作用，只不過這樣租賃點的滿意度會隨之降低，直到空滿樁現(xiàn)象發(fā)生滿意度才降為零。

為此，本文引入模糊時間的概念，建立帶模糊時間窗的車輛調(diào)度模型，即調(diào)度車未在最佳調(diào)度時間窗內(nèi)抵達租賃點對其進行調(diào)度服務時，租賃點的滿意度要打個折扣，具體表現(xiàn)在租賃點滿意度呈現(xiàn)對應下滑?？紤]到租賃者的租還意向?qū)φ{(diào)度時間的要求并不是完全線性的，通常情況下越靠近最佳的調(diào)度時間范圍，租賃點的滿意度流失得越慢，當調(diào)度時間超出可接受時間范圍，滿意度則降為0，

滿意度函數(shù)是用來衡量租賃點對調(diào)度工作的滿意程度，也可以從側(cè)面體現(xiàn)租賃者對調(diào)度工作的滿意程度，如圖1所示。

當調(diào)度車抵達租賃點ui的時間Ti∈（Ai，Bi）時，即車輛預調(diào)度時段，租賃點ui對此次調(diào)度服務的滿意度fi（Ti）最大，且fi（Ti）=1；當?shù)诌_時間Ti∈（Bi，Ci）時，即租賃點車輛數(shù)報警并已發(fā)出調(diào)度需求指令時段，租賃點ui對此次調(diào)度服務的滿意度fi（T）介于0與ι之間；當?shù)诌_時間Ti>Ci時，即租賃點已產(chǎn)生空滿樁現(xiàn)象，租賃點ui對此次調(diào)度服務的滿意度fi（Ti）最小，且fi（Ti）=0。因此，租賃點滿意度函數(shù)可以表示為式中：0<β<1為租賃點對時間的敏感系數(shù)。因此，本文所研究的公共自行車調(diào)度的數(shù)學模型如下：U={u1，u2，u3，，，un}表示所有公共自行車租賃點的集合，n是所有需要調(diào)度公共自行車的租賃點的數(shù)目，調(diào)度中心為O。租賃點ui需要調(diào)度的自行車數(shù)量為|di|（0<|di|

目標函數(shù)為式中：Z為租賃點滿意度；T為時間軸；N（t）為t時刻，所有未被調(diào)度的租賃點集合；M（t）為t時刻，所有已調(diào)度完成的租賃點集合；tik為調(diào)度車k抵達租賃點ui的時間；Qi為調(diào)度車在租賃點ui調(diào)度完成后車上裝載的自行車數(shù)量。式（2）是該模型的目標函數(shù)，即實現(xiàn)租賃點的滿意度最大化；式（4）確保調(diào)度車不超載；式（5）確保調(diào)度車從調(diào)度中心出發(fā)完成調(diào)度任務后最終都要回到調(diào)度中心；式（6）確保每個租賃點有且僅被調(diào)度車服務一次。

3 模型求解

帶模糊時間窗的城市公共自行車調(diào)度路徑優(yōu)化問題是一個多約束非線性組合優(yōu)化問題，由于受到時間窗的約束，最短調(diào)度路徑不一定是最優(yōu)化選擇，目前多以啟發(fā)式算法求解該問題滿意解。蟻群算法作為一種基于動物種群的啟發(fā)式仿生優(yōu)化算法，由意大利學者Colomi等提出，因其具有良好的并行性、協(xié)作性和魯棒性，尋優(yōu)特性好，常用于求解VRP模型，但同時也存在搜索時間長、收斂速度慢、易陷于局部最優(yōu)等缺點。

3.1 基本蟻群算法

1）算法描述。設(shè)蟻群中共有m只螞蟻，將m只螞蟻放置在調(diào)度中心O，用禁忌表tabuk記錄當前螞蟻k（k=l，2，3，…，m）所走過的租賃點，每走過一個租賃點，都需要修改禁忌表，當所有n個租賃點都加入到tabM。中時，螞蟻k便完成了一次調(diào)度任務，此時螞蟻k所走過租賃點的路徑便是該模型的一個可行解。

2）信息素初始化。Tij（t）表示t時刻租賃點ui與租賃點uj之間路徑上的信息素濃度。在蟻群算法迭代初期，為減少租賃點間的距離信息對螞蟻開始搜索的影響，增強螞蟻初始搜索的隨機性，提高螞蟻對新路徑的搜索能力，各租賃點間路徑上的信息素均被初始化為Tij（O）=c，c為常數(shù)，通常取0。

3）選擇策略。螞蟻在運動過程中，根據(jù)各條路徑上的殘留信息素濃度Tij和路徑上的啟發(fā)式信息ηij來計算選擇下一個租賃點的概率。螞蟻k在t時刻由租賃點ui運動到租賃點uj的概率用pij（t）來表示。式中：allowedk={U-tabuk}表示螞蟻k尚未走訪的租賃點集合；a為信息啟發(fā)式因子，代表調(diào)度路徑的相對重要性，反映了螞蟻在運動過程中所積累的信息素濃度在螞蟻選擇運動路徑時所起的作用；β為期望啟發(fā)式因子，代表能見度的相對重要性，反映了螞蟻在運動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度。啟發(fā)函數(shù)ηij表示調(diào)度車自租賃點ui至租賃點ui的期望程度，ηij=l/tij。

4）信息素更新。為了避免殘留信息素過多所引起的殘留信息覆蓋啟發(fā)信息，在每只螞蟻完成對所有n個租賃點的遍歷（亦即一個循環(huán)）之后，就要對全局殘留信息進行更新處理。由此，在t+n時刻租賃點路徑ιij上的信息素濃度可按如下規(guī)則進行更新調(diào)整：式中：p為信息素的揮發(fā)系數(shù)，1-p則表示信息素殘留因子，p越小，算法的收斂性越高，但會降低螞蟻的全局搜索能力，取值范圍通常為0

3.2 蟻群算法改進

在真實的螞蟻尋優(yōu)過程中，存在信息素濃度越高，信息素揮發(fā)越快這一現(xiàn)象。雖然這樣有效防止了一些路徑上的信息素濃度無限制的增長，但當一些路徑上的信息素濃度減少到零之后，算法就有可能陷于局部最優(yōu)的困境。為此，本文對基本蟻群算法中信息素的更新策略對如下改進，當螞蟻完成一次循環(huán)之后，路徑上的信息素根據(jù)以上2個式子進行全局更新。

基本蟻群算法信息素更新中，即使部分信息素的濃度相差甚大，但其揮發(fā)的速率也是相同的。按照上述2個式子進行算法的全局更新，將揮發(fā)系數(shù)由常量p轉(zhuǎn)變?yōu)橐訲ij（t）為變量的正比例函數(shù)，可依據(jù)信息素濃度與揮發(fā)速率的同向關(guān)系調(diào)整信息素，避免一些路徑上的信息素濃度過早減少到零，從而導致算法過早收斂于局部最優(yōu)。式（11）中Q為信息素強度，本文在不同階段的螞蟻尋優(yōu)循環(huán)中，Q采取了不同的值，在算法初始階段采取相對較小的值，使得路徑上的信息素濃度變化較慢，盡量避免算法過早收斂到局部最優(yōu)，而在算法尋優(yōu)后期采取相對較大的值，從而增強算法的正反饋效應，搜索出最優(yōu)路徑。

4 實例研究

4.1 數(shù)據(jù)源

本研究選取寧波市海曙區(qū)段塘片區(qū)16個公共自行車租賃點作為實驗樣本，對調(diào)度中心采集提取的實時公共自行車在樁數(shù)據(jù)進行統(tǒng)計預處理發(fā)現(xiàn)，在一天的08：00-09：00時段，上述16個公共自行車租賃點的車輛流動性最大，通過聚類的分析方法確定了各個租賃點的最佳調(diào)度時間窗和可接受調(diào)度時間窗，分別代表公共自行車系統(tǒng)的預調(diào)度時段和車輛數(shù)報警至租賃點發(fā)生空滿樁現(xiàn)象的過渡緩沖時段；在各個租賃點裝卸公共自行車的服務時間與調(diào)入出量成正比，為10輛車每分鐘；調(diào)度車輛的最大載荷為25輛公共自行車；由Google maps獲取海曙區(qū)調(diào)度中心寧波公交新典路站的經(jīng)緯度為（121.520791，29.863554），為便于區(qū)分，去掉東經(jīng)及北緯相同的部分，改為（20791，63554），下同，如表1所示。

4.2 路徑優(yōu)化

運用本文提供的改進蟻群算法對上述模型進行求解。以Matlab為工具，初始參數(shù)設(shè)置為：a=l：β=i；p=o.1；NCmax=500。通過使用本文提出的方法，運算結(jié)果最終得到最優(yōu)調(diào)度路徑，如圖2所示，仿真結(jié)果顯示完成本次調(diào)度工作需要3輛車，各輛車的調(diào)度子路徑如下，O代表調(diào)度中心。

子路徑1：0-128-165-159-0

子路徑2：0-153-157-155-0

子路徑3：0-119-17-19-27-30-150-162-163-164-177-O

4.3 結(jié)果分析

對寧波市海曙區(qū)段塘片區(qū)的公共自行車租賃點的運營現(xiàn)狀跟調(diào)度現(xiàn)狀進行分析，利用Matlab編程實現(xiàn)蟻群算法求解帶時間窗的城市公共自行車調(diào)度模型，其中：運用基本蟻群算法求解該模型的滿意度為3.4286，改進蟻群算法得到的滿意度為4.3529，相比于基本蟻群算法滿意度提升了26.96%。

通過實例仿真結(jié)果比較，本文所改進的蟻群算法是可行的，在車輛調(diào)度路徑方面，相比于基本蟻群算法，解的質(zhì)量有所提高，收斂速度有所提升。同時也可以看出，本文所改進的蟻群算法對于解決城市公共自行車車輛路徑問題是有效的，能夠快速地收斂到全局最優(yōu)解。