基于实时信息的取送货动态车辆路径问题研究
|
摘要
为适应点对点、实时城市配送对动态响应和快速决策提出的新要求,研究了多种实时信息作用和影响下的取送货动态车辆路径问题.采用将动态问题转化为一系列静态问题的建模方法,建立了基于实时信息的取送货动态车辆路径模型;设计了动态算法框架,运用构造算法获得初始可行解,运用禁忌搜索算法改善初始可行解质量.实验表明,本文的模型和算法能有效解决基于实时信息的取送货动态车辆路径问题,将初始可行解的质量(实时物流配送成本)改善了34%.
To meet the updated requirements for dynamic response and quick decision-making in the field of point-to-point real-time urban distribution,the dynamic vehicle routing problem with pick-up and delivery is studied using the real-time information.The dynamic problem is transformed into a series of static problems,and a dynamic vehicle routing model with pickup and delivery based on real-time information is established;The dynamic algorithm framework is designed,and the initial feasible solution is obtained using the construction algorithm,and the quality of the initial feasible solution is improved by using the tabu search algorithm.The experimental results show that the proposed model and algorithm can effectively solve the dynamic vehicle routing problem with pickup and delivery based on real-time information.The quality of the initial feasible solution,the cost of real-time logistics distribution,are both improved by 34%.
To meet the updated requirements for dynamic response and quick decision-making in the field of point-to-point real-time urban distribution,the dynamic vehicle routing problem with pick-up and delivery is studied using the real-time information.The dynamic problem is transformed into a series of static problems,and a dynamic vehicle routing model with pickup and delivery based on real-time information is established;The dynamic algorithm framework is designed,and the initial feasible solution is obtained using the construction algorithm,and the quality of the initial feasible solution is improved by using the tabu search algorithm.The experimental results show that the proposed model and algorithm can effectively solve the dynamic vehicle routing problem with pickup and delivery based on real-time information.The quality of the initial feasible solution,the cost of real-time logistics distribution,are both improved by 34%.
引文
[1]戈丽娜.配送过程中提货送货问题的静态动态方法的应用效果研究[D].哈尔滨:哈尔滨工业大学,2016.
[2]Ferrucci F,Bock S.Real-time control of express pickup and delivery processes in a dynamic environment[J].Transportation Research Part B:Methodological,2014,63:1-14.
[3]杨茹.集送货一体化的动态车辆调度问题研究[D].天津:南开大学,2007.
[4]Jia Y J,Wang C J,Wang L M.A rolling horizon procedure for dynamic pickup and delivery problem with time windows[C].IEEE International Conference on Automation and Logistics,Shenyang,2009:2087-2091.
[5]Marjolein V,Kees J R,Iris F V,et al.The pickup and delivery traveling salesman problem with handling costs[J].European Journal of Operational Research,2017,257(10):118-132.
[6]Escuín D,LarrodéE,Millán C.A cooperative waiting strategy based on elliptical areas for the dynamic pickup and delivery problem with time windows[J].Journal of Advanced Transportation,2016,50(8):1577-1597.
[7]Lin C H,Choy K L,Ho G T S,et al.A decision support system for optimizing dynamic courier routing operations[J].Expert Systems with Applications,2014,41(15):6917-6933.
[8]Ropke S,Cordeau J,Laporte G.Models and branchand-cut algorithms for pickup and delivery problems with time windows[J].Networks,2007,49(4):258-272.
[9]Li H,Lim A.A metaheuristic for the pickup and delivery problem with time windows[C].IEEE International Conference on Tools with Artificial Intelligence,2001:160-167.
[2]Ferrucci F,Bock S.Real-time control of express pickup and delivery processes in a dynamic environment[J].Transportation Research Part B:Methodological,2014,63:1-14.
[3]杨茹.集送货一体化的动态车辆调度问题研究[D].天津:南开大学,2007.
[4]Jia Y J,Wang C J,Wang L M.A rolling horizon procedure for dynamic pickup and delivery problem with time windows[C].IEEE International Conference on Automation and Logistics,Shenyang,2009:2087-2091.
[5]Marjolein V,Kees J R,Iris F V,et al.The pickup and delivery traveling salesman problem with handling costs[J].European Journal of Operational Research,2017,257(10):118-132.
[6]Escuín D,LarrodéE,Millán C.A cooperative waiting strategy based on elliptical areas for the dynamic pickup and delivery problem with time windows[J].Journal of Advanced Transportation,2016,50(8):1577-1597.
[7]Lin C H,Choy K L,Ho G T S,et al.A decision support system for optimizing dynamic courier routing operations[J].Expert Systems with Applications,2014,41(15):6917-6933.
[8]Ropke S,Cordeau J,Laporte G.Models and branchand-cut algorithms for pickup and delivery problems with time windows[J].Networks,2007,49(4):258-272.
[9]Li H,Lim A.A metaheuristic for the pickup and delivery problem with time windows[C].IEEE International Conference on Tools with Artificial Intelligence,2001:160-167.