硬时间窗VRP的混合变邻域禁忌搜索算法

来源：计算机工程与应用杂志2023年第13期北京时间：

作者：贺琪, 官礼和, 崔焕焕

单位：重庆交通大学 数学与统计学院，重庆 400074

摘要：为了寻求带硬时间窗的车辆路径优化问题的高质量近似解，针对现有数学模型对时间窗约束考虑不充分，建立了最小化车辆数和总行驶距离的双目标非线性优化模型，提出了一种混合变邻域禁忌搜索求解算法。一方面，采用改进的节约算法生成初始解，设计了3种删除算子和一种插入算子对初始解进行扰动优化，为后续禁忌搜索提供优良的初始解；另一方面，基于4种邻域构造算子进行禁忌迭代搜索，利用禁忌搜索的灵活存储结构、避免迂回搜索的禁忌准则和增强多样性搜索的特赦准则有效摆脱局部最优解，最终实现全局优化。在56个Solomon和18个Homberger基准算例上的实验结果表明，该算法的求解质量优于文献中两种同类型搜索算法，具有良好的收敛性和稳定性，且在42个基准实例上获得了比当前已知最好解更低的车辆总行驶距离。

关键词：车辆路径优化,时间窗,禁忌搜索,变邻域搜索