带容量约束的车辆路径问题是NP难的组合优化问题，精确算法无法在合理的时间内得到有效的解.本文提出了一种采用灰狼空间整数编码和先路由后分组解决方案生成策略的自适应遗传灰狼优化算法用于求解带容量约束的车辆路径问题.该算法提出了移动平均自适应灰狼更新策略和灰狼基因遗传策略提高全局收敛能力，同时提出带3-opt的劣势点启发邻域搜索策略来增强算法的全局和局部搜索能力.实验结果表明：所提出算法具有较高的计算精度和较强的寻优能力，有较高的鲁棒性，通过与自适应扫描和速度推测粒子群优化算法、K均值聚类和灰狼优化混合算法、大邻域搜索和蚁群优化混合算法、基于精英选择的多种群人工蜂群算法、基于集覆盖的扩展节省算法、混合变邻域生物共栖搜索算法等6个算法对比证明了算法的有效性.
Abstract
Capacitated vehicle routing problem (CVRP) is an NP-hard combinatorial optimization problem. Many CVRP instances cannot be solved by the exact algorithms in a reasonable time. This paper presents an adaptive genetic grey wolf optimizer algorithm (AGGWOA), which implements grey wolf space integer coding and route-first cluster-second solution generation strategy, to solve the capacitated vehicle routing problem. The AGGWOA proposes the adaptive update strategy on moving average and grey wolf genetic operation that improve the global convergence of the algorithm. To enhance the global search ability and the local search ability of the algorithm, the AGGWOA proposes the inferior-node heuristic neighborhood search strategy, which implements the 3-opt local search operation. The experimental results indicate that the algorithm proposed has superior computational accuracy, effective optimization ability and high robustness. The effectiveness of the algorithm proposed is proved by comparing AGGWOA with 6 other algorithms including adaptive sweep plus velocity tentative PSO(Adaptive Sweep + VTPSO), K-means clustering GWO(K-GWO), hybrid large neighbourhood search algorithm with ant colony optimization(LNS-ACO), elitism-based multiple colonies artificial bee colony(EBMC-ABC), set-covering-based extended savings algorithm(SC-ESA), hybrid variable neighborhood symbiotic organisms search(HVNSOS).
关键词
组合优化 /
车辆路径问题 /
离散灰狼优化算法 /
自适应更新 /
遗传操作 /
邻域搜索
{{custom_keyword}} /
Key words
combination optimization /
vehicle routing /
discrete grey wolf optimizer /
adaptive update /
genetic operation /
neighborhood search
{{custom_keyword}} /
中图分类号：
TP301
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[2] Korayem L,Khorsid M,Kassem S S.Using grey wolf algorithm to solve the capacitated vehicle routing problem[J].IOP Conference Series:Materials Science and Engineering,2015,83(1):012014.
[3] Akpinar S.Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem[J].Expert Systems with Applications,2016,61:28-38.
[4] Ng K K H,Lee C K M,Zhang S Z,et al.A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re-routing strategies under time-dependent traffic congestion[J].Computers & Industrial Engineering,2017,109:151-168.
[5] Akhand M A H,Peya Z J,Murase K.Capacitated vehicle routing problem solving using adaptive sweep and velocity tentative PSO[J].International Journal of Advanced Computer Science and Applications,2017,8(12):288-295.
[6] Hannan M A,Akhtar M,Begum R A,et al.Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm[J].Waste Management,2018,71:31-41.
[7] 李阳,范厚明.求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法[J].控制与决策,2018,33(07):1190-1198. LI Yang,FAN Hou-ming.Hybrid variable neighborhood symbiotic organisms search for capacitated vehicle routing problem[J].Control and Decision,2018,33(07):1190-1198.(in Chinese)
[8] Mirjalili S,Mirjalili S M,Lewis A.Grey wolf optimizer[J].Advances in Engineering Software,2014,69:46-61.
[9] 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,2017,30(2):413-435.
[10] Beasley J E.Route first-Cluster second methods for vehicle routing[J].Omega,1983,11(4):403-408.
[11] Prins C.A simple and effective evolutionary algorithm for the vehicle routing problem[J].Computers & Operations Research,2004,31(12):1985-2002.
[12] 戚远航,蔡延光,蔡颢,等.旅行商问题的混沌混合离散蝙蝠算法[J].电子学报,2016,44(10):2543-2547. QI Yuan-hang,CAI Yan-guang,CAI Hao,et al.Chaotic hybrid discrete bat algorithm for traveling salesman problem[J].Acta Electronica Sinica,2016,44(10):2543-2547.(in Chinese)
[13] 戚远航,蔡延光,蔡颢,等.带时间窗的车辆路径问题的离散蝙蝠算法[J].电子学报,2018,46(3):672-679. QI Yuan-hang,CAI Yan-guang,CAI Hao,et al.Discrete bat algorithm for vehicle routing problem with time window[J].Acta Electronica Sinica,2018,46(3):672-679.(in Chinese)
[14] 戚远航,蔡延光,蔡颢,等.泰森多边形的离散蝙蝠算法求解多车场车辆路径问题[J].控制理论与应用,2018,35(8):1142-1150. QI Yuan-hang,CAI Yan-guang,CAI Hao,et al.Voronoi diagram-based discrete bat algorithm for multi-depot vehicle routing problem[J].Control Theory & Applications,2018,35(8):1142-1150.(in Chinese)
[15] Helsgaun K.General k-opt submoves for the Lin-Kernighan TSP heuristic[J].Mathematical Programming Computation,2009,1(2):119-163.
[16] Stanojevic M,Stanojevic B,Vujosevic M.Enhanced savings calculation and its applications for solving capacitated vehicle routing problem[J].Applied Mathematics & Computation,2013,219(20):10302-10312.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金 (No.61074147）; 广东省自然科学基金 (No.S2011010005059）; 广东省教育部产学研结合项目 (No.2012B091000171，No.2011B090400460）; 广东省科技计划项目 (No.2012B050600028，No.2014B010118004，No.2015A030401104，No.2016A050502060）; 广东省普通高校青年创新人才项目 (No.2018KQNCX333）; 广州市花都区科技计划项目 (No.HD14ZD001）; 广州市科技计划项目 (No.201604016055）; 广州市天河区科技计划项目 (No.2018CX005）
{{custom_fund}}
PDF(573 KB)
