基于实时信息的取送货动态车辆路径问题研究
PDF下载 (271)孙宝凤,史俊妍,杨 雪,郑再思.基于实时信息的取送货动态车辆路径问题研究[J].宁波大学学报(理工版),2019,32(3):87-94.DOI:
SUN Bao-feng,SHI Jun-yan,YANG Xue,ZHENG Zai-si.Solution for dynamic pickup and delivery problem based on real-time information[J].Journal of Ningbo University(Natural Science & Engineering Edition),2019,32(3):87-94.DOI:
| Title: | Solution for dynamic pickup and delivery problem based on real-time information |
| 作者: | 孙宝凤, 史俊妍, 杨 雪, 郑再思 |
| Author(s): | SUN Bao-feng, SHI Jun-yan, YANG Xue, ZHENG Zai-si |
| 关键词: | 动态车辆路径规划; 取送货问题; 动态算法; 构造型算法; 禁忌搜索算法 |
| Keywords: | vehicle routing; pickup and delivery problem; dynamic algorithm; constructive algorithm; tabu search algorithm |
| 分类号: | U491 |
| 文献标识码: | A |
| 摘要: | 为适应点对点、实时城市配送对动态响应和快速决策提出的新要求, 研究了多种实时信息作用和影响下的取送货动态车辆路径问题. 采用将动态问题转化为一系列静态问题的建模方法, 建立了基于实时信息的取送货动态车辆路径模型; 设计了动态算法框架, 运用构造算法获得初始可行解, 运用禁忌搜索算法改善初始可行解质量. 实验表明, 本文的模型和算法能有效解决基于实时信息的取送货动态车辆路径问题, 将初始可行解的质量(实时物流配送成本)改善了34%. |
| Abstract: | 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%. |
| 参考文献 /References: | [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 branch- and-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 Con- ference on Tools with Artificial Intelligence, 2001:160-167. |
| 备注/Memo: | 收稿日期: 2019?03?02. 宁波大学学报（理工版）网址: http://journallg.nbu.edu.cn/ 基金项目: 国家自然科学基金（51308249）; 博士学科点专项科研基金（20130061110008）; 吉林省产业技术研究与开发专项（2015Y044）. 第一作者: 孙宝凤（1970－）, 女, 吉林长春人, 博导/教授, 主要研究方向http://journallg.nbu.edu.cn/ |
