混合多目标灰狼算法求解多目标VRPTW问题

doi:10.3778/j.issn.1002-8331.2306-0383

摘要/Abstract

摘要： 针对带时间窗的多目标车辆路径规划问题，建立了最小化总成本和均衡度的多目标车辆路径优化模型，并提出了一种混合多目标灰狼算法进行求解。主要设计3点策略：（1）设计新的编码解码方式实现连续灰狼位置向量向离散客户序列的转化。（2）采用收敛性指标和分布性指标来进行决策个体的选择。（3）设计了多种删除、插入算子实施局部路径优化。为说明算法的有效性，以Solomon中的部分算例为例，将该算法与MOIGA和改进的ACO算法进行实验对比。实验结果表明，所提出的混合多目标灰狼算法能找到更好的Pareto解，并且性能优于其他进化算法。

关键词: 多目标优化, 车辆路径规划问题, 灰狼算法, 时间窗

Abstract: A multi-objective vehicle routing optimization model is established to minimize total cost and equilibrium degree for multi-objective vehicle routing problem with time windows, and a hybrid multi-objective grey wolf algorithm is proposed to solve the problem. Mainly design three strategies: (1) A new encoding and decoding method is designed to achieve the conversion of continuous grey wolf position vectors to discrete customer sequences. (2) Convergence and distribution indicators are used to select decision individuals. (3) Multiple deletion and insertion operators have been designed to implement local routing optimization. To demonstrate the effectiveness of the algorithm, some numerical examples in Solomon are used as examples to experimentally compare the proposed algorithm with MOIGA and improved ACO algorithms. Experimental results show that the hybrid multi-objective grey wolf algorithm proposed in this paper can find a better Pareto solution, and its performance is better than other evolutionary algorithm.

Key words: multi-objective optimization, vehicle routing problem, grey wolf algorithm, time window

陈凯, 龚毅光. 混合多目标灰狼算法求解多目标VRPTW问题[J]. 计算机工程与应用, 2024, 60(11): 309-318.

CHEN Kai, GONG Yiguang. Hybrid Multiple-Objective Grey Wolf Algorithm Solving Multi-Objective Vehicle Routing Problem with Time Windows[J]. Computer Engineering and Applications, 2024, 60(11): 309-318.

参考文献

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] 庞燕, 罗华丽, 邢立宁, 等. 车辆路径优化问题及求解方法研究综述[J]. 控制理论与应用, 2019, 36(10): 1573-1584.
PANG Y, LUO H L, XING L N, et al. A survey of vehicle routing optimization problems and solution methods[J]. Control Theory and Applications, 2019, 36(10): 1573-1584.
[3] 赵振华, 王杰, 娄春元. 基于遗传算法的带时间窗约束车辆路径问题研究[J]. 物流科技, 2007, 30(2): 92-95.
ZHAO Z H, WANG J, LOU C Y. Research on vehicle routing problem with time window constraints based on genetic algorithm[J]. Logistics Technology, 2007, 30(2): 92-95.
[4] TAILLARD é, BADEAU P, GENDREAU M, et al. A tabu search heuristic for the vehicle routing problem with soft time windows[J]. Transportation Science, 1997, 31(2): 170-186.
[5] 李琳, 刘士新, 唐加福. 改进的蚁群算法求解带时间窗的车辆路径问题[J]. 控制与决策, 2010(9): 1379-1383.
LI L, LIU S X, TANG J F. Improved ant colony algorithm for solving vehicle routing problem with time windows[J]. Control and Decision Making, 2010(9): 1379-1383.
[6] 王飞. 带时间窗车辆调度问题的改进粒子群算法[J]. 计算机工程与应用, 2014, 50(6): 226-229.
WANG F. Study on vehicle scheduling problem with time windows based on improved particle swarm optimization[J]. Computer Engineering and Applications, 2014, 50(6): 226-229.
[7] 梁承姬, 黄涛, 徐德洪, 等. 改进遗传算法求解带模糊时间窗冷链配送问题[J]. 广西大学学报 (自然科学版), 2016, 41(3): 826-835.
LIANG C J, HUANG T, XU D H, et al. A solution for cold distribution with fuzzy time window based on improved genetic algorithm[J]. Journal of Guangxi University (Natural Science Edition), 2016, 41(3): 826-835.
[8] 雷金羡, 孙宇, 朱洪杰. 改进蚁群算法在带时间窗车辆路径规划问题中的应用[J]. 计算机集成制造系统, 2022, 28(11): 3535-3544.
LEI J X, SUN Y, ZHU H J. Application of improved ant colony optimization algorithms in vehicle path planning with time windows[J]. Computer Integrated Manufacturing System, 2022, 28(11): 3535-3544.
[9] 李楠, 胡蓉, 钱斌, 等. 两阶段混合优化算法求解模糊需求下多时间窗车辆路径问题[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.
[10] 陈治亚, 高辉, 徐光明, 等. 考虑随机需求和硬时间窗的多目标车辆路径优化方法[J]. 铁道科学与工程学报, 2021, 18(12): 3110-3120.
CHEN Z Y, GAO H, XU G M, et al. A multi-objective vehicle routing optimization method based onstochastic demand and hard time window[J]. Journal of Railway Science and Engineering, 2021, 18(12): 3110-3120.
[11] 易云飞, 蔡永乐, 董文永, 等. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061.
YI Y F, CAI Y L, DONG W Y, et al. An improved Ito algorithm for solving multi-objective real-time vehicle routing problems with user satisfaction[J]. Journal of Electronics, 2015, 43(10): 2053-2061.
[12] 柴获, 何瑞春, 苏江省, 等. 求解双目标带时间窗车辆路径问题的蚁群算法[J]. 交通运输系统工程与信息, 2018, 18(4): 156-162.
CHAI H, HE R C, SU J S, et al. An ant colony optimization for the bi-objective vehicle routing problem with time windows on mutilgraph[J]. Transportation System Engineering and Information, 2018, 18(4): 156-162.
[13] MIRANDA D M, BRANKE J, CONCEI??O S V. Algorithms for the multi-objective vehicle routing problem with hard time windows and stochastic travel time and service time[J]. Applied Soft Computing, 2018, 70: 66-79.
[14] MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
[15] FARIS H, ALJARAH I, AL-BETAR M A, et al. Grey wolf optimizer: a review of recent variants and applications[J]. Neural Computing and Applications, 2018, 30: 413-435.
[16] 杨维, 李歧强. 粒子群优化算法综述[J]. 中国工程科学, 2004, 6(5): 87-94.
YANG W, LI Q Q. Survey on particle swarm optimization algorithm[J]. China Engineering Science, 2004, 6(5): 87-94.
[17] GHANNADPOUR S F, ZANDIYEH F. An adapted multi-objective genetic algorithm for solving the cash in transit vehicle routing problem with vulnerability estimation for risk quantification[J]. Engineering Applications of Artificial Intelligence, 2020, 96: 103964.
[18] ZITZLER E, DEB K, THIELE L. Comparison of multiobjective evolutionary algorithms on test functions of different difficulty[C]//Proceedings of the 1999 Genetic and Evolutionary Computation Conference, 1999: 121-122.
[19] DEB K, MOHAN M, MISHRA S. A fast multi-objective evolutionary algorithm for finding well-spread pareto-optimal solutions[J]. KanGAL Report, 2003, 2003002: 1-18.
[20] KOSOLSOMBAT S, RATANAVILISAGUL C. Modified ant colony optimization with selecting and elimination customer and re-initialization for VRPTW[J]. Bulletin of Electrical Engineering and Informatics, 2022, 11(6): 3471-3482.
[21] GARCIA NAJERA A. Multi-objective evolutionary algorithms for vehicle routing problems[D]. Birmingham: University of Birmingham, 2010.
[22] HONG L. An improved LNS algorithm for real-time vehicle routing problem with time windows[J]. Computers & Operations Research, 2012, 39(2): 151-163.