基于蚁群算法的动态车辆调度问题的研究

车辆调度问题涉及的行业非常广泛,高节奏的生活对运输业实时性的要求越来越强烈。如何在静态车辆调度问题的基础上解决动态车辆调度问题并且得出最优的调度结果,已经成为众多学者研究的重点和难点。车辆调度问题属于NP难问题,以往的求解算法可以分为精确算法和启发式算法两大类：精确算法由于引入了严格的数学方法,无法避免指数爆炸增长,所以只能有效求解小规模的车辆调度问题；绝大多数研究学者把精力用在构造高质量的启发式算法上。本文通过比较各种启发式算法,并选择改进的蚁群算法来解决运输途中有新订单出现的动态车辆调度问题。 本文围绕基于蚁群算法的动态车辆调度这一主题,主要做了以下几方面的工作： 1.首先简单的描述了车辆调度问题,然后研究了动态车辆调度问题,比较了静态车辆调度和动态车辆调度的区别,分析了动态车辆调度问题中变化信息的处理方法。最后研究了各种针对车辆调度问题的算法,包括精确算法、启发式算法及亚启发式算法。 2.比较各类算法并最终选择蚁群算法,通过一系列的仿真实验,对蚁群算法参数的合理选取进行了较为深入的研究,提出了最优算法参数组合。较于以前完全凭经验和试探来选取参数,大大提高了效率。同时在三个方面对基本蚁群算法进行改进：(1)挥发因子由常数变成变量函数；(2)引入“奖惩”机制；(3)最大最小蚁群系统。将改进后的蚁群算法分别与基本蚁群算法、遗传算法进行实例分析比较,验证改进蚁群算法的有效性。 3.进行实例仿真：运用Matlab仿真软件对旅行商问题、带时间窗的静态车辆调度问题、理想路况和现实路况的实例等进行了仿真对比,通过与基本蚁群算法、遗传算法的仿真对比得出改进蚁群算法得到的优化结果更好,证明了改进蚁群算法的有效性。 4.分析选择了现实生活中较常发生的一类动态车辆调度——在运输途中有新订单到来,并用改进蚁群算法对新到订单进行处理接受还是拒绝,接受新订单的话如何在送货途中的基础上完成新订单的任务。 本文有效的完成了对基本蚁群算法的改进,并用改进蚁群算法使得一类动态车辆调度问题得到了很好的解决。达到了解决具有现实意义的车辆调度问题的目的。