基于粒子群算法的公共自行車調(diào)度優(yōu)化問(wèn)題

岳曉鵬，全啟圳，何月華

（許昌學(xué)院 數(shù)理學(xué)院，河南 許昌 461000）

1 問(wèn)題背景

近年來(lái)，公共自行車作為一種新的交通方式，得到了越來(lái)越多人的支持與認(rèn)可。公共自行車在使用過(guò)程中不會(huì)對(duì)環(huán)境形成任何污染，節(jié)能環(huán)保，與此同時(shí)，隨著廣大市民環(huán)保認(rèn)識(shí)的提升，大家逐漸更注重生活品質(zhì)，更愿意選擇健康綠色的交通方式，共享單車這一交通方式的出現(xiàn)在某種程度上滿足了人們對(duì)于綠色出行的需要。

目前，針對(duì)公共自行車調(diào)度方面的研究較少。蔣塬銳[1]等針對(duì)共享單車供需失衡、共享率低等困難，提出了目標(biāo)為最小成本的共享單車靜態(tài)調(diào)度模型，并利用單親遺傳算法求解；趙曼[2]對(duì)共享單車網(wǎng)絡(luò)，采用社會(huì)網(wǎng)絡(luò)分析法，提出了特征量和凝聚子群，得到了共享單車的局部最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)，并基于此提出調(diào)度路徑最優(yōu)方案；周傳鈺[3]結(jié)合共享單車的特點(diǎn)，考慮了軌道交通站點(diǎn)接駁區(qū)域的單車投放規(guī)模，提出調(diào)度最優(yōu)模型；盧琰[4]結(jié)合不同時(shí)段共享單車的分布特點(diǎn)，構(gòu)建混合軸輻式共享單車網(wǎng)絡(luò)結(jié)構(gòu)，提出有調(diào)度任務(wù)時(shí)間范圍和無(wú)調(diào)度任務(wù)時(shí)間范圍的調(diào)度優(yōu)化模型，并利用遺傳算法對(duì)模型驗(yàn)證進(jìn)行求解。還有一些學(xué)者利用粒子群算法在智能機(jī)器人路徑規(guī)劃、交通路線設(shè)計(jì)、物流線路規(guī)劃等方面開(kāi)展了應(yīng)用研究[5-9]。

本文在研究公共自行車調(diào)度問(wèn)題及調(diào)度影響因素后，將公共自行車的調(diào)度問(wèn)題類比為旅行商問(wèn)題，設(shè)計(jì)了基于旅行商問(wèn)題的0-1規(guī)劃數(shù)學(xué)模型，并運(yùn)用粒子群算法進(jìn)行模型的求解。

2 粒子群算法的基本原理

2.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）在1995年由Kennedy和Eberhart提出。該算法源于對(duì)鳥類捕食行為的研究[10]。粒子群算法首先隨機(jī)地初始化一群均勻分布在給定的尋優(yōu)空間中的粒子（種群規(guī)模一般為30個(gè)），然后所有的粒子根據(jù)2個(gè)極值來(lái)更新自身的速度：一個(gè)是個(gè)體極值P；另一個(gè)是群體極值g。設(shè)粒子群中粒子的總數(shù)為N，粒子的維數(shù)為m，算法的終止條件（即最大迭代次數(shù)）為M，第i個(gè)粒子在t時(shí)刻的飛行速度以及位置分別為vi（t）=[vi1（t），vi2（t），...，vim（t）]T和xi（t）=[xi1（t），xi2（t），...，xim（t）]T，而對(duì)于粒子在t時(shí)刻的個(gè)體極值表示為pi（t）=[pi1（t），pi2（t），...，pim（t）]T，同樣可以得到群體極值表達(dá)gi（t）=[gi1（t），gi2（t），...，gim（t）]T，因此所有的粒子按照如下的更新方式在搜索空間中飛行以找到最優(yōu)解。

其中：ω為慣性權(quán)重系數(shù)，c1為個(gè)體學(xué)習(xí)因子，c2為社會(huì)學(xué)習(xí)因子。

2.2 粒子群算法的求解流程

Step1：設(shè)置種群規(guī)模、變量范圍、慣性權(quán)重、學(xué)習(xí)因子等參數(shù)，并隨機(jī)地初始化一群均勻分布在給定的尋優(yōu)空間中的粒子（包含速度和位置信息）。

Step2：計(jì)算群體中各個(gè)粒子的適應(yīng)度值，設(shè)置第i個(gè)粒子的適應(yīng)度值為它的當(dāng)前個(gè)體極值pi，所有粒子中的最好粒子設(shè)置為群體的全體極值g。

Step3：根據(jù)公式（1）、（2）更新每個(gè)粒子的速度和位置。

Step4：對(duì)所有粒子，將其當(dāng)前的函數(shù)值與它以前找到過(guò)的最好位置進(jìn)行比較，如果當(dāng)前位置較好，則將個(gè)體最優(yōu)位置pi設(shè)置為這個(gè)粒子的位置，然后再對(duì)群體的全局極值g更新。

Step5：判斷給定的終止條件是否滿足。若滿足終止條件，停止搜索，輸出需要的結(jié)果；否則，返回Step3繼續(xù)搜索。

3 模型的建立和求解

3.1 公共自行車的調(diào)度選取

本文主要是研究許昌市東城區(qū)的公共自行車調(diào)度問(wèn)題，因此搜集30個(gè)公共自行車駐放點(diǎn)的地理坐標(biāo)，并計(jì)算出各個(gè)駐放點(diǎn)之間的距離，即各個(gè)駐放點(diǎn)的地理坐標(biāo)見(jiàn)表1，其之間的距離見(jiàn)表2（由于駐放點(diǎn)較多，僅展示部分?jǐn)?shù)據(jù)）。

表1 部分駐放點(diǎn)編號(hào)

表2 各個(gè)駐放點(diǎn)間的距離 單位：km

3.2 模型假設(shè)

為將該調(diào)度模型轉(zhuǎn)化為數(shù)學(xué)模型，進(jìn)行模型假設(shè)，保證一定的準(zhǔn)確性。

（1）在研究對(duì)象范圍內(nèi)，僅設(shè)立了1個(gè)車場(chǎng)和1個(gè)調(diào)度車。（2）調(diào)度車必須經(jīng)過(guò)每一個(gè)停靠點(diǎn)，并且每一個(gè)停靠點(diǎn)僅能經(jīng)過(guò)1次。（3）為保障能較好地完成調(diào)度，行車速度在40 km/h，裝或卸載3 min。（4）調(diào)度車調(diào)度過(guò)程中，公共自行車輛始終保持充足且不超過(guò)最大載重。

3.3 模型的建立

3.3.1 公共自行車的路程規(guī)劃

本文將調(diào)度問(wèn)題視為0-1規(guī)劃問(wèn)題，建立旅行商問(wèn)題的數(shù)學(xué)模型。首先，需要確定停靠點(diǎn)i和停靠點(diǎn)j是否連通，即調(diào)度車輛從路線xij上經(jīng)過(guò)記為1，否則記為0。

又有調(diào)度車輛最短路徑問(wèn)題，目標(biāo)函數(shù)取最小值，對(duì)所有存在調(diào)度車經(jīng)過(guò)的路徑xij=1的距離dij求和，為此得到以下規(guī)劃模型：

基于問(wèn)題的假設(shè)和實(shí)際的調(diào)度情況，本文對(duì)目標(biāo)函數(shù)進(jìn)行了一定的約束，其（4）（5）式表示調(diào)度車必須經(jīng)過(guò)每一個(gè)停靠點(diǎn)，并且每一個(gè)停靠點(diǎn)僅能經(jīng)過(guò)1次；（6）式表示所有的停靠點(diǎn)能且只能作為路線起點(diǎn)和終點(diǎn)各1次。

3.3.2 公共自行車的調(diào)度耗時(shí)計(jì)算

針對(duì)運(yùn)輸車在調(diào)度的過(guò)程中，消耗的時(shí)間主要花費(fèi)在路線耗時(shí)和裝卸自行車上，因此可以得到運(yùn)輸用時(shí)條件：

針對(duì)調(diào)度用時(shí)的計(jì)算，運(yùn)輸過(guò)程的耗時(shí)由（7）式表示，而（8）式則表示裝或卸載公共自行車的時(shí)間，最后由（9）式得到總的時(shí)間。其中e為每個(gè)駐放點(diǎn)的裝或卸載的平均耗時(shí)。

3.4 基于智能算法下的模型求解

由于居民對(duì)于公共自行車的需求時(shí)刻和數(shù)量是隨機(jī)的，為了更好、更快地進(jìn)行調(diào)度，使得公共自行車系統(tǒng)能夠較好地承受需求，先選擇15個(gè)駐放點(diǎn)依次進(jìn)行仿真實(shí)驗(yàn)完成調(diào)度問(wèn)題。模型中的個(gè)體學(xué)習(xí)因子c1=1，社會(huì)學(xué)習(xí)因子c2=0.1，慣性因子ω=0.2，慣性因子最大值ωmax=1，慣性因子最小值ωmin=0.2，粒子數(shù)量N=500，迭代次數(shù)M=1 000進(jìn)行求解，如圖1和圖2所示。

圖1 15個(gè)駐放點(diǎn)各代最短距離與平均距離對(duì)比圖

圖2 15個(gè)駐放點(diǎn)粒子群算法優(yōu)化路徑圖

從圖1可以看出，迭代次數(shù)在75以內(nèi)，下降速度快，而在75次以后，狀態(tài)保持平穩(wěn)，但對(duì)于各個(gè)粒子的平均距離，在1 000次迭代內(nèi)始終處于保持下降趨勢(shì)與最短距離存在一定的間距。

從圖1可以得到，該模型求解的最優(yōu)調(diào)度運(yùn)輸路線為：1→2→3→13→14→15→4→7→8→10→11→12→9→6→5→1。

因此，從調(diào)度車停車場(chǎng)出發(fā)到最后回到起點(diǎn)，依次經(jīng)過(guò)2，3，4，…，6，5，其優(yōu)化總距離為6.09 km，所耗費(fèi)總時(shí)間為0.91 h。

4 靈敏度分析

針對(duì)粒子群算法的參數(shù)設(shè)置，個(gè)體學(xué)習(xí)因子c1，根據(jù)自身經(jīng)驗(yàn)來(lái)計(jì)算粒子飛翔速度的權(quán)重；社會(huì)學(xué)習(xí)因子c2，根據(jù)自群體經(jīng)驗(yàn)來(lái)計(jì)算粒子飛翔速度的權(quán)重；粒子數(shù)量N，粒子數(shù)越多，搜索能力越強(qiáng)；慣性因子，其值較大時(shí)，全局尋優(yōu)能力強(qiáng)，局部尋優(yōu)能力弱，反之相反。迭代次數(shù)，次數(shù)過(guò)少結(jié)束過(guò)早不易得到最優(yōu)解，次數(shù)過(guò)大增大耗時(shí)，因此也不宜過(guò)大。本文繼續(xù)選用15個(gè)駐放點(diǎn)來(lái)對(duì)初始溫度、終止溫度及降溫系數(shù)進(jìn)行研究對(duì)比分析，結(jié)果見(jiàn)表3。

表3 初始溫度、終止溫度及降溫系數(shù)對(duì)結(jié)果的影響

通過(guò)表3數(shù)據(jù)可以看出，對(duì)于個(gè)體學(xué)習(xí)因子和社會(huì)學(xué)習(xí)因子，更多的是需要考慮自主的經(jīng)驗(yàn)，其次較少考慮群體經(jīng)驗(yàn)來(lái)進(jìn)行計(jì)算；為了保障粒子在搜索的過(guò)程具有一定的效果且在一定的迭代效果下能有好的解，其粒子數(shù)量設(shè)置為500，迭代次數(shù)1 000較為合適；最后關(guān)于慣性因子的設(shè)置，通過(guò)表3可以看出，針對(duì)這一問(wèn)題尋優(yōu)能力的受參數(shù)的影響不大，因此依舊選擇0.2作為模型初值。最終得到當(dāng)個(gè)人學(xué)習(xí)因子1，社會(huì)學(xué)習(xí)因子0.1，粒子數(shù)量500，慣性因子0.2，迭代次數(shù)1 000時(shí)，最短路徑距離6.01 km。

通過(guò)選取15個(gè)駐放點(diǎn)的數(shù)值模擬可以在適當(dāng)?shù)膮?shù)設(shè)置下，模擬效果良好，現(xiàn)使用這套參數(shù)進(jìn)行實(shí)際計(jì)算，選用30個(gè)駐放點(diǎn)進(jìn)行模擬調(diào)度，模擬結(jié)果如圖3和圖4所示，得到總路程為13.30 km，總耗時(shí)1.83 h。

圖3 30個(gè)駐放點(diǎn)各代最短距離與平均距離對(duì)比

圖4 30個(gè)駐放點(diǎn)粒子群算法優(yōu)化路徑

由于每天需要調(diào)度的駐放點(diǎn)的位置和數(shù)量不同，運(yùn)輸車的運(yùn)輸路線、路程以及所花的時(shí)間都有所不同，但完成調(diào)度時(shí)長(zhǎng)一般不會(huì)超過(guò)2 h，否則，市民在無(wú)車可用或者無(wú)車位可放車時(shí)，都會(huì)降低對(duì)于公共自行車系統(tǒng)的滿意度，因此在任務(wù)分配時(shí)，可以根據(jù)不同的站點(diǎn)位置及數(shù)量選擇路線來(lái)完成任務(wù)。

5 結(jié)論

本文主要研究公共自行車調(diào)度車的路線運(yùn)輸以及工作效率的優(yōu)化。主要選用旅行商問(wèn)題中的路線規(guī)劃模型以及依據(jù)車輛的平均速度、裝卸速度等參數(shù)，利用粒子群算法對(duì)該模型進(jìn)行求解，并進(jìn)行了算法參數(shù)的靈敏度分析。

相比其他智能算法，粒子群算法的參數(shù)設(shè)置易于理解，且利用參數(shù)將粒子速度和位置的合理把握，可以很好地解決這一路徑問(wèn)題。但粒子群法一般要保證研究對(duì)象在30個(gè)以內(nèi)才有較好的解，否則效果較差，而實(shí)際問(wèn)題研究對(duì)象有時(shí)會(huì)超過(guò)這一標(biāo)準(zhǔn)，這時(shí)可以考慮將全部站點(diǎn)劃分為多個(gè)工作區(qū)分別進(jìn)行調(diào)度。