基于模擬退火算法的應(yīng)急物流車輛調(diào)度

唐沖

（軍事交通學(xué)院 學(xué)員旅，天津 300161）

基于模擬退火算法的應(yīng)急物流車輛調(diào)度

唐沖

（軍事交通學(xué)院 學(xué)員旅，天津 300161）

根據(jù)應(yīng)急物流的突出特點，對應(yīng)急物流車輛調(diào)度路徑優(yōu)化進行了探討。建立了基于有單邊時間窗的應(yīng)急物流車輛調(diào)度問題的數(shù)學(xué)模型，并針對該數(shù)學(xué)模型，設(shè)計了與其相適應(yīng)的模擬退火算法。從實例計算結(jié)果看，該算法簡單可行，計算效率高，收斂速度快,對于加快物資投送，處理好突發(fā)事件具有重要意義。

模擬退火算法；應(yīng)急物流；車輛調(diào)度

1 引言

近年來，自然災(zāi)害、公共衛(wèi)生和社會安全事件在我國發(fā)生的頻率越來越高，對社會的發(fā)展進步造成了嚴重威脅。所謂應(yīng)急物流即是指以提供自然災(zāi)害、公共衛(wèi)生、社會動亂等突發(fā)事件所需應(yīng)急物資為目的，以追求時間效益最大化和災(zāi)害損失最小化為目標(biāo)的特種物流活動[1]。因此，如何處理好應(yīng)急物流的車輛路徑問題（VRP,Vehicle Rooting Problem）,成為減小突發(fā)事件帶來損失的關(guān)鍵。

解決應(yīng)急物流VRP的方法通常包括精確算法和啟發(fā)式算法。其中，精確算法由于其計算量隨問題規(guī)模的增大呈指數(shù)增長，實際應(yīng)用范圍受限[2]。而在啟發(fā)式算法中，模擬退火算法（SAA,Simulated Annealing Algorithm）以其收斂速度快、計算效率高的特點得到廣泛應(yīng)用。

SAA最早的思想由N.Metropolis于1953年提出，1983年S.Kirkpatrick成功將退火思想引入到組合優(yōu)化領(lǐng)域[3]，為解決應(yīng)急物流VRP提供了新的思路。但大部分研究，僅停留在解決無時限的VRP上，對于將SAA應(yīng)用于有時限的VRP的研究卻很少。本文基于SAA，解決了有單邊時間窗的應(yīng)急物流配送的車輛調(diào)度問題，得到了較好的計算結(jié)果。

2 單邊時間窗VRP模型

2.1 問題描述

為使問題易于理解，引入一個有單邊時間窗的配送車輛調(diào)度問題。在該問題中，所有節(jié)點及其配送中心之間都有線路連通，且各節(jié)點物資需求量一定，所有運輸車輛皆在0時刻出發(fā)，物資到達的單邊時間窗一定，要求合理安排運輸車輛，使得總的運輸距離最小。該問題滿足以下約束條件：(1)每個節(jié)點的物資需求量必須得到滿足，且只能由一臺車輛完成該節(jié)點的物資運送；(2)物資必須在允許的單邊時間窗內(nèi)到達節(jié)點；(3)車輛不允許超載。

某地發(fā)生地震災(zāi)害，現(xiàn)有n個受災(zāi)節(jié)點需要物資配送，某汽車部隊立即出動，準(zhǔn)備將駐地救災(zāi)物資運往受災(zāi)節(jié)點，駐地共有運輸車為K輛，載重量為Q,第i個受災(zāi)節(jié)點的物資需求量為gi(i=0,1,···,n),駐地到各節(jié)點的距離為d0i(i=0,1,···,n),運輸時間為t0i(i=0,1,···,n),各節(jié)點間的距離為 dij(i,j=0,1,···,n),運輸時間為tij(i,j=0,1,···,n),每噸貨物的卸貨時間為ta,貨物需要在[0,ai]內(nèi)運到i節(jié)點。

2.2 模型建立

通過分析上述條件，可得相鄰兩節(jié)點之間的物資達到時間滿足：

根據(jù)各節(jié)點物資需求量及單車運載量，確定路徑條數(shù)（所需車輛數(shù)）：

為方便模型建立，定義兩個0,1變量：

建立該單邊時間窗的配送車輛調(diào)度模型：

在上述模型中，(1)式為模型的目標(biāo)函數(shù)，要求最短運送距離最短；(2)式表示運送路徑數(shù)應(yīng)小于車輛總數(shù)；(3)式表示車輛k只能駛?cè)氚才牌溥\送的節(jié)點；(4)式表示車輛k只能駛出安排其運送的節(jié)點；(5)式表示某節(jié)點只能由一輛車運送物資；(6)式表示車輛應(yīng)在預(yù)定時間到達節(jié)點；(7)式表示運送路徑k上所有節(jié)點的物資總需求量應(yīng)小于車輛的載重量。

3 單邊時間窗VRP的模擬退火算法

3.1 模擬退火算法的原理

SAA是基于Monte-Carlo迭代求解法，并利用一般組合優(yōu)化問題與金屬退火原理的相似性建立的一種隨機搜索算法。金屬在被加熱至充分高，然后冷卻的過程中，內(nèi)部粒子由無序逐漸變?yōu)橛行?，且在每個溫度趨于能量最低態(tài)的概率為exp(-ΔE/kT)，E為溫度T時金屬的內(nèi)能，k為玻爾茲曼常數(shù)。利用這一退火特性，當(dāng)鄰域的一個解使得目標(biāo)函數(shù)減小時，便接受這個解作為新的當(dāng)前解，相反，SAA以的概率接受相對更差的解作為當(dāng)前解，Δf為前后兩次目標(biāo)函數(shù)的差值。這種具有概率突跳性的Metropolis搜索準(zhǔn)則有效地跳出了陷入局部最優(yōu)的瓶頸，從而達到全局最優(yōu)。其實現(xiàn)步驟如圖1所示。

圖1 SAA算法流程圖

其中，n(Tk)為提前設(shè)定的內(nèi)循環(huán)次數(shù)，Tf為外循環(huán)終止溫度，T0為初始溫度，n為溫度Tk下內(nèi)循環(huán)迭代步數(shù)，k為外循環(huán)降溫的次數(shù)。

3.2 單邊時間窗VRP的模擬退火算法設(shè)計

將單邊時間窗VRP與SAA對比可知，單邊時間窗VRP的解對應(yīng)退火金屬的狀態(tài)，目標(biāo)函數(shù)對應(yīng)退火過程中金屬的能量，而最優(yōu)解則對應(yīng)金屬退火中的最低能量狀態(tài)。為此，可以很好地將SAA運用于單邊時間窗VRP的求解中。

（1）解的評價指標(biāo)。解的評價指標(biāo)是取得最優(yōu)解的重要保證，為了將模型中不滿足時間，運量約束以及路徑數(shù)大于車輛數(shù)的解排除，引入懲罰因子P（根據(jù)目標(biāo)函數(shù)的值取一個較大的正數(shù)）。結(jié)合目標(biāo)函數(shù)，其表達式為：

（2）候選解的表示。采用自然數(shù)編碼的方式表示候選解，且路徑條數(shù)確定后，如6個節(jié)點，3條運送路徑的解可表示為0120340560。其中路徑1為0-1-2-0，路徑2為0-3-4-0，路徑3為0-5-6-0。

（3）候選解的產(chǎn)生[4]。任意交換兩個節(jié)點的位置，便可得到新的候選解，如交換節(jié)點1和節(jié)點5的位置，新的候選解便為05203416。

（4）降溫函數(shù)的確定。采用Tk+1=bTk的方式進行降溫，其中b為小于1的降溫系數(shù)。

（5）內(nèi)循環(huán)終止準(zhǔn)則。提前設(shè)定內(nèi)循環(huán)次數(shù)n(Tk)，即每個溫度下迭代的步數(shù)。

（6）外循環(huán)終止準(zhǔn)則。通過設(shè)定外循環(huán)終止溫度Tf，或者規(guī)定降溫次數(shù)的上限都可達到終止外循環(huán)的目的。

4 實例應(yīng)用

某地突發(fā)地震，現(xiàn)有8個受災(zāi)節(jié)點需要物資配送，某汽車部隊立即出動，準(zhǔn)備將駐地救災(zāi)物資運往各受災(zāi)節(jié)點，駐地共有運輸車20輛，單車載重量為10t，車速為65km/h，每噸物資的卸載時間為0.15h。各節(jié)點相關(guān)數(shù)據(jù)見表1，其中駐地坐標(biāo)設(shè)為（0，0）。

表1 各節(jié)點數(shù)據(jù)

首先，通過計算可得運送路徑為3條，即3輛運輸車便可滿足運輸需求。

SAA相關(guān)參數(shù)的設(shè)置為：內(nèi)循環(huán)次數(shù)n(Tk)=200，外循環(huán)終止溫度Tf=10，降溫系數(shù)b=0.95，初始溫度T0=1 200，懲罰因子P=500。通過MATLAB編程，隨機求解100次，可得結(jié)果見表2。

表2 SAA計算結(jié)果

由表2可知，在利用SAA100次的求解過程中，都能得到質(zhì)量較高的可行解，其中最短運送距離為686km。對應(yīng)的三條路徑分別為:路徑1為0-1-8-7-4-0，路徑長度為260km,運送時間為5.36h；路徑2為0-3-6-0,路徑長度為210km,運送時間為4.58h；路徑3為0-2-5-0,路徑長度為216km,運送時間為4.68h。

5 結(jié)束語

采用模擬退火算法對有單邊時間窗的配送車輛調(diào)度問題進行了求解。從實例應(yīng)用中可以看出，該算法簡單可行，計算效率高，收斂速度快，且能較好地達到全局最優(yōu)。為解決應(yīng)急物流的車輛路徑問題提供了新思路。

[1]張公讓,張勇.基于粒子群算法的應(yīng)急物流配送車輛調(diào)度研究[J].價值工程,2011,(34):9-10.

[2]王惠敏,劉剛.基于模擬退火遺傳算法的車輛調(diào)度優(yōu)化[J].微計算機信息,2010,26(11):232-233.

[3]Steinbrunn M,Moerkotte G,Kemper A.Heuristic and Ran2 domized Optimization for the Join Ordering Problem[J].The VLDB Journal,1997,6(3):8-17.

[4]郎茂祥.裝卸混合車輛路徑問題的模擬退火算法研究[J].系統(tǒng)工程學(xué)報,2005,20(5):485-491.

Study on Emergency Logistics Vehicle Dispatching Based on Simulated Annealing Algorithm

Tang Chong
(Student Brigade,Military Transportation Academy,Tianjin 300161,China)

In this paper,in view of the prominent characteristics of emergency logistics,we discussed the optimization of the dispatching route of the emergency logistics vehicles,built the emergency logistics vehicle dispatching model with unilateral time window and designed the simulated annealing algorithm for its solution.

simulatedannealing algorithm;emergency logistics;vehicle dispatching

F252.14;F224.0;U492.3+12

A

1005-152X(2017)01-0114-03

10.3969/j.issn.1005-152X.2017.01.024

2016-12-06

唐沖，男，四川成都人，軍事交通學(xué)院學(xué)生，研究方向：汽車指揮。