針對城市物流配送系統(tǒng),研究了一類帶時間窗和釋放時間約束的多行程車輛路徑問題。首先,對該運輸調(diào)度問題進行了描述,構(gòu)建了以總配送時長最小化為目標(biāo)的數(shù)學(xué)模型。其次,為了快速獲得問題的滿意解,提出了Beam-PSO優(yōu)化算法。在算法設(shè)計中,結(jié)合該問題的性質(zhì),構(gòu)建了基于隨機鍵的編解碼方法,以克服標(biāo)準(zhǔn)粒子群算法無法直接適用于求解離散問題的不足。同時,設(shè)計了基于Beam search優(yōu)化技術(shù)的局部搜索流程,用于強化算法的優(yōu)化性能。最后,進行了仿真實驗,實驗結(jié)果表明了Beam-PSO優(yōu)化算法的可行性和有效性。 

【文章來源】：計算機工程與科學(xué). 2019,41(10)北大核心CSCD

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

【部分圖文】：

圖２基于ＲＯＶ規(guī)則的隨機鍵編碼轉(zhuǎn)換Ｆｉｇｕｒｅ２ＣｏｄｅｃｏｎｖｅｒｓｉｏｎｏｆＲＯＶ－ｂａｓｅｄｒａｎｄｏｍｋｅｙｓ

次類推，可將Ｄ維實數(shù)數(shù)組映射為１個１～Ｄ的排列數(shù)組。如圖２所示，假設(shè)某一粒子的編碼數(shù)值為（０．６３，０．２５，０．１７，０．４１），依據(jù)ＲＯＶ規(guī)則可將其轉(zhuǎn)化為排列（４，２，１，３）。Ｆｉｇｕｒｅ２ＣｏｄｅｃｏｎｖｅｒｓｉｏｎｏｆＲＯＶ－ｂａｓｅｄｒａｎｄｏｍｋｅｙｓ圖２基于ＲＯＶ規(guī)則的隨機鍵編碼轉(zhuǎn)換Ｆｉｇｕｒｅ３Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｒｉｐｓｐｌｉｔｔｉｎｇ圖３行程劃分示意圖Ｆｉｇｕｒｅ４Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｈｅｔｒｉｐｓｐｌｉｔｔｉｎｇｆｏｒｍｕｌｔｉｐｌｅｖｅｈｉｃｌｅｓ圖４多車行程劃分示意圖在ＭＴＶＲＰ－ＴＷ－ＲＤ問題中，已知待服務(wù)的倉庫點總數(shù)為Ｎ。首先考慮運輸車總數(shù)為１的情形，由于每個行程至少服務(wù)１個倉庫，因而整個運輸過程至多分為Ｎ個行程。對于一個由所有倉庫編號構(gòu)成的排列（即１～Ｎ的隨機排列），利用Ｎ－１個分割符即可實現(xiàn)所有行程的劃分，圖３給出了相應(yīng)的編碼與行程劃分示意圖，該算例中需要服務(wù)的倉庫總數(shù)為９。在此基礎(chǔ)上，考慮到配送車的總數(shù)為Ｍ的情形，為了實現(xiàn)各運輸車輛的任務(wù)劃分，只需要在圖３編碼的基礎(chǔ)上增加Ｍ－１個分隔符。圖４給出了多車配送行程劃分的示意圖，該算例中需要服務(wù)的倉庫總數(shù)為９，運輸車數(shù)目為３。圖３中倉庫總數(shù)為９，編碼１～９表示倉庫編號，１０～１７為分割符號，相鄰２分隔符之間的倉庫序列構(gòu)成一個行程，行程出現(xiàn)的先后順序即為所有行程在該輛車上的執(zhí)行順序。結(jié)合

的編碼數(shù)值為（０．６３，０．２５，０．１７，０．４１），依據(jù)ＲＯＶ規(guī)則可將其轉(zhuǎn)化為排列（４，２，１，３）。Ｆｉｇｕｒｅ２ＣｏｄｅｃｏｎｖｅｒｓｉｏｎｏｆＲＯＶ－ｂａｓｅｄｒａｎｄｏｍｋｅｙｓ圖２基于ＲＯＶ規(guī)則的隨機鍵編碼轉(zhuǎn)換Ｆｉｇｕｒｅ３Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｒｉｐｓｐｌｉｔｔｉｎｇ圖３行程劃分示意圖Ｆｉｇｕｒｅ４Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｈｅｔｒｉｐｓｐｌｉｔｔｉｎｇｆｏｒｍｕｌｔｉｐｌｅｖｅｈｉｃｌｅｓ圖４多車行程劃分示意圖在ＭＴＶＲＰ－ＴＷ－ＲＤ問題中，已知待服務(wù)的倉庫點總數(shù)為Ｎ。首先考慮運輸車總數(shù)為１的情形，由于每個行程至少服務(wù)１個倉庫，因而整個運輸過程至多分為Ｎ個行程。對于一個由所有倉庫編號構(gòu)成的排列（即１～Ｎ的隨機排列），利用Ｎ－１個分割符即可實現(xiàn)所有行程的劃分，圖３給出了相應(yīng)的編碼與行程劃分示意圖，該算例中需要服務(wù)的倉庫總數(shù)為９。在此基礎(chǔ)上，考慮到配送車的總數(shù)為Ｍ的情形，為了實現(xiàn)各運輸車輛的任務(wù)劃分，只需要在圖３編碼的基礎(chǔ)上增加Ｍ－１個分隔符。圖４給出了多車配送行程劃分的示意圖，該算例中需要服務(wù)的倉庫總數(shù)為９，運輸車數(shù)目為３。圖３中倉庫總數(shù)為９，編碼１～９表示倉庫編號，１０～１７為分割符號，相鄰２分隔符之間的倉庫序列構(gòu)成一個行程，行程出現(xiàn)的先后順序即為所有行程在該輛車上的執(zhí)行順序。結(jié)合上述ＲＯＶ隨機鍵編碼方式和基于分割符的行程劃分方法，對ＭＴＶＲＰ－ＴＷ－ＲＤ問題采用如下編

【參考文獻】：
期刊論文
[1]求解車輛路徑問題的人工蜂群算法[J]. 王志剛,夏慧明.  計算機工程與科學(xué). 2014(06)
[2]基于混沌粒子群優(yōu)化的新型VRP求解算法[J]. 于勝龍,薄煜明,陳志敏,吳盤龍,朱凱,尹明鋒.  計算機工程與科學(xué). 2012(12)



本文編號：3319636