自适应遗传灰狼优化算法求解带容量约束的车辆路径问题  

Adaptive Genetic Grey Wolf Optimizer Algorithm for Capacitated Vehicle Routing Problem

作　　者：黄戈文[1,3] 蔡延光[1] 戚远航 陈厚仁[1] 王世豪 HUANG Ge-wen;CAI Yan-guang;QI Yuan-hang;CHEN Hou-ren;WANG Shi-hao(School of Automation,Guangdong University of Technology,Guangzhou,Guangdong 510006,China;School of Computer Science,University of Electronic Science and Technology of China,Zhongshan Institute,Zhongshan,Guangdong 528402,China;Information and Network Center,Jiaying University,Meizhou,Guangdong 514015,China)

机构地区：[1]广东工业大学自动化学院,广东广州510006 [2]电子科技大学中山学院计算机学院,广东中山528402 [3]嘉应学院信息网络中心,广东梅州514015

出　　处：《电子学报》2019年第12期2602-2610,共9页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61074147);广东省自然科学基金(No.S2011010005059);广东省教育部产学研结合项目(No.2012B091000171,No.2011B090400460);广东省科技计划项目(No.2012B050600028,No.2014B010118004,No.2015A030401104,No.2016A050502060);广东省普通高校青年创新人才项目(No.2018KQNCX333);广州市花都区科技计划项目(No.HD14ZD001);广州市科技计划项目(No.201604016055);广州市天河区科技计划项目(No.2018CX005)

摘　　要：带容量约束的车辆路径问题是NP难的组合优化问题,精确算法无法在合理的时间内得到有效的解.本文提出了一种采用灰狼空间整数编码和先路由后分组解决方案生成策略的自适应遗传灰狼优化算法用于求解带容量约束的车辆路径问题.该算法提出了移动平均自适应灰狼更新策略和灰狼基因遗传策略提高全局收敛能力,同时提出带3-opt的劣势点启发邻域搜索策略来增强算法的全局和局部搜索能力.实验结果表明:所提出算法具有较高的计算精度和较强的寻优能力,有较高的鲁棒性,通过与自适应扫描和速度推测粒子群优化算法、K均值聚类和灰狼优化混合算法、大邻域搜索和蚁群优化混合算法、基于精英选择的多种群人工蜂群算法、基于集覆盖的扩展节省算法、混合变邻域生物共栖搜索算法等6个算法对比证明了算法的有效性.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).

关 键 词：组合优化 车辆路径问题 离散灰狼优化算法 自适应更新 遗传操作 邻域搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]