第36卷第3期2023年6月Vol.36No.3Jun.2023四川轻化工大学学报（自然科学版）JournalofSichuanUniversityofScience&Engineering(NaturalScienceEdition)带时间窗的车辆路径规划的改进蚁群系统算法研究谢鑫煌，朱文忠，魏启康，江嘉文(四川轻化工大学计算机科学与工程学院，四川宜宾644000)摘要：带时间窗的车辆路径规划（VRPTW）是一个多项式复杂程度的非确定性（NP）的组合问题，在运输与配送物流邻域有着广泛的应用。研究表明，元启发式算法是解决VRPTW问题的有效方法。针对基础蚁群算法收敛速度慢、易陷入局部最优的问题，本研究提出了一种改进的蚁群系统。首先，在原算法中修改了信息素更新策略，采用分段函数调整信息素挥发因子；然后，在算法中引入禁忌搜索的邻域搜索算法，对路径的搜索采用2-opt变换策略；最后，实验采用SolomonBenchmark标准算例C1类数据进行Matlab仿真实验，验证并分析了改进策略的有效性。实验结果表明，对比基础蚁群算法，本次的改进算法在寻找全局最优解上有较好的效果，在不同客户数量规模下，由基础蚁群算法求解的成本221.6、424.4、1006.5分别减少至191.8、363.2和828.9。该数据集不同规模下的最优解分别为191.3、362.4及827.3，本次改进的算法实验解与最优解的差值比率仅有0.26%、0.22%和0.19%。关键词：路径规划；蚁群算法；蚁群系统；禁忌搜索中图分类号：TP391文献标志码：A引言随着电子商务经济的发展，商品的输送与传递日益依赖于物流行业[1]，而车辆路径规划问题（VehicleRoutingProblem，VRP）在物流运输中占有重要地位[2]。数据显示，2021年，我国的物流成本为16.7万亿元，约占全国GDP的14.6%，远高于其他国家[3-4]。Dantzig[5]在1959年提出VRP问题，将它定义为一个整数线性规划和一个组合优化问题。VRP是多项式复杂程度的非确定性（Non-deterministicPolynomial，NP）的组合问题[6]，它主要包含一组车辆以及一组特定位置的客户构成的客户集合。每个客户都必须接受一次服务，所有车辆的每次行驶路线的起点和终点都是配送中心。VRP问题旨在为车队找到一组最优路线，以提高向相应的客户提供服务的效率，并实现最小化总路线成本的核心目标。收稿日期：2022-05-06基金项目：四川省科技研发重点项目(2019YFG0200);四川省科技创新(苗子工程)培育项目(2022049);四川省智慧旅游研究基地技术研发项目(ZHZJ19-01);四川轻化工大学研究生创新基金(y2021090;y2021092)通信作者：朱文忠(1971-),男,教授,硕士,研究方向为企...
