Discrete Bat Algorithm for Vehicle Routing Problem with Time Window
QI Yuan-hang1, CAI Yan-guang1, CAI Hao2, HUANG He-lie1
1. School of Automation, Guangdong University of Technology, Guangzhou, Guangdong 510006, China;
2. Department of Health Science and Technology, Aalborg University, Aalborg 9220, Denmark
摘要 本文提出了一种离散蝙蝠算法求解带时间窗的车辆路径问题(vehicle routing problem with time window).该算法提出了蝙蝠位置的定义、速度的定义、位置更新操作、速度更新操作、频率更新操作,并采用惩罚机制与向量比较机制相结合的方法处理相关约束条件.该算法引入了随机插入策略、最少客户车辆插入搜索、普通插入搜索、交换搜索、带时间窗的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.
戚远航, 蔡延光, 蔡颢, 黄何列. 带时间窗的车辆路径问题的离散蝙蝠算法[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. 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.