基于模擬退火算法的公共自行車調(diào)度優(yōu)化問題

岳曉鵬 全啟圳 何月華

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

1 問題背景

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

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

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

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

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

Step1：隨機產(chǎn)生出初始解X0，使Xbest=X0，并計算目標函數(shù)值E（Xbest）；

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

Step3：基于當前最優(yōu)解Xbest鄰域函數(shù)產(chǎn)生新解Xnew，計算新解的目標函數(shù)值E（Xnew），并且計算目標函數(shù)值的增量，?E=E（Xnew）-E（Xbest）

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

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

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

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

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

3 模型的建立和求解

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

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

表1 部分駐放點編號

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

3.2 模型假設

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

（1）在研究對象范圍內(nèi)，僅設立了一個車場和一個調(diào)度車；

（2）調(diào)度車必須經(jīng)過每一個?？奎c，并且每一個?？奎c僅能經(jīng)過一次；

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

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

3.3 模型的建立

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

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

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

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

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

3.4.1 模擬退火算法的求解

由于當?shù)鼐用竦膶τ诠沧孕熊嚨男枨螅瑸榱烁?、更快的使得公共自行車系統(tǒng)能夠較好的承受每日的需求，現(xiàn)確定20、40 和60 個駐放點依次進行仿真實驗完成調(diào)度問題。

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

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

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

3.4.2 模擬退火算法的應用

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

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

圖1 每次迭代最短路徑圖

從圖2 可以得到，該模型求解的最優(yōu)調(diào)度運輸路線為：

圖2 最優(yōu)調(diào)度路線

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

因此，從調(diào)度車停車場出發(fā)到最后回到起點，依次經(jīng)過4，5，6，…，3，2，其優(yōu)化總距離為13.08km，計算求解耗時38.99s，求解速度較快。

4 靈敏度分析

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

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

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

5 主要結(jié)論

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

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