基于模擬退火算法的公共自行車調度優化問題

岳曉鵬 全啟圳 何月華

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

1 問題背景

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

目前，針對公共自行車調度方面的研究較少。蔣塬銳[1]等針對共享單車供需失衡、共享率低等困難，提出了目標為最小成本的共享單車靜態調度模型，并利用單親遺傳算法求解。李明明[2]對公共自行車的運營和調度進行研究，基于大數據的數據歸納，研究公共自行車的時間特性和周轉特性，并選用改進蟻群算解決調度模型。馮炳超、吳璟莉[3]提出基于單親遺傳算法的求解方法，利用大量的模擬數據和真實數據，求解自行車共享系統靜態再平衡問題的有效方法。盧琰[4]結合不同時段共享單車的分布特點，構建混合軸輻式共享單車網絡結構，提出有調度任務時間范圍和無調度任務時間范圍的調度優化模型，并利用遺傳算法對模型驗證進行求解。本文在分析完公共自行車調度問題及調度影響因素后，將公共自行車的調度問題類比為旅行商問題，設計了基于旅行商問題的0-1 規劃數學模型。并運用模擬退火進行模型的求解。

2 模擬退火算法的基本原理

模擬退火算法（Simulated Annealing，SA）是1953 年由N.Metropolis 等人提出的，后來經Kirkpatrick 等人推廣后得以廣泛應用[5]。SA 模擬物理固體退火的冷卻降溫過程，從某一很高的溫度出發，隨著溫度的下降，按照Metropolis 準則，結合概率突跳特性在解空間中隨機尋找全局最優解，即局部最優解可以概率性地跳出并趨于全局最優解。

模擬退火算法的求解流程：

Step1：隨機產生出初始解X0，使Xbest=X0，并計算目標函數值E（Xbest）；

Step2：給定初始溫度T0及各參數包括降溫系數kr 終止溫度Tend 每個溫度的迭代次數Iter，且T=T0，i=1；

Step3：基于當前最優解Xbest鄰域函數產生新解Xnew，計算新解的目標函數值E（Xnew），并且計算目標函數值的增量，?E=E（Xnew）-E（Xbest）

Step4：如果?E＜0，則Xbest=Xnew，即接受新解為當前最優解；

Step5：如果?E＞0，則接受概率為p（?E）=exp（-?E/T），然后以rand 產生[0，1]區間上隨機數，若rand＜p（?E），則Xbest=Xnew，即接受新解為當前最優解，否則放棄此新解，之前的Xbest仍然為最優解；令i=i+1；

Step6：判斷i≤Iter，如果滿足此條件，則重復進行步驟Step3～Step5，否則繼續進行下一步；

Step7：冷卻降溫T=kr·T，i=1；

Step8：判斷終止條件T≤Tend，如果滿足該條件，則停止計算，輸出最優解Xbest否則返回步驟Step3 繼續計算。

3 模型的建立和求解

3.1 公共自行車的調度選取

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

表1 部分駐放點編號

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

3.2 模型假設

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

（1）在研究對象范圍內，僅設立了一個車場和一個調度車；

（2）調度車必須經過每一個?？奎c，并且每一個?？奎c僅能經過一次；

（3）調度車沒有時間和速度限制，正常行駛；

（4）調度車調度過程中，公共自行車輛始終保持充足且不超過最大載重。

3.3 模型的建立

針對旅行商問題，目前的學術界的普遍觀點是：旅行商問題是一個NP 難題，除非當P=NP 時，否則求解旅行商問題并不存在一種行之有效的精確算法. 因而我們只能找到一些在某些方面接近最優解的解決方案[7-8]。

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

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

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

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

3.4.1 模擬退火算法的求解

由于當地居民的對于公共自行車的需求，為了更好、更快的使得公共自行車系統能夠較好的承受每日的需求，現確定20、40 和60 個駐放點依次進行仿真實驗完成調度問題。

這里設置算法參數，初始溫度T0=1000℃，終止溫度Tend=0.001℃，降溫系數kr=0.97，迭代次數Iter=454。由于該方法得到的一般為近似解，因此每種情況執行5 次并統計該情況下的最短總距離及求解時長，如表3 所示。

表3 不同數量駐放點下的模擬退火5 次求解

通過上表可以得到，在模擬退火算法下，20、40 和60 的這3種情況下的最短距離依次為8.49、19.06 和22.04km。

3.4.2 模擬退火算法的應用

在實際情況下，由于時間限制，一輛調度車負責的駐放點不會太多，這里以30 個駐放點為例進行模擬求解，結果如圖1 和圖2 所示。

由圖1 可以看出，迭代次數在50 以內，下降速度快，而在50～140 時，狀態保持平穩，當150～275 時，再次下降且比前期幅度大，直至320 以后處于平穩狀態。

圖1 每次迭代最短路徑圖

從圖2 可以得到，該模型求解的最優調度運輸路線為：

圖2 最優調度路線

1→4→5→6→7→17→8→9→10→11→12→25→24→23→18→21→20→22→29→30→28→27→26→19→15→16→14→13→3→2→1

因此，從調度車停車場出發到最后回到起點，依次經過4，5，6，…，3，2，其優化總距離為13.08km，計算求解耗時38.99s，求解速度較快。

4 靈敏度分析

針對模擬退火算法的參數設置，初始溫度越高，調度路徑的變化程度就越大，容易導致出現較差的解，而終止溫度則作為算法停止的平衡條件，一般溫度較低。當初始溫度相對較高時不利于算法的收斂，過低時不利于計算效率導致迭代的過高。降溫系數控制著溫度變化的快慢，數值越小，降溫越快，過早的結束算法不利于最優解的尋優。這里繼續選用30 個駐放點來對初始溫度、終止溫度及降溫系數進行研究對比分析，結果如表4 所示。

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

通過上表數據可以看出，當提高初始溫度時，求解時間變長，但所得最優距離相對略大。對于終止溫度，隨著設置溫度的上升，求解速度越快，但其最終結果并沒有0.001 時好，最優距離變遠。針對降溫系數，系數的上升并沒有得到更好的解，反而延長了求解的時間。最終得到當初始溫度1000℃，終止溫度0.001℃，降溫系數0.97 時，最短路徑距離13.08km。

5 主要結論

本文主要是研究公共自行車的調度問題，通過將公共自行車的調度問題類比轉化為旅行商問題，從而構建出了調度車的調度路徑的優化模型，再利用模擬退火法算法求解該模型并加以分析，得出以下結論：

對于大多數的智能算法都容易陷入局部最優，本文利用模擬退火算法有效的避免陷入局部最優解，因此模擬退火算法能有效地解決本文提出的調度路徑優化模型。又因模擬退火算法受各種參數的影響過大，所以對初始溫度，終止溫度和降溫系數進行靈敏度分析，做參數設置的相關研究，最終確定了本次模擬退火算法所用的參數大小，從而得到了較為滿意的運算結果。