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

doi:10.3778/j.issn.1002-8331.2211-0048

摘要/Abstract

摘要： 针对速度时变的时间依赖型车辆路径问题，分析时间依赖型路网的行程时间计算方法，提出了一种改进天鹰优化（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

石小娟, 赵兴方, 闫龙, 唐源, 赵慧敏. 改进天鹰算法求解时间依赖型车辆路径问题[J]. 计算机工程与应用, 2024, 60(4): 355-365.

SHI Xiaojuan, ZHAO Xingfang, YAN Long, TANG Yuan, ZHAO Huimin. Solving Time Dependent Vehicle Routing Problem Based on Improved Aquila Optimizer Algorithm[J]. Computer Engineering and Applications, 2024, 60(4): 355-365.

参考文献

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] MALANDRAKI C, DASKIN M S. Time dependent vehicle routing problems: formulations, properties and heuristic algorithms[J]. Transportation Science, 1992, 26(3): 185-200.
[3] 穆东, 王超, 王春胜, 等. 基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 计算机集成制造系统, 2015, 21(6): 1626-1636.
MU D, WANG C, WANG C S, et al. Solving TDVRP based on parallel-simulated annealing algorithm[J]. Computer Integrated Manufacturing Systems, 2015, 21(6): 1626-1636.
[4] ICHOUA S, GENDREAU M, POTVIN J Y. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396.
[5] 张建同, 丁烨. 变邻域模拟退火算法求解速度时变的VRPTW问题[J]. 运筹与管理, 2019, 28(11): 77-84.
ZHANG J T, DING Y. Simulated annealing with variable neighborhood for time-dependent vehicle routing problem with time window[J]. Operations Research and Management Science, 2019, 28(11): 77-84.
[6] 周鲜成, 刘长石, 周开军, 等. 时间依赖型绿色车辆路径模型及改进蚁群算法[J]. 管理科学学报, 2019, 22(5): 57-68. ZHOU X C, LIU C S, ZHOU K J, et al. Improved ant colony algorithm and modelling of time-dependent green vehicle routing problem[J]. Journal of Management Sciences in China, 2019, 22(5): 57-68.
[7] 张景玲, 刘金龙, 赵燕伟, 等. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
ZHANG J L, LIU J L, ZHAO Y W, et al. Hyper-heuristic for time-dependent VRP with simultaneous delivery and pickup[J]. Computer Integrated Manufacturing Systems, 2020, 26(7): 1905-1917.
[8] 范厚明, 孙秀娜, 张跃光, 等. 时变路网下带混合时间窗的车辆路径问题[J]. 计算机工程与应用, 2022, 58(16): 292-302.
FAN H M, SUN X N, ZHANG Y G, et al. Vehicle routing problem with mixed time windows under time-dependent network[J]. Computer Engineering and Applications, 2022, 58(16): 292-302.
[9] 珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
ZHU L, MA X, LIU Z F. Time-dependent green vehicle routing problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 187-194.
[10] LIU C, KOU G, ZHOU X, et al. Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach[J]. Knowledge-Based Systems, 2020, 188: 104813.
[11] 张歆悦, 靳鹏, 胡笑旋, 等. 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究[J/OL]. 中国管理科学 (2022-03-18) [2022-11-13]. http://doi.org/10.16381/j.cnki.issn1003-207x.2021.0203.
ZHANG X Y, JIN P, HU X X, et al. Research on the time-dependent multi-depot open vehicle routing problem with time windows[J/OL]. Chinese Journal of Management Science (2022-03-18) [2022-11-13]. http://doi.org/10. 16381/j.cnki.issn1003-207x.2021.0203.
[12] PAN B, ZHANG Z, LIM A. Multi-trip time-dependent vehicle routing problem with time windows[J]. European Journal of Operational Research, 2021, 291(1): 218-231.
[13] ABUALIGAH L, YOUSRI D, ABDELAZIZ M, et al. Aquila optimizer: a novel meta-heuristic optimization algorithm[J]. Computers & Industrial Engineering, 2021, 157: 107250.
[14] ALRASSAS A M, AL-QANESS M A A, EWEES A A, et al. Optimized ANFIS model using Aquila optimizer for oil production forecasting[J]. Processes, 2021, 9(7): 1194.
[15] WANG S, JIA H, ABUALIGAH L, et al. An improved hybrid Aquila optimizer and harris hawks algorithm for solving industrial engineering optimization problems[J]. Processes, 2021, 9(9): 1551.
[16] FATANI A, DAHOU A, AL-QANESS M A A, et al. Advanced feature extraction and selection approach using deep learning and Aquila optimizer for IoT intrusion detection system[J]. Sensors, 2021, 22(1): 140.
[17] FIGLIOZZI M A. The time dependent vehicle routing problem with time windows: benchmark problems, an efficient solution algorithm, and solution characteristics[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(3): 616-636.
[18] WANG H F, CHEN Y Y. A genetic algorithm for the simultaneous delivery and pickup problems with time window[J]. Computers & Industrial Engineering, 2012, 62(1): 84-95.
[19] 黄戈文, 蔡延光, 戚远航, 等. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.
HUANG G W, CAI Y G, QI Y H, et al. Adaptive genetic grey wolf optimizer algorithm for capacitated vehicle routing problem[J]. Acta Electronica Sinica, 2019, 47(12): 2602-2610.
[20] 李楠, 胡蓉, 钱斌, 等. 两阶段混合优化算法求解模糊需求下多时间窗车辆路径问题[J]. 控制与决策, 2022, 37(6): 1573-1582.
LI N, HU R, QIAN B, et al. Two stage hybrid optimization algorithm for vehicle routing problem with multiple time windows under fuzzy demand[J]. Control and Decision, 2022, 37(6): 1573-1582.
[21] DUAN G, FAN T, CHEN X, et al. A hybrid algorithm on the vessel routing optimization for marine debris collection[J]. Expert Systems with Applications, 2021, 182: 115198.