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

摘要：

研究了一种带时间窗的多车型需求可拆分揽收配送问题（Multi-Vehicle Split Pickup and Delivery Problem with Time Windows，MVSPDPTW）。针对这个问题以执行任务车辆行驶路径总长度最小为目标函数，建立了一个混合整数线性规划模型。提出了一种高效禁忌模拟退火（Tabu Simulated Annealing，TSA）算法，在算法中设计了两种新的邻域搜索算子，分别用于修复违反容量约束以及换车操作，多种算子配合的方式扩大了邻域搜索范围，避免算法陷入局部最优。此外在算法中加入了禁忌机制以及违反约束惩罚机制，实现了搜索空间的有效裁剪，提高了算法的全局寻优能力。最后基于Solomon数据集和构造的仿真数据集等对算法进行了大量仿真实验，实验验证了该算法的有效性。

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