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

摘要：

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

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

所属期刊栏目：59

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金;重庆市高校创新研究群体项目;重庆市研究生联合培养基地建设项目

在线出版日期：2023-07-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：82-91