Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (4): 1097-1103.

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

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

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

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

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.

CLC Number: