基于蟻群算法的應急物流配送車輛調度研究

張裕華　潘　郁

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

關鍵詞：應急管理；物流調度；蟻群算法

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

近些年無論是自然災害還是各種事故災害，公共災害等各類突發事件爆發頻繁[1]，而且規模都很大。突發性重大自然災害[2]和公共衛生事件造成巨大的人員傷亡和財產損失，必然需要大量的應急物資，以解決傷者救助、衛生防疫、恢復生產等，否則受災面積、人員、損失將會擴大。因此選擇距離最短、費用最少和時間最快的配送路徑顯得格外重要。目前國內關于物流調度方面作了一些研究，但是關于應急物流配送車輛調度問題研究還很少。鑒于物流調度的研究方法，其中有傳統的方法，比如，數學規劃，分支定界法等。不過這些方法只能基于某些簡化的假設因而不能適應實際的需要；智能調度方法，如專家系統、神經網絡和遺傳算法在使用中盡管有優點，但也有明顯的缺點[3]。根據以上問題，本文將結合應急物流的配送車輛優化調度問題，根據應急物流配送的突出特點，對應急物流配送車輛調度路線優化進行研究，建立了應急物流配送車輛調度模型，用蟻群算法進行優化車輛的配送路徑。并通過對某區域的實際應用，驗證了本文提出的模型、算法的合理性。

1數學模型

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

應急物流配送車輛調度模型為：

2蟻群算法優化求解

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

3實例分析

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

具體描述如下：

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

=0.5。最終的應急物流車輛調度情況如表3。

4結論

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

參考文獻：

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

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

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

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

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

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