唐連生，程文明，張則強，鐘斌，梁劍
（西南交通大學(xué)機械工程研究所，成都 610031）
摘要：針對基本蟻群算法收斂速度慢、易陷于局部最優(yōu)等缺陷，提出了一種改進(jìn)蟻群算法。通過車輛的滿載率調(diào)整搜索路徑上的啟發(fā)信息強度變化，對有效路徑采取信息素的局部更新和全局更新策略，并對子可行解進(jìn)行3-opt優(yōu)化，在實現(xiàn)局部最優(yōu)的基礎(chǔ)上保證可行解的全局最優(yōu)。通過對22城市車輛路徑實例的仿真，仿真結(jié)果表明，改進(jìn)型算法性能更優(yōu)，同基本蟻群相比該算法的收斂速度提高近50%，效果顯著，該算法能在更短時間內(nèi)求得大規(guī)模車輛路徑問題滿意最優(yōu)解。
關(guān)鍵字：物流，VRP，蟻群算法，車輛路徑
中國分類號：TP18 文獻(xiàn)標(biāo)識碼：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年提出，它是組合優(yōu)化問題中一個典型的NP-hard問題，用于研究亞特蘭大煉油廠向各加油站投送汽油的運輸路徑優(yōu)化問題，并迅速成為運籌學(xué)和組合優(yōu)化領(lǐng)域的前沿和研究熱點，吸引眾多學(xué)者對其進(jìn)行研究。通常用圖G=(V,E)用來描述該問題[2]，在圖G=(V，E)中，V={0,1,2,…,n}，E={(i，j)，i≠j，i，j∈V}，節(jié)點1表示倉庫（depot），其它節(jié)點為客戶。每個客戶的需求為qi，邊(i，j)對應(yīng)的距離或運輸時間或成本為Cij，所有車輛運輸能力為Q，車輛從倉庫出發(fā)，完成運輸任務(wù)后回到倉庫，每個顧客只能接受一次服務(wù)，問題的目標(biāo)函數(shù)通常是車輛數(shù)和運輸成本最小化。由于該問題的復(fù)雜性，尋找到一種高效、精確的算法的可能性微乎其微，人們開始嘗試?yán)梅律悄芩惴ㄇ蠼狻?
蟻群算法是一種新的群體智能啟發(fā)式優(yōu)化方法，適合求解車輛路徑等組合優(yōu)化問題。最初由意大利學(xué)者Dorigo[3][4]等人提出用于解決旅行商問題，隨著研究的不斷深入，已經(jīng)陸續(xù)滲透到電子、通訊、車間調(diào)度等工程領(lǐng)域。John E. Bell[5]將螞蟻系統(tǒng)優(yōu)化的亞啟發(fā)式方法應(yīng)用到VRP問題的求解。Silvia[6]探討了在車輛容量限制條件下的VRP問題，在亞啟發(fā)式算法基礎(chǔ)上提出了CVRP 的蟻群算法，并取得較好的效果。劉志勛[7]等在分析VRP和TSP區(qū)別基礎(chǔ)上，構(gòu)造了求解VRP的自適應(yīng)蟻群算法，提出了近似解可行化的解決策略。蟻群算法由于基本蟻群算法收斂速度慢且易陷于局部最優(yōu)，很難在較短時間內(nèi)對大規(guī)模VRP求得滿意最優(yōu)解，且該算法極易出現(xiàn)停滯現(xiàn)象，因此有必要對
算法進(jìn)行改進(jìn)。
全文下載
基于改進(jìn)蟻群算法的車輛路徑問題研究.doc
