Improved Bacterial Foraging Algorithm for Solving Vehicle Routing Optimization Problem with Time Windows

doi:10.19678/j.issn.1000-3428.0059260

Abstract

Abstract: This paper proposes an improved Bacterial Foraging Algorithm(BFA) to solve the Vehicle Routing Problem with Time Windows(VRPTW).The to-be-distributed customer points are clustered by K-means according to the geographical location,and the classification results are inserted into the optimal location of the distribution path in order within the time window,so the initial solution of the problem is constructed.Then the chemotaxis operation is combined with the removal operator in Large Neighborhood Search(LNS) for optimization,which expands the search range and improves the operation efficiency of the algorithm.Experimental results show that the algorithm can shorten the distribution path and minimize the overall distribution cost within the time window.

Key words: Vehicle Routing Problem(VRP), time window, Bacterial Foraging Algorithm(BFA), large neighborhood search, greedy insertion method

摘要： 为求解带时间窗的车辆路径问题（VRPTW），提出一种改进的细菌觅食算法。将待配送的客户点依据地理位置进行K-means聚类，使得到的分类结果在满足时间窗的要求下，按顺序插入配送路径的最佳位置中，构造VRPTW问题的初始解，同时通过结合趋化操作与大邻域搜索中的removal算子进行距离寻优，扩大算法搜索范围并提高运行效率。实验结果表明，在规定时间窗内，改进算法能合理安排配送路径并最小化总配送成本。

关键词: 车辆路径问题, 时间窗, 细菌觅食算法, 大邻域搜索, 贪婪插入法

CLC Number:

TP301.6

LI Jun, HAO Liyan, HE Yitao, DUAN Yurong. Improved Bacterial Foraging Algorithm for Solving Vehicle Routing Optimization Problem with Time Windows[J]. Computer Engineering, 2021, 47(11): 44-53.

李珺, 郝丽艳, 何奕涛, 段钰蓉. 求解带时间窗车辆路径优化问题的改进细菌觅食算法[J]. 计算机工程, 2021, 47(11): 44-53.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0059260

http://www.ecice06.com/EN/Y2021/V47/I11/44

Figures/Tables 17

References

[1] 金淳,张雨,王聪.带时间窗车辆路径问题的分布式多agent蚁群算法[J].计算机应用研究,2018,35(3):666-670. JIN C,ZHANG Y,WANG C.Distributed multi agent-based ant colony algorithm for vehicle routing problem with time windows[J].Application Research of Computers,2018,35(3):666-670.(in Chinese)
[2] 徐廷学,张海军,付霖宇,等.基于量子蚁群算法的VRPTW研究[J].火力与指挥控制,2019,44(8):34-40. XU T X,ZHANG H J,FU L Y,et al.Research on VRPTW based on quantum ant colony algorithm[J].Fire Control & Command Control,2019,44(8):34-40.(in Chinese)
[3] 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(Applications and Reviews),2012,42(2):254-267.
[4] 李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策,2010,25(9):1379-1383. LI L,LIU S X,TANG J F.Improved ant colony algorithm for solving vehicle routing problem with time windows[J].Control and Decision,2010,25(9):1379-1383.(in Chinese)
[5] 张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统,2002,8(6):451-454. ZHANG L P,CHAI Y T,CAO R.Improved genetic algorithm for vehicle routing problem with time windows[J].Computer Integrated Manufacturing Systems,2002,8(6):451-454.(in Chinese)
[6] LIU J S,LUO Z W,DUAN D Z,et al.A GA approach to vehicle routing problem with time windows considering loading constraints[J].High Technology Letters,2017,23(1):54-62.
[7] WU Y X,SONG W,CAO Z G,et al.Learning improvement heuristics for solving routing problems[EB/OL].[2020-07-11].https://arxiv.org/abs/1912.05784.
[8] CHEN B H,QU R,BAI R B,et al.A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes[J].RAIRO-Operations Research,2020,54(5):1467-1494.
[9] PENG B,WANG J H,ZHANG Z Z.A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems[EB/OL].[2020-07-11].https://arxiv.org/abs/2002.03282.
[10] 余伶俐,魏亚东,霍淑欣.基于MCPDDPG的智能车辆路径规划方法及应用[J].控制与决策,2021,36(4):835-846. YU L L,WEI Y D,HUO S X.Intelligent vehicle path planning method and application based on MCPDDPG[J].Control and Decision,2021,36(4):835-846.(in Chinese)
[11] 张景玲,冯勤炳,赵燕伟,等.基于强化学习的超启发算法求解有容量车辆路径问题[J].计算机集成制造系统,2020,26(4):1118-1129. ZHANG J L,FENG Q B,ZHAO Y W,et al.Hyper-heuristic for CVRP with reinforcement learning[J].Computer Integrated Manufacturing Systems,2020,26(4):1118-1129.(in Chinese)
[12] PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine,2002,22(3):52-67.
[13] 李奕颖,秦刚.基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解[J].计算机系统应用,2019,28(7):9-16. LI Y Y,QIN G.Solving vehicle routing problem with time window based on Spark's improved ant colony algorithm[J].Computer Systems & Applications,2019,28(7):9-16.(in Chinese)
[14] 唐德权,黄金贵,史伟奇.基于大数据平台的动态车辆路径调度算法[J].计算机工程,2018,44(1):74-78. TANG D Q,HUANG J G,SHI W Q.Dynamic vehicle routing schedule algorithm based on big-data platform[J]. Computer Engineering,2018,44(1):74-78.(in Chinese)
[15] YASSEN E T,AYOB M,NAZRI M Z A,et al.An adaptive hybrid algorithm for vehicle routing problems with time windows[J].Computers & Industrial Engineering,2017,113:382-391.
[16] 孙沪增,李章维,秦子豪,等.带时间窗车辆路径规划算法研究与实现[J].小型微型计算机系统,2020,41(5):972-978. SUN H Z,LI Z W,QIN Z H,et al.Research and implementation on time-window vehicle routing problem[J].Journal of Chinese Computer Systems,2020,41(5):972-978.(in Chinese)
[17] QI Y T,HOU Z T,LI H,et al.A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows[J].Computers & Operations Research,2015,62:61-77.
[18] DENG Y,ZHU W H,LI H W,et al.Multi-type ant system algorithm for the time dependent vehicle routing problem with time windows[J].Journal of Systems Engineering and Electronics,2018,29(3):625-638.
[19] SHAW P.Using constraint programming and local search methods to solve vehicle routing problems[C]//Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming.New York,USA:ACM Press,1998:417-431.
[20] YAO B Z,YAN Q Q,ZHANG M J,et al.Improved artificial bee colony algorithm for vehicle routing problem with time windows[J].PLoS One,2017,12(9):18-27.
[21] 仪孝展.基于改进遗传算法的物流车辆路径规划方法研究与应用[D].西安:西安理工大学,2018. YI X Z.Research and application of logistics vehicle route planning based on improved genetic algorithm[D].Xi'an:Xi'an University of Technology,2018.(in Chinese)
[22] NALEPA J,BLOCHO M.Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows[J].Soft Computing,2016,20(6):2309-2327.

Please choose a citation manager

Content to export