多目標帶時間窗的車輛路徑問題的單親遺傳混合蟻群算法

劉　云，張惠珍

(上海理工大學　管理學院，上海　200093)

多目標帶時間窗的車輛路徑問題的單親遺傳混合蟻群算法

劉云，張惠珍

(上海理工大學管理學院，上海200093)

摘要：考慮具有最大等待時間、最大運輸時間限制且帶時間窗的車輛路徑問題，建立了以車輛行駛路徑最短和使用車輛數最小為目標的數學模型。將單親遺傳算法和基本蟻群算法相結合，使其優勢互補，并利用單親遺傳算法的特點，構建出兩種求解該問題的單親遺傳混合蟻群算法，分別為：單點單親遺傳混合蟻群算法和多點單親遺傳混合蟻群算法。測試算例的結果表明：求解多目標帶時間窗的車輛路徑問題時，與基本蟻群算法相比，單親遺傳混合蟻群算法具有計算效率高、收斂性好等優點，尤其單點單親遺傳混合蟻群算法不僅具有較好的計算性能，而且具有較高的穩定性。

關鍵詞：交通工程；車輛路徑問題；單親遺傳混合蟻群算法；多目標；時間窗

0引言

帶時間窗的車輛路徑問題[1](Vehicle Routing Problem with Time Windows, VRPTW)最早由Savelsbergh提出，是在車輛路徑問題(Vehicle Routing Problem, VRP)的基礎上增加了客戶接受配送服務的時間窗要求，較VRP更貼近實際生活。VRPTW已被證實是一個NP難問題，當問題規模較大時，精確算法難以求出其最優解，因此，國內外很多學者利用智能啟發式算法來尋找其滿意解。常見的求解VRPTW的智能啟發式算法有遺傳算法[2-3]、蟻群算法[4-7]、模擬退火算法[8-9]、粒子群算法[10-11]等。然而，迄今為止，這些智能啟發式算法大都被用于求解單目標的車輛路徑問題，在多目標車輛路徑優化問題中涉及的并不多。……