带时间窗的车辆路径问题的离散蝙蝠算法

doi:10.3969/j.issn.0372-2112.2018.03.024

电子学报 ›› 2018, Vol. 46 ›› Issue (3): 672-679.DOI: 10.3969/j.issn.0372-2112.2018.03.024

带时间窗的车辆路径问题的离散蝙蝠算法

戚远航¹, 蔡延光¹, 蔡颢², 黄何列¹

1. 广东工业大学自动化学院, 广东广州 510006;
2. 奥尔堡大学健康科学与工程系, 丹麦奥尔堡 9220

收稿日期:2016-09-30 修回日期:2016-12-21 出版日期:2018-03-25
- 通讯作者:
- 蔡延光
- 作者简介:
- 戚远航,男,1993年6月出生,广东湛江人.现为广东工业大学博士生,从事供应链物流及智能算法的研究.E-mail:qiyuanhang77@163.com
- 基金资助:
- 国家自然科学基金 (No.61074147）; 广东省自然科学基金 (No.S2011010005059）; 广东省教育部产学研结合项目 (No.2012B091000171，No.2011B090400460）; 广东省科技计划项目 (No.2012B050600028，No.2014B010118004，No.2016A050502060）; 广州市花都区科技计划项目 (No.HD14ZD001）; 广州市科技计划项目 (No.201604016055）

Discrete Bat Algorithm for Vehicle Routing Problem with Time Window

QI Yuan-hang¹, CAI Yan-guang¹, CAI Hao², HUANG He-lie¹

1. School of Automation, Guangdong University of Technology, Guangzhou, Guangdong 510006, China;
2. Department of Health Science and Technology, Aalborg University, Aalborg 9220, Denmark

Received:2016-09-30 Revised:2016-12-21 Online:2018-03-25 Published:2018-03-25

摘要/Abstract

摘要： 本文提出了一种离散蝙蝠算法求解带时间窗的车辆路径问题（vehicle routing problem with time window）.该算法提出了蝙蝠位置的定义、速度的定义、位置更新操作、速度更新操作、频率更新操作，并采用惩罚机制与向量比较机制相结合的方法处理相关约束条件.该算法引入了随机插入策略、最少客户车辆插入搜索、普通插入搜索、交换搜索、带时间窗的2-Opt搜索等策略来扩大搜索空间、加强算法的收敛效率.实验结果表明：所提出算法具有较强的寻优能力、较高的鲁棒性、较少的时间耗费；本文所采用的关键参数值和策略能提高所提出算法的性能；通过假设检验证明了所提出算法与对比算法之间的算法性能均有显著性差异.

关键词: 离散蝙蝠算法, 车辆路径问题, 时间窗, 2-Opt

Abstract: This paper presents a discrete bat algorithm to solve the vehicle routing problem with time window (VRPTW).The proposed algorithm defines position,velocity,updated operation of the position,updated operation of the velocity and updated operation of the frequency,and uses a method which combines the penal function with vectorial comparison to deal with constrained conditions.The proposed algorithm adopts random inserted strategy,inserted research strategy for the vehicle with minimum customers,ordinary inserted research strategy,exchanged research strategy and 2-Opt strategy with time window to expand the search space and enhance the convergent rate.Experimental results show that,the proposed algorithm has a stronger optimization capability,higher robustness and less time consumption,key parameter values and strategies used in this paper can improve performances of the proposed algorithm,and according to the hypotheses testing,there exsits a significant difference between the proposed algorithm and comparative algorithms.

Key words: discrete bat algorithm, vehicle routing problem, time window, 2-Opt

中图分类号:

TP301

戚远航, 蔡延光, 蔡颢, 黄何列. 带时间窗的车辆路径问题的离散蝙蝠算法[J]. 电子学报, 2018, 46(3): 672-679.

QI Yuan-hang, CAI Yan-guang, CAI Hao, HUANG He-lie. Discrete Bat Algorithm for Vehicle Routing Problem with Time Window[J]. Acta Electronica Sinica, 2018, 46(3): 672-679.

参考文献

[1] Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[2] Gong Y J,Zhang J,Liu O,et al.Optimizing the vehicle routing problem with time windows:a discrete particle swarm optimization approach[J].IEEE Transactions on Systems Man and Cybernetics Part C,2012,42(2):254-267.
[3] Hu W,Liang H,Peng C,et al.A hybrid chaos-particle swarm optimization algorithm for the vehicle routing problem with time window[J].Entropy,2013,4(4):1247-1270.
[4] Barbucha D.A cooperative population learning algorithm for vehicle routing problem with time windows[J].Neurocomputing,2014,146(146):210-229.
[5] Yang X S.A New Metaheuristic Bat-Inspired Algorithm[M].Heidelberg:Springer Berlin Heidelberg,2010.65-74.
[6] Osaba E,Yang X S,Diaz F,et al.An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems[J].Engineering Applications of Artificial Intelligence,2016,48(C):59-71.
[7] Zhou Y,Luo Q,Xie J,et al.A Hybrid Bat Algorithm with Path Relinking for the Capacitated Vehicle Routing Problem[M].Cham:Springer International Publishing,2016.255-276.
[8] 孟祥虎,胡蓉,钱斌.求解带时间窗车辆路径问题的有效混合PBIL算法[J].系统工程理论与实践,2014,34(10):2701-2709. MENG Xiang-hu,HU Rong,QIAN Bin.Effective hybrid population-based incremental learning algorithm for vehicle routing problem with time windows[J].Systems Engineering-Theory and Practice,2014,34(10):2701-2709.(in Chinese)
[9] 葛斌,韩江洪,魏臻,等.求解带时间窗车辆路径问题的动态混合蚁群优化算法[J].模式识别与人工智能,2015,28(7):641-650. GE Bin,HAN Jiang-Hong,WEI Zhen,et al.Dynamic hybrid ant colony optimization algorithm for solving the vehicle routing problem with time windows[J].Pattern Recognition and Artificial Intelligence,2015,28(7):641-650.(in Chinese)
[10] Hiermann G,Puchinger J,Ropke S,et al.The electric fleet size and mix vehicle routing problem with time windows and recharging stations[J].European Journal of Operational Research,2016,252(3):995-1018.
[11] 周永权,黄正新,刘洪霞.求解TSP问题的离散型萤火虫群优化算法[J].电子学报,2012,40(6):1164-1170. ZHOU Yong-quan,HUANG Zheng-xin,LIU Hong-xia.Discrete glowworm swarm optimization algorithm for TSP problem[J].Acta Electronica Sinica,2012,40(6):1164-1170.(in Chinese)
[12] Qi Y,Hou Z,Li H,et al.A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows[J].Computers and Operations Research,2015,62(C):61-77.
[13] Xu S H,Liu J P,Zhang F H,et al.A combination of genetic algorithm and particle swarm optimization for vehicle routing problem with time windows[J].Sensors,2015,15(9):21033-21053.
[14] Niu Y,He J,Wang Z,et al.A P-Based hybrid evolutionary algorithm for vehicle routing problem with time windows[J].Mathematical Problems in Engineering,2014,2014(3):1-11.
[15] Yu B,Yang Z Z,Yao B Z.A hybrid algorithm for vehicle routing problem with time windows[J].Expert Systems with Applications,2011,38(1):435-441.

带时间窗的车辆路径问题的离散蝙蝠算法

Discrete Bat Algorithm for Vehicle Routing Problem with Time Window

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	魏振春, 傅宇, 马仲军, 吕增威, 石雷, 张本宏. 带时间窗的无线可充电传感器网络多目标路径规划算法[J]. 电子学报, 2022, 50(8): 1819-1829.
[2]	李纪三, 纪彦星, 曹鼎, 刘溶, 任渊. 基于广义时间窗的旋转相控阵雷达资源调度算法[J]. 电子学报, 2022, 50(5): 1050-1057.
[3]	郭荣梅, 胡小兵. 求解时间窗口网络中前k条最短路径的方法[J]. 电子学报, 2020, 48(7): 1387-1395.
[4]	戚远航, 蔡延光, 蔡颢, 杨亮, YAO Yeboah. 带容量约束的供应链物流运输调度问题的双层变邻域蝙蝠算法[J]. 电子学报, 2019, 47(7): 1434-1442.
[5]	黄戈文, 蔡延光, 戚远航, 陈厚仁, 王世豪. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.
[6]	张子成, 韩伟, 毛波. 基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题[J]. 电子学报, 2018, 46(8): 1849-1857.
[7]	戚远航, 蔡延光, 蔡颢, 汤雅连, 吕文祥. 旅行商问题的混沌混合离散蝙蝠算法[J]. 电子学报, 2016, 44(10): 2543-2547.
[8]	易云飞, 董文永, 林晓东, 蔡永乐. 求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J]. 电子学报, 2015, 43(4): 658-664.
[9]	易云飞, 蔡永乐, 董文永, 林晓东. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061.
[10]	周永权, 黄正新, 刘洪霞. 求解TSP问题的离散型萤火虫群优化算法[J]. 电子学报, 2012, 40(6): 1164-1170.
[11]	王俊;颜罡. 一种移动终端多天线方向图重构快速选择算法与基于滑动时间窗的加速实现[J]. 电子学报, 2011, 39(4): 803-811.
[12]	郭嘉;雷苗;彭喜元. 基于相应簇回声状态网络静态分类方法[J]. 电子学报, 2011, 39(3A): 14-18.
[13]	王生水;柴舜连;毛钧杰. 一种加快时间步迭代的加窗技术[J]. 电子学报, 2006, 34(9): 1700-1702.
[14]	祝崇隽;刘民;吴澄;吴晓冰. 针对模糊需求的VRP的两种2-OPT算法[J]. 电子学报, 2001, 29(8): 1035-1037.
[15]	刘超;薛正辉;高本庆;刘瑞祥;杨仕明. 时域近场测试中的探头误差分析与修正[J]. 电子学报, 2001, 29(12): 1689-1692.