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

doi:10.3969/j.issn.0372-2112.2019.12.021

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

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

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

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-wen^1,3, CAI Yan-guang¹, QI Yuan-hang², CHEN Hou-ren¹, WANG Shi-hao¹

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)

摘要/Abstract

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

中图分类号:

TP301

黄戈文, 蔡延光, 戚远航, 等. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.

HUANG Ge-wen, CAI Yan-guang, QI Yuan-hang, et al. Adaptive Genetic Grey Wolf Optimizer Algorithm for Capacitated Vehicle Routing Problem[J]. Acta Electronica Sinica, 2019, 47(12): 2602-2610.

参考文献

[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.

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

Adaptive Genetic Grey Wolf Optimizer Algorithm for Capacitated Vehicle Routing Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李杨帅, 彭斐, 韩倩, 李小帅, 解光军. 一种针对QCA电路自动布局布线的混合策略研究[J]. 电子学报, 2023, 51(3): 666-674.
[2]	李彦苍, 巩翔宇. 基于信息熵的改进狮群算法及其在组合优化中的应用[J]. 电子学报, 2021, 49(8): 1577-1585.
[3]	戚远航, 蔡延光, 蔡颢, 杨亮, YAO Yeboah. 带容量约束的供应链物流运输调度问题的双层变邻域蝙蝠算法[J]. 电子学报, 2019, 47(7): 1434-1442.
[4]	王辛, 王晓峰, 李卫民. 一种求解最小割的警示传播算法[J]. 电子学报, 2019, 47(11): 2386-2391.
[5]	戚远航, 蔡延光, 蔡颢, 黄何列. 带时间窗的车辆路径问题的离散蝙蝠算法[J]. 电子学报, 2018, 46(3): 672-679.
[6]	许烁, 王阳, 孙成恺. 模块化可重构服务机器人群的任务规划[J]. 电子学报, 2016, 44(1): 101-109.
[7]	易云飞, 董文永, 林晓东, 蔡永乐. 求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J]. 电子学报, 2015, 43(4): 658-664.
[8]	易云飞, 蔡永乐, 董文永, 林晓东. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061.
[9]	郑巧仙, 李明, 李元香, 唐秋华. 求解双边装配线平衡问题的改进蚁群算法[J]. 电子学报, 2014, 42(5): 841-845.
[10]	钱洁, 郑建国. 引入逆学习的量子自适应禁忌搜索算法[J]. 电子学报, 2013, 41(6): 1069-1075.
[11]	张银雪, 田学民, 邓晓刚. 基于改进人工蜂群算法的盲源分离方法[J]. 电子学报, 2012, 40(10): 2026-2030.
[12]	郑友莲;李元香;雷德明. 求解模糊作业车间调度问题的群体邻域搜索算法[J]. 电子学报, 2011, 39(10): 2454-2458.
[13]	周雅兰;王甲海;印鉴. 一种基于分布估计的离散粒子群优化算法[J]. 电子学报, 2008, 36(6): 1242-1248.
[14]	王少尉, 季晓勇. 最优多用户检测问题研究[J]. 电子学报, 2007, 35(12): 2339-2342.
[15]	邢焕来, 潘炜, 邹喜华. 一种解决组合优化问题的改进型量子遗传算法[J]. 电子学报, 2007, 35(10): 1999-2002.