计算机应用 ›› 2020, Vol. 40 ›› Issue (4): 1097-1103.DOI: 10.11772/j.issn.1001-9081.2019081355

• 先进计算 • 上一篇    下一篇

带时间窗的同时取送货车辆路径问题建模及模因求解算法

张庆华, 吴光谱   

  1. 北京科技大学 机械工程学院, 北京 100083
  • 收稿日期:2019-08-05 修回日期:2019-09-30 出版日期:2020-04-10 发布日期:2020-04-17
  • 通讯作者: 张庆华
  • 作者简介:张庆华(1974-),男,黑龙江德都人,副教授,博士,主要研究方向:物流信息系统、物流系统规划、供应链信息采集与监控、物流技术及自动化;吴光谱(1996-),男,河南沈丘人,硕士研究生,主要研究方向:路径规划、物流信息系统。

Modeling and memetic algorithm for vehicle routing problem with simultaneous pickup-delivery and time windows

ZHANG Qinghua, WU Guangpu   

  1. School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China
  • Received:2019-08-05 Revised:2019-09-30 Online:2020-04-10 Published:2020-04-17

摘要: 为解决逆向物流背景下的带时间窗的同时取送货车辆路径问题(VRPSPDTW),根据实际情况建立了相应的车辆路径问题模型,并采用模因算法进行求解。在模型的求解过程中使用引导弹射搜索(GES)生成初始种群,在种群进化的过程中采用边界组合交叉(EAX)产生子代,并采用多种邻域结构对子代进行修复、教育,以提高解的质量和算法的搜索效率。通过在Wang和Chen测试数据集上与遗传算法(GA)、并行模拟退火(p-SA)算法、离散布谷鸟(DCS)算法进行比较,实验结果显示:在小规模算例进行求解时,所提算法全部取得了当前最优解;对标准规模算例进行求解时,所提算法使70%的算例更新或获取了当前最优解,获得的最优求解算例结果与当前最优解相比有超过5%的提升,充分验证了所提算法求解VRPSPDTW的良好性能。

关键词: 车辆路径问题, 同时取送货, 时间窗, 模因算法, 引导弹射搜索

Abstract: In order to solve the Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW)in the context of reverse logistics,the corresponding vehicle routing problem model was established according to the actual situation and solved by memetic algorithm. In the process of solving the model,the Guided Ejection Search (GES)was used to generate the initial population. In the process of population evolution,the Edge Assembly Crossover (EAX)method was used to generate the offspring,and in order to improve the quality of solutions and the search efficiency of algorithms,multiple neighborhood structures were used to repair and educate the offspring. The performance of memetic algorithm was tested and compared with Genetic Algorithm (GA),parallel-Simulate Annealing algorithm (p-SA) and Discrete Cuckoo Search(DCS)algorithm on Wang and Chen test dataset. Experimental results show that the proposed algorithm obtains the current optimal solutions when solving all small-scale examples;the algorithm updates or achieves current optimal solutions on 70% examples when solving the standard-scale examples,and the obtained optimal solution has more than 5% improvement compared with the current optimal solution,fully verifying the good performance of the algorithm for solving VRPSPDTW.

Key words: vehicle routing problem, simultaneous pickup-delivery, time window, memetic algorithm, Guided Ejection Search (GES)

中图分类号: