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

作者：于芹作者单位：上海交通大学文献类型：硕士论文011车辆路径规划概述经典车辆路径问题其实就是在车辆路径的调度中仅仅考虑最基本的货车载重量约束(或容量约束)的最一般化的运输问题即有容量约束的车辆路径问题(CapacitatedVehicleRoutingProblem）。经典VRP要求满足的条件及假设：CVRP的数学模型带时间窗的车辆路径问题VRPTWVRPTW的数学模型2对VRP问题的相关研究求解问题的元启发式算法3蚁群算法简史蚁群算法简史1998年10月在比利时布鲁塞尔召开了第一届蚁群算法国际研讨会（ANTS）标志着蚁群算法的正式国际化。2000年MarcoDorigo和BonabeauE等人在国际顶级学术刊物《Nature》上发表了蚁群算法的研究综述从而把这一领域的研究推向了国际数学的最前沿。在我国最早关于蚁群算法的研究见于1997年10月张纪会与徐心和发表的论文“一种新的进化算法——蚁群算法”中。蚁群算法的研究现状蚁群算法原理蚁群算法原理下图是一个形象化的图示用以说明蚁群的路径搜索过程蚂蚁算法采用人工蚂蚁模拟自然界蚂蚁的寻径方式每个人工蚂蚁的行为符合下列规律基于TSP的基本蚁群算法的数学模型在t时刻蚂蚁k由城市i转移到城市j的状态转移概率为了避免残留信息素过多引起残留信息淹没启发信息在每只蚂蚁走完一步或者完成对所有n个城市的遍历（也即一个循环结束）后要对残留信息进行更新处理。t+n时刻在路径(ij)上的信息量可按照如下规则进行调整。根据信息素更新策略的不同DorigoM提出了三种不同的基本蚁群算法模型分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型基本蚁群算法的程序结构流程4蚁群算法的基本步骤：基本蚁群算法的改进改进算法中位于第i个结点的蚂蚁k按以下选择策略移动到结点j：改进算法的信息素局部更新规则改进算法的信息素全局更新规则蚁群算法应用实例计算结果每次迭代的最短距离与平均距离对比图结果对比5CVRP问题的蚁群算法实现在VRP问题中每只蚂蚁所构造的回路仅是可行解的一个组成部分各蚂蚁所构造的回路可能能够组成一些可行解但也可能一个可行解都得不到。避免无可行解可采取以下策略：CVRP实例仿真运行过程界面一次仿真运行的结果多配送中心的车辆路径问题MDVRPMDVRP的数学模型