带时间窗的车辆路径规划的改进蚁群系统算法研究

摘要

带时间窗的车辆路径规划(VRPTW)是一个多项式复杂程度的非确定性(NP)的组合问题,在运输与配送物流邻域有着广泛的应用。研究表明,元启发式算法是解决VRPTW问题的有效方法。针对基础蚁群算法收敛速度慢、易陷入局部最优的问题,本研究提出了一种改进的蚁群系统。首先,在原算法中修改了信息素更新策略,采用分段函数调整信息素挥发因子;然后,在算法中引入禁忌搜索的邻域搜索算法,对路径的搜索采用2-opt变换策略;最后,实验采用Solomon Benchmark标准算例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%。