張裕華　潘　郁

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

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

中圖分類號：F224文獻標(biāo)識碼：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引言

近些年無論是自然災(zāi)害還是各種事故災(zāi)害，公共災(zāi)害等各類突發(fā)事件爆發(fā)頻繁[1]，而且規(guī)模都很大。突發(fā)性重大自然災(zāi)害[2]和公共衛(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)點，但也有明顯的缺點[3]。根據(jù)以上問題，本文將結(jié)合應(yīng)急物流的配送車輛優(yōu)化調(diào)度問題，根據(jù)應(yīng)急物流配送的突出特點，對應(yīng)急物流配送車輛調(diào)度路線優(yōu)化進行研究，建立了應(yīng)急物流配送車輛調(diào)度模型，用蟻群算法進行優(yōu)化車輛的配送路徑。并通過對某區(qū)域的實際應(yīng)用，驗證了本文提出的模型、算法的合理性。

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

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

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

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

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

3實例分析

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

具體描述如下：

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

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

4結(jié)論

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

參考文獻：

[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] 錢曉龍，唐立新，劉文新. 動態(tài)調(diào)度研究方法綜述[J]. 控制與決策，2001,2(16):141-145.

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

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

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

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

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