基于蟻群算法的緊急物流配送路徑優(yōu)化設(shè)計(jì)

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

一、引言

近些年無論是自然災(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)度問題研究還很少。鑒于物流調(diào)度的研究方法，其中有傳統(tǒng)的方法，比如，數(shù)學(xué)規(guī)劃，分支定界法等。不過這些方法只能基于某些簡(jiǎn)化的假設(shè)因而不能適應(yīng)實(shí)際的需要.智能調(diào)度方法，如專家系統(tǒng)、神經(jīng)網(wǎng)絡(luò)和遺傳算法在使用中盡管有優(yōu)點(diǎn)，但也有明顯的缺點(diǎn)。根據(jù)以上問題，本文將結(jié)合應(yīng)急物流的配送車輛優(yōu)化調(diào)度問題，根據(jù)應(yīng)急物流配送的突出特點(diǎn)，對(duì)應(yīng)急物流配送車輛調(diào)度路線優(yōu)化進(jìn)行探討，建立了應(yīng)急物流配送車輛調(diào)度模型，用蟻群算法對(duì)車輛的配送路徑進(jìn)行優(yōu)化。

二、問題描述

物流配送路徑優(yōu)化是指對(duì)一系列裝貨點(diǎn)(或卸貨點(diǎn))，組織適當(dāng)?shù)男熊嚲€路，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、發(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)化問題描述，假設(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)說明:

(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)算法，它通過模擬自然界蟻群從巢穴到食物源的最短路徑的覓食過程來求解一些NP難題。蟻群算法是一種通用型隨機(jī)優(yōu)化算法，對(duì)問題的求解沒有苛刻的限制使用條件，可以在非常困難的條件下搜索到組合問題的最優(yōu)解或較優(yōu)解，在很多經(jīng)典的組合優(yōu)化領(lǐng)域上都有較好的應(yīng)用，如旅行商問題(TSP)和非對(duì)稱旅行商問題(ATSP)、作業(yè)車間調(diào)度問題(JSP)。蟻群算法是通過信息素的積累和更新來尋求最優(yōu)解。螞蟻有能力在沒有任何提示下找到從巢穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇。其根本原因是螞蟻在尋找食物源時(shí)，在其走過的路上釋放一種特殊的分泌物——信息素，后來的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上該物質(zhì)的強(qiáng)度成正比。當(dāng)它們碰到一個(gè)沒有走過的路口時(shí)，就隨機(jī)地挑選一條路徑前行，與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的信息素濃度越低。當(dāng)后來的螞蟻再次碰到這個(gè)路口時(shí)，選擇信息素較高路徑的概率就會(huì)相對(duì)較大。而當(dāng)一定路徑上通過螞蟻越來越多時(shí)，其留下的信息素軌跡也越來越多，后來的螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(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)過支路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)度問題中，爬山法、遺傳算法等取得了一定的成果，但是由文獻(xiàn)比較結(jié)果顯示蟻群算法的計(jì)算結(jié)果明顯優(yōu)于其他方法。因此本文采用了蟻群算法解決應(yīng)急物流配送車輛調(diào)度問題。

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

(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)過程中，只允許移向未到達(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已走過的節(jié)點(diǎn)。當(dāng)一個(gè)周期結(jié)束，進(jìn)入t+1時(shí)刻，對(duì)各路徑上的信息進(jìn)行調(diào)整，即:

(12)

(13)

螞蟻K在本次循環(huán)中經(jīng)過路徑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é)

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

參考文獻(xiàn):

[1]謝秉磊 李 軍:《有時(shí)間窗的非滿載車輛調(diào)度問題的遺傳算法》[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