改进蚁群算法优化车辆路径问题的研究  

Study on Optimization of Vehicle Routing Problem by Improved Ant Colony Algorithm

作　　者：邓会馨 武俊丽[1] DENG Huixin;WU Junli(School of Information and Electronic Technology,Jiamusi University,Jiamusi Heilongjiang 154007,China)

机构地区：[1]佳木斯大学信息电子技术学院,黑龙江佳木斯154007

出　　处：《佳木斯大学学报（自然科学版）》2024年第1期38-42,共5页Journal of Jiamusi University：Natural Science Edition

基　　金：佳木斯大学博士专项(22ZB201515)。

摘　　要：研究采用改进的蚁群算法优化带约束的车辆路径的问题。考虑的约束条件包括路径约束、时间窗约束和容量约束。主要目的是提出一种改进的蚁群算法进行车辆路径优化,构建配送车辆行驶路线,实现配送路线总成本的最小化。从三方面对蚁群算法进行了改进:对参与条件转移概率的候选节点列表进行预处理减少路线构建过程计算的时间复杂度;提出插入式节约算法用于改进蚁群初始配送路线提高寻优精度;基于蚁群系统对信息素更新策略进行改进,加快算法收敛速度。基于Solomon基准数据集,与近年来已取得的研究成果展开对比实验,证明提出的改进算法在提高求解精度和搜索效率方面的有效性,在优化带约束条件的车辆路径问题时的实用性,拓展了蚁群算法的应用领域。In this paper,an improved ant colony algorithm is used to optimize constrained vehicle routing.The constraints considered include path constraints,time window constraints and capacity constraints.The main purpose is to propose an improved ant colony algorithm to optimize vehicle routing,construct vehicle routing,and minimize the total cost of distribution routes.The ant colony algorithm is improved from three aspects:preprocessing the candidate node list involved in conditional transition probability to reduce the time complexity of route construction.An Insertion-based saving algorithm was proposed to improve the initial distribution route of ant colony to improve the optimization accuracy.Based on ant colony system,the pheromone up-dating strategy was improved to accelerate the convergence rate.Based on the Solomon benchmark data set,compared with the research results obtained in recent years,the effectiveness of the improved algorithm in improving the solution accuracy and search efficiency,and the practicability in optimizing the vehicle routing problem with constraints,which expands the application field of ant colony algorithm.

关 键 词：蚁群算法 车辆路径问题 时间窗 插入式节约算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]