[摘 要] 本文將結(jié)合應(yīng)急物流的配送車輛優(yōu)化調(diào)度問題，根據(jù)應(yīng)急物流配送的突出特點，對應(yīng)急物流配送車輛調(diào)度路線優(yōu)化進行探討，建立了應(yīng)急物流配送車輛調(diào)度模型，用蟻群算法對車輛的配送路徑進行優(yōu)化。

一、引言

近些年無論是自然災(zāi)害還是各種事故災(zāi)害，公共災(zāi)害等各類突發(fā)事件爆發(fā)頻繁，而且規(guī)模都很大。突發(fā)性重大自然災(zāi)害和公共衛(wèi)生事件造成巨大的人員傷亡和財產(chǎn)損失，必然需要大量的應(yīng)急物資，以解決傷者救助、衛(wèi)生防疫、恢復(fù)生產(chǎn)等，否則受災(zāi)面積、人員、損失將會擴大。因此選擇距離最短、費用最少和時間最快的配送路徑顯得格外重要。目前國內(nèi)關(guān)于物流調(diào)度方面作了一些研究，但是關(guān)于應(yīng)急物流配送車輛調(diào)度問題研究還很少。鑒于物流調(diào)度的研究方法，其中有傳統(tǒng)的方法，比如，數(shù)學(xué)規(guī)劃，分支定界法等。不過這些方法只能基于某些簡化的假設(shè)因而不能適應(yīng)實際的需要.智能調(diào)度方法，如專家系統(tǒng)、神經(jīng)網(wǎng)絡(luò)和遺傳算法在使用中盡管有優(yōu)點，但也有明顯的缺點。根據(jù)以上問題，本文將結(jié)合應(yīng)急物流的配送車輛優(yōu)化調(diào)度問題，根據(jù)應(yīng)急物流配送的突出特點，對應(yīng)急物流配送車輛調(diào)度路線優(yōu)化進行探討，建立了應(yīng)急物流配送車輛調(diào)度模型，用蟻群算法對車輛的配送路徑進行優(yōu)化。

二、問題描述

物流配送路徑優(yōu)化是指對一系列裝貨點(或卸貨點)，組織適當(dāng)?shù)男熊嚲€路，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等)下，達到一定的目標，使總代價最小(如路程最短、費用最少、時間盡量少、使用車輛盡量少等)，并且同時滿足以下條件及假設(shè):各個需求點的位置和需求量為已知，尋找一個優(yōu)秀的配送方案，使得總代價最小。

1.約束條件

(1)所有節(jié)點之間都有路線相通。(2)各救災(zāi)點與各受災(zāi)地點、各受災(zāi)地點之間的運輸距離作為已知量。(3)每個受災(zāi)地點對救災(zāi)物資的需求是必須在規(guī)定時間送到。(4)所有的受災(zāi)地點的需求，在物資數(shù)量方面和運輸時間方面都能夠得到滿足。(5)單個需求節(jié)點的需求量小于單車車容量。(6)為簡化問題描述，假設(shè)車輛所在車場到物資儲備中心的距離忽略不計。

2.數(shù)學(xué)模型

在上述條件下指派運輸車輛以期達到總的運輸距離最短，從而降低應(yīng)急物流的運輸成本。應(yīng)急物流配送車輛調(diào)度模型如下。

目標函數(shù):

(1)

Min k(2)

約束條件:

i=0，1，2，…，n(3)

RTi≤LTii=0，1，2，…，n (4)

i=0，1，2，…，n (5)

i，j=0，1，2，…，n (6)

i，j=0，1，2，…，n (7)

X=(xik)∈D (8)

k≤n(9)

公式中符號說明:

(1)dij表示為從節(jié)點i到節(jié)點j的運輸距離，當(dāng)i，j=0時表示該節(jié)點為救災(zāi)點，否則為受災(zāi)點。

(2)。

(3)k表示車輛數(shù)量;q表示單車車容量lgi(i≠0)表示第i個受災(zāi)節(jié)點對于救災(zāi)物資的需求量;。

(4)RTi表示車輛到達i點的時刻;LTi表示最遲允許車輛到達時刻。

三、蟻群算法原理

蟻群算法是意大利學(xué)者M·Dorigo等提出的一種仿生尋優(yōu)算法，它通過模擬自然界蟻群從巢穴到食物源的最短路徑的覓食過程來求解一些NP難題。蟻群算法是一種通用型隨機優(yōu)化算法，對問題的求解沒有苛刻的限制使用條件，可以在非常困難的條件下搜索到組合問題的最優(yōu)解或較優(yōu)解，在很多經(jīng)典的組合優(yōu)化領(lǐng)域上都有較好的應(yīng)用，如旅行商問題(TSP)和非對稱旅行商問題(ATSP)、作業(yè)車間調(diào)度問題(JSP)。蟻群算法是通過信息素的積累和更新來尋求最優(yōu)解。螞蟻有能力在沒有任何提示下找到從巢穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇。其根本原因是螞蟻在尋找食物源時，在其走過的路上釋放一種特殊的分泌物——信息素，后來的螞蟻選擇該路徑的概率與當(dāng)時這條路徑上該物質(zhì)的強度成正比。當(dāng)它們碰到一個沒有走過的路口時，就隨機地挑選一條路徑前行，與此同時釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的信息素濃度越低。當(dāng)后來的螞蟻再次碰到這個路口時，選擇信息素較高路徑的概率就會相對較大。而當(dāng)一定路徑上通過螞蟻越來越多時，其留下的信息素軌跡也越來越多，后來的螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強度。而強度大的信息素會吸引更多的螞蟻，從而形成一種正反饋機制。螞蟻的路徑搜索原理如圖所示，有兩條支路ACB和ADB，支路ACB中節(jié)點A和B各有兩只螞蟻，其中螞蟻1、2由A向B行進，而3、4則由B向A行進。假設(shè)螞蟻速度相同，當(dāng)螞蟻2和螞蟻4經(jīng)過支路ADB分別到達節(jié)點B和A，而螞蟻1和3還在支路ACB的途中。顯然，支路ADB留下的信息素的痕跡濃度要高于支路ACB上的信息素濃度，所以當(dāng)再有螞蟻到達點A和B時，它們選擇支路ADB的概率就會更大，從而增加支路ADB上的信息素痕跡的濃度，形成正反饋，這樣螞蟻可以容易找到一條到食物源的最短路徑。

四、蟻群算法優(yōu)化求解

在研究調(diào)度問題中，爬山法、遺傳算法等取得了一定的成果，但是由文獻比較結(jié)果顯示蟻群算法的計算結(jié)果明顯優(yōu)于其他方法。因此本文采用了蟻群算法解決應(yīng)急物流配送車輛調(diào)度問題。

在優(yōu)化求解過程中，我們做如下定義:

(1)m:蟻群中螞蟻的數(shù)量。

(2)ηij路徑ij的能見度。

(3)Γij t時刻在路徑ij上的信息量。

(4)ΔΓijk螞蟻k在本次循環(huán)中留在路徑ij上的信息量。

(5)Pjik螞蟻k在t時刻由位置i轉(zhuǎn)移到位置j的概率。

(6)α:轉(zhuǎn)跡的相對重要性，α≥0。

(7)β:能見度的相對重要性，β≥0。

(8)ρ:信息數(shù)的持久性，0≤ρ≤1，1-ρ表示信息素的衰減度。

(9)假設(shè)Γij(0)=C，C為一常量。

(10)螞蟻k在運動過程中，只允許移向未到達的受災(zāi)點或者是救災(zāi)物資儲備中心，并且根據(jù)當(dāng)前所處位置的不同選擇不同路徑。

(11)當(dāng)螞蟻位于救災(zāi)點時:由于救災(zāi)點假設(shè)均滿足車載重量約束，則在這些救災(zāi)點中螞蟻k按照式(10)給出的轉(zhuǎn)移規(guī)則移向受災(zāi)點s;否則隨機產(chǎn)生一個(0，1)間的隨機數(shù)r，若r

其中S表示為:，

S=arg max{[Γ(r，u)]α·[η(r，u)]β}uallowed(10)

Pijk(t)表示為:

(11)

allowedk=[0，1，…，n-1]-tabuk表示t時刻螞蟻k下一步允許選擇的點。在蟻群算法中，我們假設(shè)人工蟻群系統(tǒng)有記憶功能，用tabuk(k=1，2，…，m)記錄螞蟻k已走過的節(jié)點。當(dāng)一個周期結(jié)束，進入t+1時刻，對各路徑上的信息進行調(diào)整，即:

(12)

(13)

螞蟻K在本次循環(huán)中經(jīng)過路徑ij，否則為0(14)

其中Q是常數(shù)，表示螞蟻循環(huán)一周所釋放的總信息量。 表示k只螞蟻在本次循環(huán)中所走路徑的總長度，它體現(xiàn)了全局范圍內(nèi)的最短路徑，能都提高系統(tǒng)搜索的收斂速度。參數(shù)Q、C、α、β、ρ可以用實驗方法確定其最優(yōu)組合。停止條件可以用固定循環(huán)次數(shù)或者當(dāng)進化趨勢不明顯時便停止計算。

五、總結(jié)

蟻群算法是通過信息素傳遞來選擇路徑，具有較好的全局尋優(yōu)能力，收斂速度快和穩(wěn)定性強的優(yōu)點，與傳統(tǒng)算法相比能夠很好地解決連通圖結(jié)構(gòu)的問題。因此，蟻群算法是解決物流配送路徑優(yōu)化問題的一個有效算法。它可以縮短運輸距離與運輸時間，減少客運商服務(wù)成本，提高服務(wù)質(zhì)量。

參考文獻:

[1]謝秉磊 李 軍:《有時間窗的非滿載車輛調(diào)度問題的遺傳算法》[J].《系統(tǒng)工程學(xué)報》2000(3):290～294

[2]趙家俊 于寶琴:《現(xiàn)代物流配送管理》[M].北京大學(xué)出版社，2004:94～99

[3]崔雪麗 馬 良:《有缺貨限制的VRP螞蟻算法研究》[J].《上海理工大學(xué)學(xué)報》2003(1):39～4