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

岳曉鵬，全啟圳，何月華

（許昌學院 數理學院，河南 許昌 461000）

1 問題背景

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

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

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

2 粒子群算法的基本原理

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

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）在1995年由Kennedy和Eberhart提出。該算法源于對鳥類捕食行為的研究[10]。粒子群算法首先隨機地初始化一群均勻分布在給定的尋優(yōu)空間中的粒子（種群規(guī)模一般為30個），然后所有的粒子根據2個極值來更新自身的速度：一個是個體極值P；另一個是群體極值g。設粒子群中粒子的總數為N，粒子的維數為m，算法的終止條件（即最大迭代次數）為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，同樣可以得到群體極值表達gi（t）=[gi1（t），gi2（t），...，gim（t）]T，因此所有的粒子按照如下的更新方式在搜索空間中飛行以找到最優(yōu)解。

其中：ω為慣性權重系數，c1為個體學習因子，c2為社會學習因子。

2.2 粒子群算法的求解流程

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

Step2：計算群體中各個粒子的適應度值，設置第i個粒子的適應度值為它的當前個體極值pi，所有粒子中的最好粒子設置為群體的全體極值g。

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

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

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

3 模型的建立和求解

3.1 公共自行車的調度選取

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

表1 部分駐放點編號

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

3.2 模型假設

為將該調度模型轉化為數學模型，進行模型假設，保證一定的準確性。

（1）在研究對象范圍內，僅設立了1個車場和1個調度車。（2）調度車必須經過每一個停靠點，并且每一個停靠點僅能經過1次。（3）為保障能較好地完成調度，行車速度在40 km/h，裝或卸載3 min。（4）調度車調度過程中，公共自行車輛始終保持充足且不超過最大載重。

3.3 模型的建立

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

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

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

基于問題的假設和實際的調度情況，本文對目標函數進行了一定的約束，其（4）（5）式表示調度車必須經過每一個停靠點，并且每一個停靠點僅能經過1次；（6）式表示所有的停靠點能且只能作為路線起點和終點各1次。

3.3.2 公共自行車的調度耗時計算

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

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

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

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

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

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

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

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

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

4 靈敏度分析

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

表3 初始溫度、終止溫度及降溫系數對結果的影響

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

通過選取15個駐放點的數值模擬可以在適當的參數設置下，模擬效果良好，現使用這套參數進行實際計算，選用30個駐放點進行模擬調度，模擬結果如圖3和圖4所示，得到總路程為13.30 km，總耗時1.83 h。

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

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

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

5 結論

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

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