發(fā)布時(shí)間：2021-11-02 09:55

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

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

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

【部分圖文】：

路線圖1

均已訪問完畢，則k=k+1，轉(zhuǎn)至步驟2;如果所有螞蟻遍歷完畢，找出當(dāng)前最優(yōu)解，按照鄰域搜索策略進(jìn)行可行解的優(yōu)化，然后根據(jù)更新公式更新信息素;n=n+1，如果n＜N，轉(zhuǎn)至步驟2;(6)輸出結(jié)果，退出程序。3仿真實(shí)驗(yàn)多時(shí)間窗車輛路徑問題尚無標(biāo)準(zhǔn)的測(cè)試數(shù)據(jù)，該算例數(shù)據(jù)取自文獻(xiàn)［11］，不在此一一列舉。改進(jìn)蟻群算法的參數(shù)設(shè)置為:種群規(guī)模100，迭代次數(shù)200，初始信息素為1，α=1，β=2，ε=1，ρ=0．1，T=1000，r=0.9。改進(jìn)蟻群算法求得的最優(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·計(jì)算機(jī)技術(shù)與發(fā)展第29卷

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

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



本文編號(hào)：3471825