计算机工程与应用 ›› 2024, Vol. 60 ›› Issue (4): 355-365.DOI: 10.3778/j.issn.1002-8331.2211-0048

• 工程与应用 • 上一篇    下一篇

改进天鹰算法求解时间依赖型车辆路径问题

石小娟,赵兴方,闫龙,唐源,赵慧敏   

  1. 1. 山东工商学院 管理科学与工程学院,山东  烟台  264005
    2. 深圳海关工业品检测技术中心,广东  深圳  518067
  • 出版日期:2024-02-15 发布日期:2024-02-15

Solving Time Dependent Vehicle Routing Problem Based on Improved Aquila Optimizer Algorithm

SHI Xiaojuan, ZHAO Xingfang, YAN Long, TANG Yuan, ZHAO Huimin   

  1. 1. School of Management Science and Engineering, Shandong Technology and Business University, Yantai, Shandong 264005, China
    2. Testing Technology Center for Industrial Products of Shenzhen Customs District, Shenzhen, Guangdong 518067, China
  • Online:2024-02-15 Published:2024-02-15

摘要: 针对速度时变的时间依赖型车辆路径问题,分析时间依赖型路网的行程时间计算方法,提出了一种改进天鹰优化(improved Aquila optimizer, IAO)算法。设计了一种天鹰位置-顾客序列(Aquila-customer, A-C)编解码方式,结合天鹰狩猎的拓展勘探、缩小勘探范围、扩大开发范围以及缩小开发范围四种搜捕猎物的方式,重新定义其智能寻优行为,引入自适应大规模邻域搜索策略,设计多种邻域破坏算子与修复算子,并在算法中加入劣解接受准则,提出循环启发式扰动机制与精英解扰动机制两种停滞扰动策略。Solomon基准算例对比实验以及基于Figliozzi测试算例与遗传算法、粒子群算法、蚁群算法的仿真对比实验均验证了IAO算法的优化性能,同时实际案例的实验结果充分证明了IAO算法在收敛速度与求解质量上的优越性,表明其具备求解时间依赖型车辆路径问题的应用价值。

关键词: 车辆路径问题, 时间依赖, 天鹰优化算法, 自适应大规模邻域搜索

Abstract: An improved Aquila optimizer (IAO) algorithm is proposed for the time dependent vehicle routing problem with time-varying speed, and the travel time calculation method of the time dependent road network is analyzed. An Aquila-customer (A-C) coding and decoding method is designed based on the characteristics of vehicle routing problem. Combining the four hunting methods of Aquila: expanding exploration, narrowing exploration range, expanding exploitation range and narrowing exploitation range, its intelligent search behavior is redefined, adaptive large neighborhood search (ALNS) strategy is introduced, and various neighborhood destroy operators and repair operators are designed. The inferior solution acceptance criterion is added to the algorithm, and two stagnation perturbation strategies, circular heuristic perturbation mechanism and elite perturbation mechanism, are proposed. Solomon benchmark and simulations based on Figliozzi test cases with genetic algorithms, particle swarm algorithms and ant colony algorithms demonstrate the optimization performance of the IAO algorithm, while the experimental results of real cases verify the superiority of the IAO algorithm in terms of convergence speed and solution quality. It is shown that IAO algorithm has the application value for solving time dependent vehicle routing problem.

Key words: vehicle routing problem, time dependent, Aquila optimizer, adaptive large neighborhood search