岳曉鵬 全啟圳 何月華

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

1 問題背景

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

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

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

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

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

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

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

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

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

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

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

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

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

3 模型的建立和求解

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

本文主要是研究許昌市魏都區(qū)一帶的公共自行車調(diào)度問題，因此搜集60 個(gè)公共自行車的駐放點(diǎn)的地理坐標(biāo)，并計(jì)算出各個(gè)駐放點(diǎn)之間的距離，即各個(gè)駐放點(diǎn)的地理坐標(biāo)如表1 所示，其之間的距離如表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è)立了一個(gè)車場(chǎng)和一個(gè)調(diào)度車；

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

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

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

3.3 模型的建立

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

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

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

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

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

3.4.1 模擬退火算法的求解

由于當(dāng)?shù)鼐用竦膶?duì)于公共自行車的需求，為了更好、更快的使得公共自行車系統(tǒng)能夠較好的承受每日的需求，現(xiàn)確定20、40 和60 個(gè)駐放點(diǎn)依次進(jìn)行仿真實(shí)驗(yàn)完成調(diào)度問題。

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

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

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

3.4.2 模擬退火算法的應(yīng)用

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

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

圖1 每次迭代最短路徑圖

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

圖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)度車停車場(chǎng)出發(fā)到最后回到起點(diǎn)，依次經(jīng)過4，5，6，…，3，2，其優(yōu)化總距離為13.08km，計(jì)算求解耗時(shí)38.99s，求解速度較快。

4 靈敏度分析

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

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

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

5 主要結(jié)論

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

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