计算机应用

作者：李焱, 潘大志, 郑思情

单位：1.西华师范大学 数学与信息学院, 四川 南充 637009；2.最优化理论与应用四川省高校重点实验室(西华师范大学), 四川 南充 637009

关键词：多车场带时间窗车辆路径问题,自适应大邻域搜索,序列分割,自适应权重,模拟退火

基金：国家自然科学基金资助项目(11871059);西华师范大学英才科研基金资助项目(17YC385)

针对多车场带时间窗车辆路径问题（MDVRPTW），提出一种改良自适应大邻域搜索算法（IALNS）。首先，在构造初始解阶段改进一种路径分割算法；其次，在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子，为各算子引入评分机制，采用轮盘赌方式选取启发式算子；同时，将迭代周期分段，动态调整各周期内的算子权重信息，有效避免算法陷入局部最优；最后，采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验，确定IALNS的相关参数，将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明，所提算法与变邻域搜索（VNS）算法的求解误差不超过0.8%，在某些算例上甚至更优；与多相位改进的蛙跳算法相比，算法的平均耗时减少12.8%，所提算法在绝大多数算例上运行时间更短。因此，验证了所提算法是求解MDVRPTW的有效算法。

来源：2024年第6期

《计算机应用》期刊编辑部

查看计算机应用杂志2024年第6期