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

唐沖

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

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

唐沖

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

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

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

1 引言

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

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

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

2 單邊時(shí)間窗VRP模型

2.1 問(wèn)題描述

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

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

2.2 模型建立

通過(guò)分析上述條件，可得相鄰兩節(jié)點(diǎn)之間的物資達(dá)到時(shí)間滿(mǎn)足：

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

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

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

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

3 單邊時(shí)間窗VRP的模擬退火算法

3.1 模擬退火算法的原理

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

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

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

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

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

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

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

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

4 實(shí)例應(yīng)用

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

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

首先，通過(guò)計(jì)算可得運(yùn)送路徑為3條，即3輛運(yùn)輸車(chē)便可滿(mǎn)足運(yùn)輸需求。

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。通過(guò)MATLAB編程，隨機(jī)求解100次，可得結(jié)果見(jiàn)表2。

表2 SAA計(jì)算結(jié)果

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

5 結(jié)束語(yǔ)

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

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

[2]王惠敏,劉剛.基于模擬退火遺傳算法的車(chē)輛調(diào)度優(yōu)化[J].微計(jì)算機(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]郎茂祥.裝卸混合車(chē)輛路徑問(wèn)題的模擬退火算法研究[J].系統(tǒng)工程學(xué)報(bào),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é)生，研究方向：汽車(chē)指揮。