唐連生，程文明，張則強，鐘斌，梁劍
（西南交通大學機械工程研究所，成都 610031）
摘要：針對基本蟻群算法收斂速度慢、易陷于局部最優等缺陷，提出了一種改進蟻群算法。通過車輛的滿載率調整搜索路徑上的啟發信息強度變化，對有效路徑采取信息素的局部更新和全局更新策略，并對子可行解進行3-opt優化，在實現局部最優的基礎上保證可行解的全局最優。通過對22城市車輛路徑實例的仿真，仿真結果表明，改進型算法性能更優，同基本蟻群相比該算法的收斂速度提高近50%，效果顯著，該算法能在更短時間內求得大規模車輛路徑問題滿意最優解。
關鍵字：物流，VRP，蟻群算法，車輛路徑
中國分類號：TP18 文獻標識碼：A
VEHICLE ROUTING SIMULATION RESEARCH BASED ON AN IMPROVED ANT COLONY ALGORITHM
Tang Liansheng, Cheng Wenming, Zhang Zeqiang, Zhong Bin, Liang jian
(Research Institute of Mechanical Engineering, Southwest Jiaotong University, Chengdu, 610031)
ABSTRACT：An improved ant colony algorithm is proposed aiming at the basic ant colony algorithms convergence slow and be prone to plunge a partial basis. The inspired route information strength changes according to the search vehicles loaded rate. Both local information and global information are updated on the effective route. Achieving optimal local basis ensures the best possible solution by means of 2-opt optimized algorithm. The example of 22 city vehicle routing is simulated by this algorithm, and it shows that the speed of convergence nearly 50% increased compared with the basic ant algorithm. The algorithm has achieved significant results, and less time by the algorithm to solve large-scale vehicle routing problems.
KEYWORDS：Logistics; VRP; Ant colony algorithm; Vehicle routing
1 引言
車輛路徑問題（Vehicle Routing Problem，簡稱VRP）來源于交通運輸，由Dantzig[1]于1959年提出，它是組合優化問題中一個典型的NP-hard問題，用于研究亞特蘭大煉油廠向各加油站投送汽油的運輸路徑優化問題，并迅速成為運籌學和組合優化領域的前沿和研究熱點，吸引眾多學者對其進行研究。通常用圖G=(V,E)用來描述該問題[2]，在圖G=(V，E)中，V={0,1,2,…,n}，E={(i，j)，i≠j，i，j∈V}，節點1表示倉庫（depot），其它節點為客戶。每個客戶的需求為qi，邊(i，j)對應的距離或運輸時間或成本為Cij，所有車輛運輸能力為Q，車輛從倉庫出發，完成運輸任務后回到倉庫，每個顧客只能接受一次服務，問題的目標函數通常是車輛數和運輸成本最小化。由于該問題的復雜性，尋找到一種高效、精確的算法的可能性微乎其微，人們開始嘗試利用仿生智能算法求解。
蟻群算法是一種新的群體智能啟發式優化方法，適合求解車輛路徑等組合優化問題。最初由意大利學者Dorigo[3][4]等人提出用于解決旅行商問題，隨著研究的不斷深入，已經陸續滲透到電子、通訊、車間調度等工程領域。John E. Bell[5]將螞蟻系統優化的亞啟發式方法應用到VRP問題的求解。Silvia[6]探討了在車輛容量限制條件下的VRP問題，在亞啟發式算法基礎上提出了CVRP 的蟻群算法，并取得較好的效果。劉志勛[7]等在分析VRP和TSP區別基礎上，構造了求解VRP的自適應蟻群算法，提出了近似解可行化的解決策略。蟻群算法由于基本蟻群算法收斂速度慢且易陷于局部最優，很難在較短時間內對大規模VRP求得滿意最優解，且該算法極易出現停滯現象，因此有必要對
算法進行改進。
全文下載
基于改進蟻群算法的車輛路徑問題研究.doc
