带时间窗的多车型需求可拆分揽收配送问题

摘要

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