基于蚁群优化算法的车辆路径问题研究

本文研究的车辆路径问题包括带运载能力限制的车辆路径问题(CVRP),客户可分的车辆路径问题(SDVRP)和带时间窗的客户可分的车辆路径问题(SDVRPTW)。文中对三类车辆路径问题进行了详细的问题描述,给出了通用的数学模型,并针对各自的特点,设计了相应的蚁群优化算法(ACO)进行求解,将算法在标准问题测试集上进行测试,获得了满意的结果。 本文采用ACO中的蚂蚁系统(AS)来求解VRP。针对AS中收敛性差,易于停滞的缺陷,通过引入信息素窗口限制信息素的最大最小值,只对迭代最好解进行信息素更新,增加精英蚂蚁,判断汇聚情况进行信息素重新初始化,在每次迭代中加入局部搜索优化,在选择概率中加入与问题相关的参数等措施对AS进行优化,大大提高了AS收敛性,有效的避免了算法的停滞现象。利用以上蚂蚁算法在标准数据集上进行求解问题的测试,验证了蚂蚁算法的一些基本参数的性质。 本课题受到交通部课题的资助(“西部地区公路运输大通道集疏运应用技术研究”),负责项目中子课题物流信息管理系统中车辆路线优化模块。利用ACO解决SDVRP的研究成果进行车辆路线优化,并在西部项目的物流管理系统上进行应用,帮助解决了实际的客户可分车辆路线优化问题。