基于鄰域搜索的成品油多艙多目標配送路徑優(yōu)化算法研究
發(fā)布時間：2021-07-10 16:13
針對成品油配送中多車型,多車艙的優(yōu)化調度難題,綜合考慮路徑安排,艙位指派及車輛指派等決策.以配送成本最小,路徑風險最小以及油品準時送達為目標,建立了成品油配送多目標路徑優(yōu)化模型.基于鄰域搜索的基本思想,提出求解成品油配送多目標路徑優(yōu)化問題的MOVNS算法框架,并結合不同的可行解運行策略和比較準則,衍生出三類MOVNS算法（MOVNS-1、MOVNS-2、MOVNS-3）.采用12組算例進行數(shù)值實驗,結果表明,三種算法均能有效的求解配送模型,提升成品油多艙配送問題的解決效率;且MOVNS-2算法具有較強的局部搜索能力,MOVNS-3算法容易跳出局部最優(yōu):同時,考慮節(jié)點關聯(lián)性的可行解構造策略和并行鄰域搜索策略能夠增強算法的尋優(yōu)能力.
【文章來源】：系統(tǒng)工程理論與實踐. 2019,39(10)北大核心CSSCIEICSCD
【文章頁數(shù)】：16 頁
【部分圖文】：
圖１?ＭＯＶＮＳ算法框架??不兼容節(jié)點：由于約束（１０）和（１１）限制了油品的裝載形式．因此若對任意車型．通過３．２．１節(jié)的艙位指??＜＿．互．？＋?？＋．??
?２?＝?＼Ｈｋ＼??（ｉｅｖ＾ｐ．ｈ）??（２１）??ＩＫ?＝?Ｌ??ｈ??Ｖｉ?６?ｖ＇．Ｖｐ?ｅ?ｐ．??（２２）??ｎ??（＊，ｐ）??１．??（２３）??＾?＜?Ｑｈｋ＇，??（２４）??＼Ｈｋ＼＞＼Ｖ＇＼＼Ｐ＼．??（２５）??由約束（２２）和（２３）可知．油罐車Ｖ單次配送的加油站數(shù)小于等于其可用艙位數(shù)｜辦｜．結合模型定義??以及油罐車分艙常識，可知ＣＡＰ問題是一類規(guī)模較小的０－１整數(shù)規(guī)劃問題，本文擬采用較大需求優(yōu)先指派??的原則進行ＣＡＰ問題的求解．具體操作如圖２所示．同時．在初始化排序過程中．在保證較大需求優(yōu)先指派??的前提下，為滿足約束（２２）？（２５），需要優(yōu)先安排同一加油站的油品需求．??對待裝栽的油品排序得集合＝?，，．．．，??可用車艙集合乂．?｝??ｊ?－－??＝１??｝??ｆ??將＾指派給麵??－其屮＾??＝ｍａｘ｛—?＾?１，?Ｖ／ｚ?ｇ?Ｈｋ，｝?■??ｈ??ｉ除＂豐所宥與＾劉７應相同加？樂站面?Ｎ??油品需求，并對ｙ按順序ｔ新編號??＇?＇??Ｈｋ．?＝?Ｈｋ．＼｛ｈｍｎ｝??輸出指派結果??圖２艙位指派算法??３．２．２載重檢測??同一般ＶＲＰ問題一致．成品油配送問題包含時間窗和艙容約束．本文ｄ通過式（３）的方式將時間窗約??束轉化為了求解目標．因此在路徑構造和后續(xù)迭代過程中僅需考慮車輛的艙容限制：車載檢測包含兩部分：第??一，艙位使用情況檢測：第二．負載可行檢測．??１）艙位使用情況檢測??①若待檢驗車輛ｆｃ指定服務的加油站節(jié)點中存在ｊ的不兼容節(jié)點．則連接加油站違反艙容約束：??②假設待檢驗車輛Ａ？的已裝載油品需求總數(shù)為風，％表示加油站７的油品需求總數(shù)．
第Ｋ）期??詹紅鑫．等：基于鄰域搜索的成品油多艙多Ｈ標配送路徑優(yōu)化算法研究??２６７１??個解運行的多目標鄰域兌法（ＭＯＶＮＳ－２）和基于種群的多目標鄰域算法（ＭＯＶＮＳ－３）而言？具有較強的局部??搜索能力．能夠得到更小的乂乃值．其１２組算例的平均值僅為０．１８．遠低ｆ?ＭＯＶＮＳ－２的０．３２以及??ＭＯＶＮＳ－３的０．７４．盡管具有較強的局部搜索能力．但由于缺乏對各子目標進行獨立的考量．導致其優(yōu)化結??果并不占優(yōu)．ｒｌ２、ｒｌ３的平均取值僅為２．２８和２．２９．且在超過一半的算例中．ＭＯＶＮＳ－１的優(yōu)化結果完全不??占優(yōu)：此外．ＭＯＶＮＳ－１算法只能得到一個優(yōu)化解．不能提供多種解決方案供決策主體選擇．與另外兩種算法??相比．缺乏靈活性．??ＡＩＯＶＮＳ－２每次迭代只對單個解進行操作．且其采用了并行鄰域搜索的方式．加快了算法的收斂速度，因??此ＭＯＶＮＳ－２比ＭＯＶＮＳ－３得到更小的分布間距Ｓ．二者的平均比例維持在１?：?２．５左右．即ＭＯＶＮＳ－２能??夠獲得分布更為均勻的Ｐａｒｅｔｏ解集：此外，ＭＯＶＮＳ－２的．４Ｄ值也遠低于比ＡＩＯＶＮＳ－３．也印證了其局部尋??優(yōu)能力要強于Ｍ０ＶＮＳ－３．??另一方面．在多目標鄰域搜索算法中．基于種群運行的Ｍ０ＶＮＳ－３可以在一個更大范圍的解空間中進行??搜索．因此．Ｍ０ＶＮＳ－３所得Ｐａｒｅｔｏ解集的最大分散度Ｚ）大于Ｍ０ＶＮＳ－２?（平均比例為２?：?１）．即獲得更為??寬廣的解分布．??此外，對比ｉＭＯＶＮＳ－２和Ｍ０ＶＮＳ－３的／？值可發(fā)現(xiàn)從整體上上看．ＡＩ０ＶＮＳ－３得到的Ｐａｒｅｔｏ解集更具??有優(yōu)勢．但在算例１和２中．ＭＯＶＮＳ－２能夠得到更大／？值．這可能是由于Ｍ０
【參考文獻】：
期刊論文
[1]基于兩階段算法的大規(guī)模成品油二次配送優(yōu)化[J]. 張立峰,易萬里,劉曉蘭. 系統(tǒng)工程理論與實踐. 2016(11)
[2]基于訂單鄰域的成品油二次配送中帶時間窗車輛路徑規(guī)劃問題[J]. 李敏,倪少權,周凌,黃強. 計算機集成制造系統(tǒng). 2015(08)
[3]成品油二次配送調度優(yōu)化模型及其遺傳算法求解[J]. 馬義飛,孫曉燕. 運籌與管理. 2010(06)
[4]油品配送車輛路徑問題的交互式求解方法[J]. 戴錫,葉耀華,吳勤旻,朱道立. 系統(tǒng)工程學報. 2009(06)
[5]基于交通流量的城市交叉口事故預測研究——以廣州市為例[J]. 杜衛(wèi)衛(wèi),姜立春,劉付衍華. 華東交通大學學報. 2009(05)
碩士論文
[1]危險貨物道路運輸事故統(tǒng)計分析及綜合管理系統(tǒng)的建立[D]. 石磊.長安大學 2014
本文編號：3276246
【文章來源】：系統(tǒng)工程理論與實踐. 2019,39(10)北大核心CSSCIEICSCD
【文章頁數(shù)】：16 頁
【部分圖文】：
圖１?ＭＯＶＮＳ算法框架??不兼容節(jié)點：由于約束（１０）和（１１）限制了油品的裝載形式．因此若對任意車型．通過３．２．１節(jié)的艙位指??＜＿．互．？＋?？＋．??
?２?＝?＼Ｈｋ＼??（ｉｅｖ＾ｐ．ｈ）??（２１）??ＩＫ?＝?Ｌ??ｈ??Ｖｉ?６?ｖ＇．Ｖｐ?ｅ?ｐ．??（２２）??ｎ??（＊，ｐ）??１．??（２３）??＾?＜?Ｑｈｋ＇，??（２４）??＼Ｈｋ＼＞＼Ｖ＇＼＼Ｐ＼．??（２５）??由約束（２２）和（２３）可知．油罐車Ｖ單次配送的加油站數(shù)小于等于其可用艙位數(shù)｜辦｜．結合模型定義??以及油罐車分艙常識，可知ＣＡＰ問題是一類規(guī)模較小的０－１整數(shù)規(guī)劃問題，本文擬采用較大需求優(yōu)先指派??的原則進行ＣＡＰ問題的求解．具體操作如圖２所示．同時．在初始化排序過程中．在保證較大需求優(yōu)先指派??的前提下，為滿足約束（２２）？（２５），需要優(yōu)先安排同一加油站的油品需求．??對待裝栽的油品排序得集合＝?，，．．．，??可用車艙集合乂．?｝??ｊ?－－??＝１??｝??ｆ??將＾指派給麵??－其屮＾??＝ｍａｘ｛—?＾?１，?Ｖ／ｚ?ｇ?Ｈｋ，｝?■??ｈ??ｉ除＂豐所宥與＾劉７應相同加？樂站面?Ｎ??油品需求，并對ｙ按順序ｔ新編號??＇?＇??Ｈｋ．?＝?Ｈｋ．＼｛ｈｍｎ｝??輸出指派結果??圖２艙位指派算法??３．２．２載重檢測??同一般ＶＲＰ問題一致．成品油配送問題包含時間窗和艙容約束．本文ｄ通過式（３）的方式將時間窗約??束轉化為了求解目標．因此在路徑構造和后續(xù)迭代過程中僅需考慮車輛的艙容限制：車載檢測包含兩部分：第??一，艙位使用情況檢測：第二．負載可行檢測．??１）艙位使用情況檢測??①若待檢驗車輛ｆｃ指定服務的加油站節(jié)點中存在ｊ的不兼容節(jié)點．則連接加油站違反艙容約束：??②假設待檢驗車輛Ａ？的已裝載油品需求總數(shù)為風，％表示加油站７的油品需求總數(shù)．
第Ｋ）期??詹紅鑫．等：基于鄰域搜索的成品油多艙多Ｈ標配送路徑優(yōu)化算法研究??２６７１??個解運行的多目標鄰域兌法（ＭＯＶＮＳ－２）和基于種群的多目標鄰域算法（ＭＯＶＮＳ－３）而言？具有較強的局部??搜索能力．能夠得到更小的乂乃值．其１２組算例的平均值僅為０．１８．遠低ｆ?ＭＯＶＮＳ－２的０．３２以及??ＭＯＶＮＳ－３的０．７４．盡管具有較強的局部搜索能力．但由于缺乏對各子目標進行獨立的考量．導致其優(yōu)化結??果并不占優(yōu)．ｒｌ２、ｒｌ３的平均取值僅為２．２８和２．２９．且在超過一半的算例中．ＭＯＶＮＳ－１的優(yōu)化結果完全不??占優(yōu)：此外．ＭＯＶＮＳ－１算法只能得到一個優(yōu)化解．不能提供多種解決方案供決策主體選擇．與另外兩種算法??相比．缺乏靈活性．??ＡＩＯＶＮＳ－２每次迭代只對單個解進行操作．且其采用了并行鄰域搜索的方式．加快了算法的收斂速度，因??此ＭＯＶＮＳ－２比ＭＯＶＮＳ－３得到更小的分布間距Ｓ．二者的平均比例維持在１?：?２．５左右．即ＭＯＶＮＳ－２能??夠獲得分布更為均勻的Ｐａｒｅｔｏ解集：此外，ＭＯＶＮＳ－２的．４Ｄ值也遠低于比ＡＩＯＶＮＳ－３．也印證了其局部尋??優(yōu)能力要強于Ｍ０ＶＮＳ－３．??另一方面．在多目標鄰域搜索算法中．基于種群運行的Ｍ０ＶＮＳ－３可以在一個更大范圍的解空間中進行??搜索．因此．Ｍ０ＶＮＳ－３所得Ｐａｒｅｔｏ解集的最大分散度Ｚ）大于Ｍ０ＶＮＳ－２?（平均比例為２?：?１）．即獲得更為??寬廣的解分布．??此外，對比ｉＭＯＶＮＳ－２和Ｍ０ＶＮＳ－３的／？值可發(fā)現(xiàn)從整體上上看．ＡＩ０ＶＮＳ－３得到的Ｐａｒｅｔｏ解集更具??有優(yōu)勢．但在算例１和２中．ＭＯＶＮＳ－２能夠得到更大／？值．這可能是由于Ｍ０
【參考文獻】：
期刊論文
[1]基于兩階段算法的大規(guī)模成品油二次配送優(yōu)化[J]. 張立峰,易萬里,劉曉蘭. 系統(tǒng)工程理論與實踐. 2016(11)
[2]基于訂單鄰域的成品油二次配送中帶時間窗車輛路徑規(guī)劃問題[J]. 李敏,倪少權,周凌,黃強. 計算機集成制造系統(tǒng). 2015(08)
[3]成品油二次配送調度優(yōu)化模型及其遺傳算法求解[J]. 馬義飛,孫曉燕. 運籌與管理. 2010(06)
[4]油品配送車輛路徑問題的交互式求解方法[J]. 戴錫,葉耀華,吳勤旻,朱道立. 系統(tǒng)工程學報. 2009(06)
[5]基于交通流量的城市交叉口事故預測研究——以廣州市為例[J]. 杜衛(wèi)衛(wèi),姜立春,劉付衍華. 華東交通大學學報. 2009(05)
碩士論文
[1]危險貨物道路運輸事故統(tǒng)計分析及綜合管理系統(tǒng)的建立[D]. 石磊.長安大學 2014
本文編號：3276246
本文鏈接：http://sikaile.net/kejilunwen/sousuoyinqinglunwen/3276246.html
