Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (6): 1897-1904.DOI: 10.11772/j.issn.1001-9081.2023060760

Special Issue: 先进计算

• Advanced computing • Previous Articles     Next Articles

Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window

Yan LI1,2, Dazhi PAN1,2(), Siqing ZHENG1   

  1. 1.School of Mathematics & Information,China West Normal University,Nanchong Sichuan 637009,China
    2.Sichuan Colleges and Universities Key Laboratory of Optimization Theory and Applications (China West Normal University),Nanchong Sichuan 637009,China
  • Received:2023-06-14 Revised:2023-09-16 Accepted:2023-09-20 Online:2023-10-07 Published:2024-06-10
  • Contact: Dazhi PAN
  • About author:LI Yan, born in 1997, M. S. candidate. His research interests include intelligent computing, combinatorial optimization.
    ZHENG Siqing, born in 2000, M. S. candidate. Her research interests include uniform convex optimization.
  • Supported by:
    National Natural Science Foundation of China(11871059);Talent Research Fund of China West Normal University(17YC385)

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

李焱1,2, 潘大志1,2(), 郑思情1   

  1. 1.西华师范大学 数学与信息学院, 四川 南充 637009
    2.最优化理论与应用四川省高校重点实验室(西华师范大学), 四川 南充 637009
  • 通讯作者: 潘大志
  • 作者简介:李焱(1997—),男(苗族),四川泸州人,硕士研究生,主要研究方向:智能计算、组合优化
    郑思情(2000—),女,四川南充人,硕士研究生,主要研究方向:均匀凸优化。
  • 基金资助:
    国家自然科学基金资助项目(11871059);西华师范大学英才科研基金资助项目(17YC385)

Abstract:

Aiming at the Multi-Depot Vehicle Routing Problem with Time Window (MDVRPTW), an Improved Adaptive Large Neighborhood Search algorithm (IALNS) was proposed. Firstly, a path segmentation algorithm was improved in the stage of constructing the initial solution. Then, in the optimization stage, the designed removal and repair heuristic operators were used to compete with each other to select the optimal operator, a scoring mechanism was introduced for the operators, and the heuristic operator was selected by roulette. At the same time, the iteration cycle was segmented and the operator weight information was dynamically adjusted in each cycle, effectively to prevent the algorithm from falling into local optimum. Finally, simulated annealing mechanism was adopted as the acceptance criterion of the solution. The relevant parameters of the IALNS were determined by experiments on the Cordeau normative instances, and the solution results of the proposed algorithm were compared with other representative research results in this field. The experimental results show that the solution error between IALNS and Variable Neighborhood Search (VNS) algorithm does not exceed 0.8%, even better in some cases; compared with the multi-phase improved shuffled frog leaping algorithm, the average time-consuming of the proposed algorithm is reduced by 12.8%, and the runtime is shorter for most instances. So the above results verify IALNS is an effective algorithm for solving MDVRPTW.

Key words: Multi-Depot Vehicle Routing Problem with Time Window (MDVRPTW), Adaptive Large Neighborhood Search (ALNS), sequence segmentation, adaptive weight, simulated annealing

摘要:

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

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

CLC Number: