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

岳曉鵬，全啟圳，何月華

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

1 問題背景

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

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

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

2 粒子群算法的基本原理

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

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）在1995年由Kennedy和Eberhart提出。該算法源于對鳥類捕食行為的研究[10]。粒子群算法首先隨機地初始化一群均勻分布在給定的尋優(yōu)空間中的粒子（種群規(guī)模一般為30個），然后所有的粒子根據(jù)2個極值來更新自身的速度：一個是個體極值P；另一個是群體極值g。設(shè)粒子群中粒子的總數(shù)為N，粒子的維數(shù)為m，算法的終止條件（即最大迭代次數(shù)）為M，第i個粒子在t時刻的飛行速度以及位置分別為vi（t）=[vi1（t），vi2（t），...，vim（t）]T和xi（t）=[xi1（t），xi2（t），...，xim（t）]T，而對于粒子在t時刻的個體極值表示為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為個體學(xué)習(xí)因子，c2為社會學(xué)習(xí)因子。

2.2 粒子群算法的求解流程

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

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

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

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

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

3 模型的建立和求解

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

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

表1 部分駐放點編號

表2 各個駐放點間的距離 單位：km

3.2 模型假設(shè)

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

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

3.3 模型的建立

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

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

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

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

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

針對運輸車在調(diào)度的過程中，消耗的時間主要花費在路線耗時和裝卸自行車上，因此可以得到運輸用時條件：

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

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

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

圖1 15個駐放點各代最短距離與平均距離對比圖

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

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

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

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

4 靈敏度分析

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

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

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

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

圖3 30個駐放點各代最短距離與平均距離對比

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

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

5 結(jié)論

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

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