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

一、引言

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

二、問(wèn)題描述

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

1.約束條件

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

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

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

目標(biā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)

公式中符號(hào)說(shuō)明:

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

(2)。

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

(4)RTi表示車輛到達(dá)i點(diǎn)的時(shí)刻;LTi表示最遲允許車輛到達(dá)時(shí)刻。

三、蟻群算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中S表示為:，

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

Pijk(t)表示為:

(11)

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

(12)

(13)

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

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

五、總結(jié)

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

參考文獻(xiàn):

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

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

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