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

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

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

【部分圖文】：

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

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

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

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



本文編號(hào)：3319636