蚁群算法在车辆路径问题中的应用研究

配送是物流系统中很重要的环节。在物流的各项成本中,配送成本占了相当高的比例。车辆路径问题是配送系统的核心问题,也是研究热点之一。对车辆路径进行优化,可以提高物流经济效益,实现物流科学化。因此,研究物流配送车辆路径优化问题,不仅具有较大的理论意义,而且还有相当大的实用价值。 本论文在综述国内外有关车辆路径问题研究现状的基础上,通过对几类车辆路径问题模型的分析,对解决此类问题的蚁群算法进行了研究。 1.带时间窗的车辆路径问题是车辆路径问题的一个基本类型,也是目前研究最多的一类车辆路径问题。本文采用基本蚁群系统求解,并对蚁群系统的相关参数以及蚂蚁行为对算法性能的影响通过实验仿真进行了详细的研究。 2.带时间窗的装卸货问题其模型相对带时间窗的车辆路径问题更具一般性。针对装卸货问题的约束条件,采用了一种解构造方式基于插入算法的蚁群算法予以求解。算法设计了两类信息素,分别引导解构造过程的两个关键步骤。仿真表明,该算法能获得满意的结果。 3.研究了蚁群算法求解带软时间窗的随机需求车辆路径问题。分析了随机需求车辆路径问题的研究现状,给出了带软时间窗的随机需求车辆路径问题的数学模型。基于预优化策略,通过在蚁群算法目标函数中引入对违背时间窗路径的惩罚因子,将多目标问题转化为单目标问题。设计了带软时间窗的随机需求车辆路径问题的测试实例,并对各不同规模的实例进行了仿真。 4.研究了基于可信性测度的带模糊旅行时间的车辆路径问题。在介绍基本模糊理论的基础上,给出了基于可信性测度的带模糊旅行时间的车辆路径问题的数学模型,然后采用双蚁群系统分别优化问题的两个目标。设计了测试实例并进行了仿真。 5.最后,对全文进行总结,并对进一步的研究提出一些展望。