張輝++鄭彭軍

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

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

DOI：10.16315/j.stm.2015.06.006

中圖分類號(hào)：U491.1+7

文獻(xiàn)標(biāo)志碼：A

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

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

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

1 問題分析

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

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

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

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

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

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

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

3 模型求解

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

3.1 基本蟻群算法

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

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

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

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

3.2 蟻群算法改進(jìn)

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

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

4 實(shí)例研究

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

本研究選取寧波市海曙區(qū)段塘片區(qū)16個(gè)公共自行車租賃點(diǎn)作為實(shí)驗(yàn)樣本，對(duì)調(diào)度中心采集提取的實(shí)時(shí)公共自行車在樁數(shù)據(jù)進(jìn)行統(tǒng)計(jì)預(yù)處理發(fā)現(xiàn)，在一天的08：00-09：00時(shí)段，上述16個(gè)公共自行車租賃點(diǎn)的車輛流動(dòng)性最大，通過聚類的分析方法確定了各個(gè)租賃點(diǎn)的最佳調(diào)度時(shí)間窗和可接受調(diào)度時(shí)間窗，分別代表公共自行車系統(tǒng)的預(yù)調(diào)度時(shí)段和車輛數(shù)報(bào)警至租賃點(diǎn)發(fā)生空滿樁現(xiàn)象的過渡緩沖時(shí)段；在各個(gè)租賃點(diǎn)裝卸公共自行車的服務(wù)時(shí)間與調(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)化

運(yùn)用本文提供的改進(jìn)蟻群算法對(duì)上述模型進(jìn)行求解。以Matlab為工具，初始參數(shù)設(shè)置為：a=l：β=i；p=o.1；NCmax=500。通過使用本文提出的方法，運(yùn)算結(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é)果分析

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

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