具有時間窗約束累積性車輛路徑問題的禁忌搜索優化算法

作者：董蕊,劉冉,江志斌,任盼

摘要：基于對中國實際物流運輸中成本計算方法的研究,考慮到我國高速公路系統計價方式的特殊性,提出了具有時間窗約束的累積性車輛路徑問題。以降低實際車輛運輸成本為目標,設計了新型的禁忌搜索算法對問題進行有效求解;算法中嵌入多種鄰域搜索方法,允許同時在可行和不可行解空間內進行鄰域搜索,同時采用Nagata提出的時間窗違反量計算方法[1-2]對解的時間窗約束違反進行評估。針對提出的新型問題的數值試驗證明了所采用的時間窗違反量計算方法的時間節約性和有效性;同時由于該問題可以覆蓋傳統的累積性車輛路徑問題,對后者的數值實驗以及與其他優化算法的對比驗證了所提出算法的優良求解效果。

發文機構：上海交通大學工業工程與管理系

關鍵詞：累積性成本車輛路徑時間窗禁忌搜索cumulative costvehicle routing problemtime windowTabu search

分類號： TP301[自動化與計算機技術—計算機系統結構][自動化與計算機技術—計算機科學與技術]