有時間窗的車輛路徑問題的改進ＭＡＸ－ＭＩＮ蟻群算法

[摘要] MAX—MIN蟻群算法是一種改進蟻群算法，文本構造了求解VRPTW的最大最小蟻群算法，將仿真結果與其他經典算法進行比較，結果證明該算法性能優良。

[關鍵詞] MAX-MIN蟻群算法時間窗車輛路徑問題優化

一、VRPTW模型的建立

帶有時間窗口的車輛路徑問題是典型的多目標組合優化NP-hard問題，因此需要通過合理的構造數學模型來安排車輛配送路線，達到提高配送效率同時又能夠產生巨大的社會和經濟效益的目的。

VRPTW包括一些客戶和倉庫，每個客戶有一定的需求和時間窗口。每個客戶只能由一輛車一次服務完成，還要保證每個客戶只能被精確的訪問一次，同時不能違背時間窗口約束。其目的是要找到一個可行解使得車輛數最少并且總行程最小。

二、最大最小蟻群算法

為克服在Ant．Q中可能出現的停滯現象，Thomas Stutzle等提出了MMAS算法。該算法具有比基本蟻群算法更貪婪的搜索模式，其主要的改進有以下幾點:首先，MMAS在運行期間更多的利用最優解信息，即每次迭代后僅允許一只最優的螞蟻增加信息素。其次，該算法限定了信息素濃度的上下限，有效避免了在搜索中過早收斂于非全局最優解。

將m只螞蟻隨機放到n個客戶中，為t時刻支路(i，j)上的信息素強度，每只螞蟻都可認為是根據狀態轉移策略來選擇下一個客戶，并遵循信息素全局更新規則和信息素限制規則。

1.狀態轉移策略

針對VRPTW自身的特點，我們定義其狀態轉移概率為:

其中h∈allowedk={n-tabuk};ηij為啟發信息;α(α≥0)代表信息素的權重，β(β≥0)代表啟發信息的權重;μij=di0+dj0-dij為節約值; δij為緊迫性因子。

2.信息素更新規則

在MMAS中，只允許其中的最優路徑更新信息素，其更新規則為:

其中，為該次迭代sib或全局最優路徑sgb的目標函數。

3.信息素限制規則

為了降低算法搜索中的早期停滯問題，該算法限定了信息素濃度允許值的上下限，即

。若，則;若，則。

在搜索過程中，當得到最優解時，按下式便得到一個動態變化的:

為了提高算法的收斂性，我們一般先給定一個Pbest，然后根據下式來選定一個 ：

三、算例分析及結論

設某倉庫使用完全相同的車輛把貨物運往8個客戶，車輛的載重能力為8噸，車速為50公里每小時，客戶所需貨物的重量，服務時間及訪問時間窗口的具體要求由Tab.1給出。客戶之間的距離如Tab.2所示。問題是尋找合適的路徑，使得車輛運行總成本最小。

實驗開始，將每個客戶都放置一只螞蟻，螞蟻的個數與客戶數相同。取α=1，β=3，γ=3，λ=1，ρ=0.8，θ=10。采用本文的算法，得到的最優解為:第一輛車：0-2-7-4-0;第二輛車：0-3-1-0;第三輛車：0-8-5-6-0。

將求解的結果與Clarke-Wright算法和遺傳算法比較，從Tab.3中可以看出MMAS不失為帶時間窗車輛路徑問題的一個較優解。

四、結語

本文將MMAS算法應用于VRPTW問題中，充分發揮了其超強的貪婪搜索能力，獲得了較為滿意的實驗效果。這次成功嘗試再次表明了該算法在組合優化領域中是具有強大競爭力的，同時也證明了用這種方法解決具有一定的理論參考價值和實際意義。

參考文獻:

[1]吳啟迪汪 鐳:智能蟻群算法及應用[M].上海科技出版社，2004，4

[2]劉云忠宣慧玉:動態蟻群算法在帶時間窗車輛路徑問題中的應用[J].中國科學工程，2005，12(7):35－40

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