基于两阶段算法的需求可拆分多车型车辆路径问题
详细信息 查看官网全文
- 英文论文题名：Research on Split Delivery Andheterogeneous Fleet Vehicle Routing Problem Based on Two Phase Algorithm
- 论文作者：潘雯雯 ; 郭海湘 ; 周光勇 ; 杜天松
- 英文论文作者：PAN Wen-wen ; GUO Hai-xiang ; ZHOU Guang-yong ; DU Tian-song ; School of Economics and Management ; China University of Geosciences ; Research Center for Digital Business Management ; China University of Geosciences ; Research Center for China Mineral Resources Strategy and Policy ; China University of Geosciences
- 年：2016
- 作者机构：中国地质大学经济管理学院;中国地质大学数字化商务管理研究中心;中国地质大学中国矿产资源战略与政策研究中心;
- 论文关键词：需求可拆分 ; 多车型 ; 车辆路径问题 ; 两阶段算法
- 英文论文关键词：split delivery ; heterogeneous fleet ; vehicle routing problem ; two phase algorithm
- 会议召开时间：2016-11-12
- 会议录名称：第十八届中国管理科学学术年会论文集
- 英文会议录名称：Proceedings of the 18th Chinese Annual Conference on Management Science
- 语种：中文
- 分类号：F252;O221.4
- 学会代码：ZHYJ
- 会议名称：第十八届中国管理科学学术年会
- 会议地点：中国陕西西安
- 主办单位：中国优选法统筹法与经济数学研究会、西安交通大学、中国科学院科技战略咨询研究院、《中国管理科学》编辑部
- 学会名称：中国优选法统筹法与经济数学研究会
- 页数：7
- 文件大小：756k
- 原文格式：O
- 会议级别：全国
摘要
需求可拆分车辆路径问题(SDVRP)属于车辆路径问题(VRP)的变种问题,SDVRP模型松弛了客户服务次数和允许客户需求超过车辆装载能力,能提高车辆装载率和降低车辆成本。SDVRP模型都基于相同车型的假设,这不符合实际物流配送中使用不同车型的情况;且较少分析客户需求拆分阈值对问题解的影响;此外,SDVRP研究较少应用新型仿生搜索算法。因此,本文以多车型和需求拆分阈值为新约束,建立需求可拆分的多车型车辆路径问题(SD-HFVRP)混合整数规划模型;提出以路径优化和路径改进相结合的两阶段算法(TPA)。最后以华北分公司大牛地气田物流系统中的污水回收路径规划为例,重新规划了大牛地气田污水回收的车辆行驶路线,并与大牛地实际回收方案对比,模拟结果有效地减少了车辆使用数目和运输成本。
The split delivery vehicle routing problemC SDVRP) is a variant of the classical vehicle routing problemC VRP),and SDVRP can relax times of customer's service and allow customer's demand to exceed the capacity of vehicle.SDVRP model is more able to improve the vehicle loading rate and reduce the vehicle cost.But the SDVRP based on the assumption of homogeneous fleet of vehicles is not exactly the same with the situation that capacitiies of the vehicles are different during distribution.The research about the split threshold of customer's demandCthe relationship between residual capacity of vehicles and next served customer's demand)is currently little and less literatures analyze the impact on optimal solution of SDVRP.And,the research of SDVRP algorithm involves fewer new bionic search algorithms.Therefore,this paper putting both heterogeneous fleet and the split threshold of customer's demand as new constraints of SDVRP,puts forward the split delivery and heterogeneous fleet vehicle routing problem and establish the mixed integer programming model of SDHFVRP.Secondly,this paper puts forward two phase Algorithm(TPA)to optimize SDHFVRP model and TPA combines Path Optimization and Path Improvement.Then this article analyzes how different values of split threshold of customer's demand have impact on SDHFVRP solution and simulates the contrast experiment about single fleet and heterogeneous fleet.Finally,the article takes the sewage recycling problems in the logistics system of da niu di gas field as example.From this case,the simulational solution shows SDHFVRP model is rational and TPA algorithm is feasible,which csn solve engineering application problems and provide customer with a more holistic science and lower cost solution of actual and overall distribution.
The split delivery vehicle routing problemC SDVRP) is a variant of the classical vehicle routing problemC VRP),and SDVRP can relax times of customer's service and allow customer's demand to exceed the capacity of vehicle.SDVRP model is more able to improve the vehicle loading rate and reduce the vehicle cost.But the SDVRP based on the assumption of homogeneous fleet of vehicles is not exactly the same with the situation that capacitiies of the vehicles are different during distribution.The research about the split threshold of customer's demandCthe relationship between residual capacity of vehicles and next served customer's demand)is currently little and less literatures analyze the impact on optimal solution of SDVRP.And,the research of SDVRP algorithm involves fewer new bionic search algorithms.Therefore,this paper putting both heterogeneous fleet and the split threshold of customer's demand as new constraints of SDVRP,puts forward the split delivery and heterogeneous fleet vehicle routing problem and establish the mixed integer programming model of SDHFVRP.Secondly,this paper puts forward two phase Algorithm(TPA)to optimize SDHFVRP model and TPA combines Path Optimization and Path Improvement.Then this article analyzes how different values of split threshold of customer's demand have impact on SDHFVRP solution and simulates the contrast experiment about single fleet and heterogeneous fleet.Finally,the article takes the sewage recycling problems in the logistics system of da niu di gas field as example.From this case,the simulational solution shows SDHFVRP model is rational and TPA algorithm is feasible,which csn solve engineering application problems and provide customer with a more holistic science and lower cost solution of actual and overall distribution.
引文
[1]李进,傅培华,李修琳,等.低碳环境下的车辆路径问题及禁忌搜索算法研究[J].中国管理科学,2015,23(10):98-106.
[2]颜瑞,张群,胡睿.考虑三维装箱约束的车辆路径问题研究[J].中国管理科学,2015,23(1):128-134.
[3]Dror M,Trudeau P.Savings by split delivery routing[J].Transportation Science,1989,23(2):141-145.
[4]Dror M,Trudeau P.Split delivery routing[J].Naval Research Logistics(NRL),1990,37(3):383-402.
[5]Dror M,Laporte G,Trudeau P.Vehicle routing with split deliveries[J].Discrete Applied Mathematics,1994,50(3):239-254.
[6]Archetti C,Mansini R,Speranza M G.The split delivery vehicle routing problem with small capacity[J].Transportation Science,2001.
[7]Archetti C,Mansini R,Speranza M G.Complexity and reducibility of the skip delivery problem[J].Transportation Science,2005,39(2):182-187.
[8]Archetti C,Savelsbergh M W P,Speranza M G.To split or not to split:That is the question[J].Transportation Research Part E:Logistics and Transportation Review,2008,44(1):114-123.
[9]Nowak M,Ergun(O|¨),WhiteⅢC C.Pickup and delivery with split loads[J].Transportation Science,2008,42(1):32-43.
[10]隋露斯,唐加福,潘震东.用蚁群算法求解需求可拆分车辆路径问题[C]//中国控制与决策会议.烟台.2008:997-1001.
[11]Belenguer J M,Martinez M C,Mota E.A lower bound for the split delivery vehicle routing problem[J].Operations Research,2000,48(5):801-810.
[12]Archetti C,Speranza M G,Hertz A.A tabu search algorithm for the split delivery vehicle routing problem[J].Transportation Science,2006,40(1):64-73.
[13]Boudia M,Prins C,Reghioui M.An effective memetic algorithm with population management for the split delivery vehicle routing problem[C]//Proceedings of International Workshop on Hybrid Metaheuristics.Springer Berlin Heidelberg,2007:16-30.
[14]Archetti C,Speranza M G.The split delivery vehicle routing problem:A survey[M]//The vehicle routing problem:Latest advances and new challenges.US:Springer,2008:103-122.
[15]Berbotto L,Garcia S,Nogales F J.A randomized granular tabu search heuristic for the split delivery vehicle routing problem[J].Annals of Operations Research,2014,222(1):153-173.
[16]Silva M M,Subramanian A,Ochi L S.An iterated local search heuristic for the split delivery vehicle routing problem[J].Computers&Operations Research,2015,53:234-249.
[17]刘旺盛,黄娟.需求可拆分的车辆路径问题的分段求解[J].集美大学学报:自然科学版,2011,16(1):38-44.
[18]熊浩,鄢慧丽.需求可拆分车辆路径问题的三阶段禁忌算法[J].系统工程理论与实践,2015(5):1230-1235.
[19]Frizzell P W,Giffin J W.The split delivery vehicle scheduling problem with time windows and grid network distances[J].Computers&Operations Research,1995,22(6):655-667.
[21]侯立文,谭家美,赵元.求解带时间窗的客户需求可分条件下的车辆路径问题[J].中国管理科学,2007,15(6):46-51.
[22]Archetti C,Speranza M G.A direct trip algorithm for the k-split delivery vehicle routing problem[R].Technical report,2002.
[23]Ho S C,Haugland D.A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J].Computers&Operations Research,2004,31(12):1947-1964.
[24]汪婷婷.基于需求的物流配送车辆路径问题的研究[D].合肥:合肥工业大学,2014.
[25]杨亚璪,靳文舟,郝小妮等.求解集送货可拆分车辆路径问题的启发式算法[J].华南理工大学学报(自然科学版),2010(3):58-63.
[26]李三彬,柴玉梅,王黎明.需求可拆分的开放式车辆路径问题研究[J].计算机工程,2011(6):168-171.
[27]Ray S,Soeanu A.Berger J,et al.The multi-depot splitdelivery vehicle routing problem:Model and solution algorithm[J].Knowledge-Based Systems,2014,71:238-265.
[28]Vornhusen B,Kopfer H.Emission Vehicle routing problem with split delivery and a heterogeneous vehicle fleet[C]//Proceedings of International Conference on Computational Logistics.Springer International Publishing,2015:76-90.
[29]Szeto W Y,Wu Yongzhong.Ho S C.An artificial bee colony algorithm for the capacitated vehicle routing problem[J].European Journal of Operational Research,2011,215(1):126-135.
[2]颜瑞,张群,胡睿.考虑三维装箱约束的车辆路径问题研究[J].中国管理科学,2015,23(1):128-134.
[3]Dror M,Trudeau P.Savings by split delivery routing[J].Transportation Science,1989,23(2):141-145.
[4]Dror M,Trudeau P.Split delivery routing[J].Naval Research Logistics(NRL),1990,37(3):383-402.
[5]Dror M,Laporte G,Trudeau P.Vehicle routing with split deliveries[J].Discrete Applied Mathematics,1994,50(3):239-254.
[6]Archetti C,Mansini R,Speranza M G.The split delivery vehicle routing problem with small capacity[J].Transportation Science,2001.
[7]Archetti C,Mansini R,Speranza M G.Complexity and reducibility of the skip delivery problem[J].Transportation Science,2005,39(2):182-187.
[8]Archetti C,Savelsbergh M W P,Speranza M G.To split or not to split:That is the question[J].Transportation Research Part E:Logistics and Transportation Review,2008,44(1):114-123.
[9]Nowak M,Ergun(O|¨),WhiteⅢC C.Pickup and delivery with split loads[J].Transportation Science,2008,42(1):32-43.
[10]隋露斯,唐加福,潘震东.用蚁群算法求解需求可拆分车辆路径问题[C]//中国控制与决策会议.烟台.2008:997-1001.
[11]Belenguer J M,Martinez M C,Mota E.A lower bound for the split delivery vehicle routing problem[J].Operations Research,2000,48(5):801-810.
[12]Archetti C,Speranza M G,Hertz A.A tabu search algorithm for the split delivery vehicle routing problem[J].Transportation Science,2006,40(1):64-73.
[13]Boudia M,Prins C,Reghioui M.An effective memetic algorithm with population management for the split delivery vehicle routing problem[C]//Proceedings of International Workshop on Hybrid Metaheuristics.Springer Berlin Heidelberg,2007:16-30.
[14]Archetti C,Speranza M G.The split delivery vehicle routing problem:A survey[M]//The vehicle routing problem:Latest advances and new challenges.US:Springer,2008:103-122.
[15]Berbotto L,Garcia S,Nogales F J.A randomized granular tabu search heuristic for the split delivery vehicle routing problem[J].Annals of Operations Research,2014,222(1):153-173.
[16]Silva M M,Subramanian A,Ochi L S.An iterated local search heuristic for the split delivery vehicle routing problem[J].Computers&Operations Research,2015,53:234-249.
[17]刘旺盛,黄娟.需求可拆分的车辆路径问题的分段求解[J].集美大学学报:自然科学版,2011,16(1):38-44.
[18]熊浩,鄢慧丽.需求可拆分车辆路径问题的三阶段禁忌算法[J].系统工程理论与实践,2015(5):1230-1235.
[19]Frizzell P W,Giffin J W.The split delivery vehicle scheduling problem with time windows and grid network distances[J].Computers&Operations Research,1995,22(6):655-667.
[21]侯立文,谭家美,赵元.求解带时间窗的客户需求可分条件下的车辆路径问题[J].中国管理科学,2007,15(6):46-51.
[22]Archetti C,Speranza M G.A direct trip algorithm for the k-split delivery vehicle routing problem[R].Technical report,2002.
[23]Ho S C,Haugland D.A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J].Computers&Operations Research,2004,31(12):1947-1964.
[24]汪婷婷.基于需求的物流配送车辆路径问题的研究[D].合肥:合肥工业大学,2014.
[25]杨亚璪,靳文舟,郝小妮等.求解集送货可拆分车辆路径问题的启发式算法[J].华南理工大学学报(自然科学版),2010(3):58-63.
[26]李三彬,柴玉梅,王黎明.需求可拆分的开放式车辆路径问题研究[J].计算机工程,2011(6):168-171.
[27]Ray S,Soeanu A.Berger J,et al.The multi-depot splitdelivery vehicle routing problem:Model and solution algorithm[J].Knowledge-Based Systems,2014,71:238-265.
[28]Vornhusen B,Kopfer H.Emission Vehicle routing problem with split delivery and a heterogeneous vehicle fleet[C]//Proceedings of International Conference on Computational Logistics.Springer International Publishing,2015:76-90.
[29]Szeto W Y,Wu Yongzhong.Ho S C.An artificial bee colony algorithm for the capacitated vehicle routing problem[J].European Journal of Operational Research,2011,215(1):126-135.