关键词: 车辆路径问题, 模拟退火, 时间窗, 需求可拆分, 揽收配送

Abstract:

This paper studies a Multi-Vehicle Split Pickup and Delivery Problem with Time Windows（MVSPDPTW）. To solve this problem, this paper takes the minimum total length of the vehicle’s driving path as the objective function to establish a mixed integer linear programming model. An efficient Tabu Simulated Annealing（TSA） algorithm is proposed. In the algorithm, two new neighborhood search operators are designed, which are used to repair capacity violations and vehicle change operations respectively. The coordinated way expands the neighborhood search range and avoids the algorithm falling into local optimum. In addition, a tabu mechanism and a penalty mechanism for violation of constraints are added to the algorithm, which can cut the search space effectively and improve the global optimization ability of the algorithm. Finally, a large number of simulation experiments based on the Solomon data set and the constructed simulation data set are provided, so as to verify the effectiveness of the algorithm.

Key words: vehicle routing problem, simulated annealing, time windows, split demand, pickup and delivery