改进的蚁群算法求解带时间窗的车辆路径问题

李琳^1,2,3，刘士新^1,2，唐加福^1,2

1. 东北大学信息科学与工程学院2. 东北大学流程工业综合自动化教育部重点实验室3. 沈阳航空航天大学理学院

摘 要：设计了一种改进的蚁群算法,将蚁群系统（ACS）与最大最小蚂蚁系统（MMAS）相结合,在状态转移规则中引入时间窗跨度与服务等待时间因素,并在算法的不同阶段采用不同的信息素蒸发策略以防止算法陷入局部最优.使用路径内2-opt优化方法以及路径间2-opt*优化方法对每次迭代过程所得到的最优解进行局部优化.通过对相关文献实验数据的测试结果表明,该算法在求解效果及运算效率上优于遗传算法与禁忌搜索算法.

关键词：蚁群算法;时间窗;车辆路径问题;优化;