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

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

王 建，李红云，杨燕飞

【摘 要】采用营运车辆的最短行驶距离作为带时间窗车辆路径问题的优化目标，在混合蚁群算法中采用信息素 3层更新策略以完成对车辆的调度，信息素挥发自适应策略充分考虑实时路况，考虑信息素空间扩散特性的局部更新策略，更加忠实于自然界的真实蚂蚁系统，可以提高算法的收敛速度，采用阈值判断的全局信息素更新策略可以防止算法陷入局部最优。通过C#语言实现了混合蚁群算法的计算机求解，最后对10个仿真实例进行仿真计算，结果表明，混合蚁群算法收敛快，寻优结果稳定。 【期刊名称】北京汽车 【年(卷),期】2015(000)003 【总页数】6

【关键词】车辆路径；时间窗；信息素更新策略；蚁群算法

车辆路径问题（Vehicle Routing Problem，VRP）是营运车辆研究领域中一个具有重要理论和现实意义的问题[1]。由于该问题属于 NP-hard（Non-deterministic Polynomial Hard，非确定性多项式难题），所以寻找到一种高效而精确的算法的可能性微乎其微，而自然界中生物群体的合作与竞争等复杂行为产生的群体智能往往对解决某些特定的随机寻优问题提供了高效的解决方法，因此人们开始尝试利用仿生智能算法求解。

蚁群算法模型来源于对自然界真实蚂蚁行为的观测，蚁群在解决优化以及分布控制问题上具有很高的智能性，因此蚁群算法对解决复杂寻优问题的新型算法的开发与应用具有重要的启发价值。蚁群算法随机寻优机制的核心内容是分布