融合邻域搜索策略蚁群算法求解带时间窗口的车辆路径问题

计算机与现代化 ›› 2022, Vol. 0 ›› Issue (03): 98-102.

融合邻域搜索策略蚁群算法求解带时间窗口的车辆路径问题

(1.西华师范大学数学与信息学院,四川南充637009;2.西华师范大学计算方法与应用研究所,四川南充637009)

出版日期:2022-04-29 发布日期:2022-04-29
作者简介:张雄(1996—),男,四川巴中人,硕士研究生,研究方向:智能算法,E-mail: liaofana@foxmail.com; 通信作者:潘大志(1974—),男,四川三台人,教授,硕士生导师,研究方向:智能计算与算法设计,E-mail: pdzzj@126.com。
基金资助:
国家自然科学基金资助项目(11871059); 四川省教育厅自然科学基金资助项目(18ZA0469); 西华师范大学英才科研基金资助项目(17YC385)

Ant Colony Algorithm Combining Neighborhood Search Strategy for Vehicle Routing Problem with Time Window

(1. College of Mathematics and Information, China West Normal University, Nanchong 637009, China；

2. Institute of Computing Method and Application Software, China West Normal University, Nanchong 637009, China)

Online:2022-04-29 Published:2022-04-29

摘要/Abstract

摘要： 对于求解带时间窗口车辆路径问题,提出一种融合邻域搜索策略的改进蚁群算法，针对时间窗口特性，将等待时间加入到蚁群算法的状态转移规则之中。为提升算法的局部寻优能力，设计多种节点删除操作和插入操作对得到的路径进行邻域搜索。最后利用Solomon标准算例对改进算法进行测试，与目前已知最优解对比，实验结果表明改进后的蚁群算法对带时间窗口的车辆路径问题有较好的适用性。

关键词: 车辆路径问题, 时间窗口, 蚁群算法, 邻域搜索

Abstract: For solving the vehicle routing problem with time windows, this paper proposes an improved ant colony algorithm that integrates neighborhood search strategies. In view of the time window characteristics, the waiting time is added to the state transition rule of the ant colony algorithm. In order to improve the local optimization ability of the algorithm, a variety of node for deletion operations and insertion operations are designed to search the neighborhood of the obtained path. Finally, the improved algorithm is tested using the Solomon standard example, and compared with the currently known optimal solution. The experimental results show that the improved ant colony algorithm has good applicability to the vehicle routing problem with time windows.

Key words: vehicle routing problem, time window, ant colony algorithm, local search

张雄, 潘大志, . 融合邻域搜索策略蚁群算法求解带时间窗口的车辆路径问题[J]. 计算机与现代化, 2022, 0(03): 98-102.

ZHANG Xiong, PAN Da-zhi, . Ant Colony Algorithm Combining Neighborhood Search Strategy for Vehicle Routing Problem with Time Window[J]. Computer and Modernization, 2022, 0(03): 98-102.

参考文献［25］

［1］	DANTZIG G B, RAMSER J H. The truck dispatching problem［J］. Management Science, 1959,6(1):80-91.
［2］	SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research, 1987,35(2):254-265.
［3］	韩亚娟,彭运芳,魏航,等. 超启发式遗传算法求解带软时间窗的车辆路径问题［J］. 计算机集成制造系统, 2019,25(10):2571-2579.
［4］	张智海,吴星玮. 带时间窗车辆路径问题的并行遗传算法［J］. 工业工程, 2007(3):111-114.
［5］	吴天羿,许继恒,刘建永,等. 求解有硬时间窗车辆路径问题的改进遗传算法［J］. 系统工程与电子技术, 2014,36(4):708-713.
［6］	CHEN C H, TING C J. A hybrid ant colony system for vehicle routing problem with time windows［J］. Eastern Asia Society for Transportation Studies, 2005,6:2822-2836.
［7］	张建同,丁烨. 变邻域模拟退火算法求解速度时变的VRPTW问题［J］. 运筹与管理, 2019,28(11):77-84.
［8］	蔚帅,蒋洪伟. 基于聚类的变邻域模拟退火算法求解VRPTW［J］. 北京信息科技大学学报(自然科学版), 2020,35(5):86-92.
［9］	范厚明,刘文琪,徐振林,等. 混合粒子群算法求解带软时间窗的VRPSPD问题［J］. 计算机工程与应用, 2018,54(19):221-229.
［10］	叶勇,张惠珍. 求解带时间窗车辆路径问题的狼群算法［J］. 公路交通科技, 2017,34(10):100-107.
［11］	戚远航,蔡延光,蔡颢,等. 带时间窗的车辆路径问题的离散蝙蝠算法［J］. 电子学报, 2018,46(3):672-679.
［12］	CORDEAU J F, LAPORTE G, MERCIER A. A unified tabu search heuristic for vehicle routing problems with time windows［J］. Journal of the Operational Research Society, 2001,52(8):928-936.
［13］	仪孝展. 基于改进遗传算法的物流车辆路径规划方法研究与应用［D］. 西安:西安理工大学, 2018.
［14］	黄务兰,张涛. 基于改进遗传算法的带时间窗车辆路径问题研究［J］. 微型机与应用, 2016,35(13):21-24.
［15］	HARZI M, KRICHEN S. Variable neighborhood descent for solving the vehicle routing problem with time windows［J］. Electronic Notes in Discrete Mathematics, 2017,58:175-182.
［16］	PARASKEVOPOULOS D C, REPOUSSIS P P, TARANTILIS C D, et al. A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows［J］. Journal of Heuristics, 2008,14(5):425-455.
［17］	DONG W B, ZHOU K, QI H Q, et al. A tissue P system based evolutionary algorithm for multi-objective VRPTW［J］. Swarm and Evolutionary Computation, 2018,39:310-322.
［18］	ALZAQEBAH M A, JAWARNEH S, SARIM H M, et al. Bees algorithm for vehicle routing problems with time windows［J］. International Journal of Machine Learning and Computing, 2018,8(3):234-240.
［19］	DORIGO M, MANIEZZO V, COLORNI A. Ant system: Optimization by a colony of cooperating agents［J］. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 1996,26(1):29-41.
［20］	徐廷学,张海军,付霖宇,等. 基于量子蚁群算法的VRPTW研究［J］. 火力与指挥控制, 2019,44(8):34-40.
［21］	邓丽娟,张纪会. 混合蚁群算法求解双目标时间窗VRP［J］. 复杂系统与复杂性科学, 2020,17(4):73-84.
［22］	李奕颖,秦刚. 基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解［J］. 计算机系统应用, 2019,28(7):9-16.
［23］	NIOR O S D S, JOS EUGNIO LEAL J E, REIMANN M. A multiple ant colony system with random variable neighborhood descent for the dynamic vehicle routing problem with time windows［J］. Soft Computing, 2021,25(1):2935-2948.
［24］	金淳,张雨,王聪. 带时间窗车辆路径问题的分布式多agent蚁群算法［J］. 计算机应用研究, 2018,35(3):666-670.
［25］	KONSTANTAKOPOULOS G D. GAYIALIS S P, KECHAGIAS E P, et al. A multiobjective large neighborhood search metaheuristic for the vehicle routing problem with time windows［J］. Algorithms, 2020,13(10):243-259.

[1]	曲建波, 孙剑伟. 基于蚁群算法的导航卫星功率增强任务规划[J]. 计算机与现代化, 2021, 0(02): 104-108.
[2]	高月仁, 吴涛, 高峡. 基于蚁群算法优化的路由频率动态择径的研究[J]. 计算机与现代化, 2020, 0(12): 32-37.
[3]	李显良1,2，周庆平2，谭长庚3，谭焱良2，徐则阳2. 基于蚁群算法的城市体育设施优化选址[J]. 计算机与现代化, 2020, 0(03): 33-.
[4]	叶家琪1，符强1，2，贺亦甲1，叶浩1 . 基于聚类集成的蚁群算法求解大规模TSP问题[J]. 计算机与现代化, 2020, 0(02): 31-.
[5]	梁晶亮,黄军胜,白树军,王鹏,李睿. 基于蚁群算法的电力数据网络APT攻击预警模型[J]. 计算机与现代化, 2019, 0(01): 95-.
[6]	付永忠，潘云峰. 基于改进蚁群算法的垂直旋转式贴片机贴装顺序优化[J]. 计算机与现代化, 2017, 0(8): 17-.
[7]	凌云翔1,2,宋志远1,张世海1,马力2. 基于蚁群算法的高原地区车辆运输路径优化问题[J]. 计算机与现代化, 2016, 0(9): 77-82.
[8]	宋琪，敬超. 面向多核系统的蚁群最优化能耗调度算法[J]. 计算机与现代化, 2016, 0(6): 91-96.
[9]	陈潋，乐嘉锦，陈德华，冯洁莹. 糖尿病临床诊断事件序列中频繁模式的发现算法[J]. 计算机与现代化, 2016, 0(4): 7-11.
[10]	蔡明，左勇安. 基于MapReduce的混合蚁群算法研究[J]. 计算机与现代化, 2016, 0(10): 6-.
[11]	李媛祯，杨群，段汐. 基于均衡更新蚁群算法的飞机排序调度[J]. 计算机与现代化, 2015, 0(2): 57-.
[12]	蔡文哲，王斌君. 一种QoS平面蚁群路由算法的设计与实现[J]. 计算机与现代化, 2015, 0(12): 15-.
[13]	陈曼青1，武子荣1，崔伟宁1，常婷婷2. 改进蚁群算法在装备保障路径选择中的应用[J]. 计算机与现代化, 2015, 0(11): 113-117.
[14]	朱卫宵，祝前旺，陈康. 基于改进蚁群算法的海上编队传感器资源分配模型[J]. 计算机与现代化, 2014, 0(12): 15-18+22.
[15]	刘晓曦;李卓越. 优化蚁群算法的云环境负载均衡[J]. 计算机与现代化, 2013, 1(9): 42-45.