Adaptive Genetic Grey Wolf Optimizer Algorithm for Capacitated Vehicle Routing Problem
HUANG Ge-wen1,3, CAI Yan-guang1, QI Yuan-hang2, CHEN Hou-ren1, WANG Shi-hao1
1. School of Automation, Guangdong University of Technology, Guangzhou, Guangdong 510006, China;
2. School of Computer Science, University of Electronic Science and Technology of China, Zhongshan Institute, Zhongshan, Guangdong 528402, China;
3. Information and Network Center, Jiaying University, Meizhou, Guangdong 514015, China
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).
[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.
2019, Vol. 47 
