物流運輸成本在物流總成本中占有很大比重,合理安排車輛路線,滿足用戶需求對企業(yè)有重要意義。車輛路徑問題是運籌優(yōu)化領(lǐng)域的熱點研究問題,多時間窗車輛路徑問題是對車輛路徑問題的擴展。文中以總成本最小為目標,建立了多時間窗車輛路徑問題的一般數(shù)學模型,針對蟻群算法在求解時容易陷入局部最優(yōu)解和收斂速度慢的問題,改進轉(zhuǎn)移概率公式,采用鄰域搜索策略提高解的質(zhì)量,借鑒模擬退火算法的思想對信息素進行更新,提高算法的尋優(yōu)能力,加快收斂速度。實驗結(jié)果表明,改進后的蟻群算法可以有效求得最優(yōu)解,降低物流運輸成本。相比其他算法,改進后的蟻群算法求解精確度高,收斂速度快,在求解多時間窗車輛路徑問題上有著較好的性能。 

【文章來源】：計算機技術(shù)與發(fā)展. 2019,29(01)

【文章頁數(shù)】：4 頁

【部分圖文】：

路線圖1

均已訪問完畢，則k=k+1，轉(zhuǎn)至步驟2;如果所有螞蟻遍歷完畢，找出當前最優(yōu)解，按照鄰域搜索策略進行可行解的優(yōu)化，然后根據(jù)更新公式更新信息素;n=n+1，如果n＜N，轉(zhuǎn)至步驟2;(6)輸出結(jié)果，退出程序。3仿真實驗多時間窗車輛路徑問題尚無標準的測試數(shù)據(jù)，該算例數(shù)據(jù)取自文獻［11］，不在此一一列舉。改進蟻群算法的參數(shù)設(shè)置為:種群規(guī)模100，迭代次數(shù)200，初始信息素為1，α=1，β=2，ε=1，ρ=0．1，T=1000，r=0.9。改進蟻群算法求得的最優(yōu)解為2156．8，共需要4輛車完成配送任務(wù)，路線如圖1、2和表1所示。圖1路線圖1圖2路線圖2表1車輛路線表車輛路線裝載率/%10→1→4→3→6→2→5→06020→7→9→10→8→11→072．53a0→20→19→15→18→0953b0→18→15→19→20→09540→17→16→13→14→12→095·401·計算機技術(shù)與發(fā)展第29卷

821616．69標準蟻群算法2168．9220624．58模擬退火算法2168．92470．1128．56禁忌搜索算法2168．92323．3146．86從表2中可以看出，在20次實驗中，改進蟻群算法求得的最優(yōu)解為2156．8，平均每次求得的最優(yōu)解為2161，標準差為6．69，三項指標均優(yōu)于其他三種算法。標準蟻群算、模擬退火算法和禁忌搜索算法均停留在某個局部最優(yōu)解上，說明改進蟻群算法在跳出局部最優(yōu)解方面具有良好的性能，而且算法求解的標準差較小，結(jié)果相對穩(wěn)定，而未改進的標準蟻群算法、模擬退火算法和禁忌搜索算法在求解過程中的穩(wěn)定性較差。從圖3可以看出，模擬退火算法和禁忌搜索算法在迭代過程中變化幅度大，穩(wěn)定性差，而且求解質(zhì)量不高，而改進蟻群算法在求解問題時速度較快，穩(wěn)定性好，求解質(zhì)量高于其他三種算法。圖3算法迭代對比圖4結(jié)束語車輛路徑問題屬于NP難題，構(gòu)造高質(zhì)量的啟發(fā)式算法是很多學者的研究方向。針對多時間窗車輛路徑問題建立了一般數(shù)學模型，改進蟻群算法進行求解，和其他算法求得的結(jié)果進行比對分析。改進后的蟻群算法在求解多時間窗車輛路徑問題上有著較好的性能，是求解多時間窗車輛路徑問題的較好途徑。參考文獻:［1］DANTZIGG，ＲAMSEＲJ．Thetruckdispatchingproblem［J］．ManagementScience，1959，6(1):80－91．［2］楊宇棟，朗茂祥，胡思繼．有時間窗車輛路徑問題的模型及其改進模擬退火算法研究［J］．管理工程學報，2006，20(3):104－107．［3］劉志碩，柴躍廷，申金升．蟻群算法及其在有硬時間窗的車輛路徑問題中的應用［J］．計算機集成制造系統(tǒng)，2006，12(4):596－602．［4］何小鋒，馬良．帶時間窗車輛路徑問題的量子蟻群算法［J］．系統(tǒng)工程理論與實踐，2013，33(5):1255－1261．［5］BELHAIZAS，HANSENP，

【參考文獻】：
期刊論文
[1]多模糊時間窗車輛路徑問題的建模及求解[J]. 閆芳,王媛媛.  交通運輸系統(tǒng)工程與信息. 2016(06)
[2]多時間窗車輛路徑問題的智能水滴算法[J]. 李珍萍,趙菲,劉洪偉.  運籌與管理. 2015(06)
[3]基于蟻群模擬退火算法的云環(huán)境任務(wù)調(diào)度[J]. 張浩榮,陳平華,熊建斌.  廣東工業(yè)大學學報. 2014(03)
[4]帶時間窗車輛路徑問題的量子蟻群算法[J]. 何小鋒,馬良.  系統(tǒng)工程理論與實踐. 2013(05)
[5]基于協(xié)同自適應禁忌的多時窗VRP算法實現(xiàn)[J]. 朱玲玲,楊愛琴,吳寬仁.  計算機應用研究. 2012(12)
[6]允許分割配送的多時間窗車輛調(diào)度問題的改進蟻群算法求解[J]. 馬華偉,葉浩然,夏維.  中國管理科學. 2012(S1)
[7]多時間窗車輛路徑問題的數(shù)學模型及算法[J]. 黃秋愛,李珍萍.  物流技術(shù). 2012(13)
[8]求解有時間窗的車輛路徑問題的混合蟻群算法[J]. 丁秋雷,胡祥培,李永先.  系統(tǒng)工程理論與實踐. 2007(10)
[9]有時間窗車輛路徑問題的模型及其改進模擬退火算法研究[J]. 楊宇棟,朗茂祥,胡思繼.  管理工程學報. 2006(03)
[10]蟻群算法及其在有硬時間窗的車輛路徑問題中的應用[J]. 劉志碩,柴躍廷,申金升.  計算機集成制造系統(tǒng). 2006(04)



本文編號：3471825