基于蟻群算法的應(yīng)急物流配送車輛調(diào)度研究

張?jiān)ＨA　潘　郁

摘要：以車輛配送問題為背景，運(yùn)用了蟻群算法來求解應(yīng)急物流配送車輛調(diào)度模型。在帶有時(shí)間窗的基礎(chǔ)上考慮應(yīng)急系統(tǒng)各節(jié)點(diǎn)的運(yùn)輸距離和費(fèi)用構(gòu)造模型。根據(jù)模型的特點(diǎn)，設(shè)計(jì)了蟻群算法求解方法，并針對(duì)螞蟻路徑選擇做了改進(jìn)性分析。實(shí)例研究結(jié)果表明，蟻群算法在應(yīng)急物流配送車輛調(diào)度問題中具有合理性、可行性和有效性。

關(guān)鍵詞：應(yīng)急管理；物流調(diào)度；蟻群算法

中圖分類號(hào)：F224文獻(xiàn)標(biāo)識(shí)碼：A

Abstract: Taking the vehicle routing problem（VRP）as background, an emergency logistics distribution VRP model is established, which is solved by ant colony algorithm and considering distribution distance and cost when transport between every two spots on basis of time windows. In the light of the characteristic of the model, the solving procedure based on ant colony algorithm is designed and the improved analysis is been done to aim at ant choosing route. Results of example's researching show the rationality, the feasibility and the validity of using ant colony algorithm here.

Key words: emergency management; logistics distribution; ant colony algorithm

0引言

近些年無(wú)論是自然災(zāi)害還是各種事故災(zāi)害，公共災(zāi)害等各類突發(fā)事件爆發(fā)頻繁[1]，而且規(guī)模都很大。突發(fā)性重大自然災(zāi)害[2]和公共衛(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)[3]。根據(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)度模型，用蟻群算法進(jìn)行優(yōu)化車輛的配送路徑。并通過對(duì)某區(qū)域的實(shí)際應(yīng)用，驗(yàn)證了本文提出的模型、算法的合理性。

1數(shù)學(xué)模型

本文討論的是有時(shí)間窗[4]的車輛調(diào)度優(yōu)化問題，假設(shè)救災(zāi)點(diǎn)與各受災(zāi)地點(diǎn)、各受災(zāi)地點(diǎn)之間的運(yùn)輸距離作為已知量。每個(gè)受災(zāi)地點(diǎn)對(duì)救災(zāi)物資的需求是必須在規(guī)定時(shí)間送到。所有的受災(zāi)地點(diǎn)的需求，在物資數(shù)量方面和運(yùn)輸時(shí)間方面都能夠得到滿足；同時(shí)單個(gè)需求節(jié)點(diǎn)的需求量小于單車最大載重量。路網(wǎng)為完全網(wǎng)絡(luò)，即所有節(jié)點(diǎn)之間都有線路連通。車輛所在車場(chǎng)到物資儲(chǔ)備中心的距離忽略不計(jì)。在上述條件下指派運(yùn)輸車輛以期達(dá)到總的運(yùn)輸距離最短，從而降低應(yīng)急物流的運(yùn)輸成本。

應(yīng)急物流配送車輛調(diào)度模型為：

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

在研究調(diào)度問題中，爬山法、遺傳算法和模擬退火法取得了一定的成果，但是由文獻(xiàn)[5]比較結(jié)果顯示蟻群算法的計(jì)算結(jié)果明顯優(yōu)于其他三種。因此本文采用了蟻群算法解決應(yīng)急物流配送車輛調(diào)度問題。蟻群算法是通過信息素傳遞來選擇路徑，具有較高的計(jì)算效率和穩(wěn)定性與傳統(tǒng)算法相比能夠很好地解決連通圖結(jié)構(gòu)的問題。

3實(shí)例分析

為了考察上述模型的性質(zhì)和算法的效果，根據(jù)上述模型的條件選用某地區(qū)所測(cè)算的原始數(shù)據(jù)為依據(jù)進(jìn)行分析。

具體描述如下：

運(yùn)用本文的蟻群算法對(duì)上述問題進(jìn)行求解。以matlab7.0為工具，在p-4機(jī)上運(yùn)算，參數(shù)設(shè)置：α、β、Q、τ0根據(jù)實(shí)驗(yàn)方法確定其最優(yōu)組合選為α=1；β=3；Q=100；τ0=0.000001；ρ服從0,1分布因此隨機(jī)選取為ρ

=0.5。最終的應(yīng)急物流車輛調(diào)度情況如表3。

4結(jié)論

本文通過蟻群算法對(duì)目標(biāo)函數(shù)進(jìn)行了優(yōu)化求解，對(duì)于應(yīng)急物流的配送車輛調(diào)度進(jìn)行了優(yōu)化取得良好的結(jié)果。不過進(jìn)一步地研究方向還需考慮多個(gè)救災(zāi)物資儲(chǔ)備中心，受災(zāi)點(diǎn)等待受災(zāi)的損失費(fèi)用[7]等因素。因此本文的研究和結(jié)論也為在應(yīng)急物流配送車輛調(diào)度的更深入研究提供了思路。

參考文獻(xiàn)：

[1]Megumi Kano, Linda B. Bourque. Correlates of School Disaster Preparedness: Main Effects of Funding and Coordinator Role[J]. Natural Hazards, 2008,9(49):49-59.

[2]Michael K. Lindell, Carla S. Prater, Walter Gillis Peacock. Organizational Communication and Decision Making for Hurricane Emergencies[J]. Natural Hazards, 2007,3(8):50-60.

[3] 錢曉龍，唐立新，劉文新. 動(dòng)態(tài)調(diào)度研究方法綜述[J]. 控制與決策，2001,2(16):141-145.

[4] 鐘石泉，賀國(guó)光. 有時(shí)間窗約束車輛調(diào)度優(yōu)化的一種禁忌算法[J]. 系統(tǒng)工程理論方法應(yīng)用，2005,6(14):522-526.

[5] 劉志碩，申金升，柴躍廷. 基于自適應(yīng)蟻群算法的車輛路徑問題研究[J]. 控制與決策，2005,5(20):562-566.

[6] 甄彤，張秋聞，馬志. 基于改進(jìn)蟻群算法的糧食物流調(diào)度研究[J]. 河南工業(yè)大學(xué)學(xué)報(bào)，2008,3(29):62-65.

[7] 潘郁，余佳，達(dá)慶利. 基于粒子群算法的連續(xù)性消耗應(yīng)急資源調(diào)度[J]. 系統(tǒng)工程學(xué)報(bào)，2007,5(22):556-560.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文