电子学报 ›› 2019, Vol. 47 ›› Issue (12): 2602-2610.DOI: 10.3969/j.issn.0372-2112.2019.12.021

• 学术论文 • 上一篇    下一篇

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

黄戈文1,3, 蔡延光1, 戚远航2, 陈厚仁1, 王世豪1   

  1. 1. 广东工业大学自动化学院, 广东广州 510006;
    2. 电子科技大学中山学院计算机学院, 广东中山 528402;
    3. 嘉应学院信息网络中心, 广东梅州 514015
  • 收稿日期:2018-12-02 修回日期:2019-07-20 出版日期:2019-12-25
    • 通讯作者:
    • 蔡延光
    • 作者简介:
    • 黄戈文 男,1972年7月出生于广东梅县.现为广东工业大学自动化学院博士生,嘉应学院信息网络中心系统分析师.研究方向为组合优化、运输调度、计算智能等.E-mail:huang_gewen@163.com;戚远航 男,1993年6月出生于广东湛江.2018年在广东工业大学获得工学博士学位,现为电子科技大学中山学院讲师,从事复杂系统建模与优化、智能规划、运输调度的研究.E-mail:qiyuanhang77@163.com
    • 基金资助:
    • 国家自然科学基金 (No.61074147); 广东省自然科学基金 (No.S2011010005059); 广东省教育部产学研结合项目 (No.2012B091000171,No.2011B090400460); 广东省科技计划项目 (No.2012B050600028,No.2014B010118004,No.2015A030401104,No.2016A050502060); 广东省普通高校青年创新人才项目 (No.2018KQNCX333); 广州市花都区科技计划项目 (No.HD14ZD001); 广州市科技计划项目 (No.201604016055); 广州市天河区科技计划项目 (No.2018CX005)

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. 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
  • Received:2018-12-02 Revised:2019-07-20 Online:2019-12-25 Published:2019-12-25
    • Corresponding author:
    • CAI Yan-guang
    • Supported by:
    • National Natural Science Foundation of China (No.61074147); National Natural Science Foundation of Guangdong Province,  China (No.S2011010005059); Industry-university-research Integration program of Department of Education of Guangdong Province (No.2012B091000171, No.2011B090400460); Science and Technology Project of Guangdong Province (No.2012B050600028, No.2014B010118004, No.2015A030401104, No.2016A050502060); Youth Innovative Talent Program of Universities in Guangdong Province (No.2018KQNCX333); Science and Technology Program of Huadu District,  Guangzhou,  China (No.HD14ZD001); Guangzhou Science and Technology Program (No.201604016055); Science and Technology Program of Tianhe District,  Guangzhou City (No.2018CX005)

摘要: 带容量约束的车辆路径问题是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).

 

Key words: combination optimization, vehicle routing, discrete grey wolf optimizer, adaptive update, genetic operation, neighborhood search

中图分类号: