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