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

作者：于芹作者单位：上海交通大学文献类型：硕士论文,基于蚁群算法的物流车辆路径优化问题的研究,01,车辆路径规划概述,03,蚁群算法简介,02,VRP问题的相关研究,04,改进的ACO及TSP求解,05,CVRP问题及求解,Contents,目,录,1,车辆路径问题概述,车辆路径规划概述,车辆路径调度问题是由 G Dantzig 首先提出的,N Christofides 在后来总结深化。车辆路径问题（VRP），主要解决的是派多少辆车走什么样的路线进行运输的问题。具体来讲，就是给定了相互连通的若干有货物需求的顾客点，若干车辆从配送中心出发，完成对所有顾客点的配送任务后回到配送中心，要求所走的路线不能重复，目的是找到最小成本的配送方案。,根据实际约束条件的差异，车辆路径问题种类千变万化，并各具特色。,经典车辆路径问题，其实就是在车辆路径的调度中，仅仅考虑最基本的货车载重量约束(或容量约束)的最一般化的运输问题，即有容量约束的车辆路径问题(Capacitated Vehicle Routing Problem）。经典VRP要求满足的条件及假设：,经典车辆路径问题CVRP,CVRP的数学模型,k：第k辆车：运输车辆的数量：车辆k所走的路径的集合,带时间窗的车辆路径问题VRPTW,在很多时候，会要求在一定时间范围内到达顾客点(当然有时配送中心也有时间范围限制)，否则将因停车等待或配送延迟而产生损失。比较而言，时间窗VRP除了必须实现经典 VRP 的要求，还要考虑访问时间的限制，这样才能找到合理方案。,VRPTW 的数学模型,2,VRP问题的相关研究,对VRP问题的相关研究,3,蚁群算法简介,蚁群算法简史,2001年至今,1996年-2001年,意大利学者Dorigo1991年,启发,蚁群算法简史,蚁群算法（Ant Algorithm)是一种由自然界真实蚂蚁觅食行为提炼而成的优化算法，于1991年，由意大利学者Macro Dorigo在其博士论文中提出，并成功的解决了旅行商（TSP）问题。1996年,Macro Dorigo等人在IEEE系统、人、控制论汇刊上发表了”Ant system:optimization by a colony of cooperating agents”一文，系统地阐述了蚁群算法的基本原理和数学模型，蚁群算法逐渐引起了世界许多国家研究者的关注，其应用领域也得到了迅速拓宽。,1998年10月在比利时布鲁塞尔召开了第一届蚁群算法国际研讨会（ANTS），标志着蚁群算法的正式国际化。2000年，Marco Dorigo和Bonabeau E等人在国际顶级学术刊物Nature上发表了蚁群算法的研究综述，从而把这一领域的研究推向了国际数学的最前沿。在我国，最早关于蚁群算法的研究见于1997年10月张纪会与徐心和发表的论文“一种新的进化算法蚁群算法”中。,蚁群算法简史,蚁群算法的研究现状,目前，人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域，由解决一维静态优化问题发展到解决多维动态优化组合问题，由离散域范围内研究逐渐拓展到了连续域范围内研究。同时在蚁群算法的模型改进以及其他仿生优化算法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。,有学者通过对比实验发现，在组合优化问题中，蚁群算法的优化性能要好于遗传算法等算法。,蚁群算法是一种基于种群的启发式搜索算法。蚁群算法广泛应用于求解TSP问题，Job-Shop调度问题，二次指派问题，背包问题等。,蚁群算法 是一种很有发展前景的优化算法,蚁群算法原理,蚁群算法原理,蚂蚁能快速找到最佳觅食路径是因为在蚂蚁个体之间是通过一种称为信息素的物质进行信息传递的。蚂蚁在运动过程中，不但能够在它所经过的路径上留下该物质，而且能够感知这种物质的存在及其强度，并朝着该物质强度高的方向移动，以此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈现象。在一定时间内较短路径通过的蚂蚁要多于较长路径，而某一路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大。,下图是一个形象化的图示，用以说明蚁群的路径搜索过程,蚂蚁觅食协作本质可概括成如下三点：路径概率选择机制：信息素踪迹越浓的路径，被选中的概率越大；信息素更新机制：路径越短，路径上的信息素踪迹增长得越快；协同工作机制：蚂蚁个体通过信息素进行信息交流。,蚂蚁算法采用人工蚂蚁模拟自然界蚂蚁的寻径方式，每个人工蚂蚁的行为符合下列规律,基于TSP的基本蚁群算法的数学模型,以TSP为例说明 Dorigo等人提出的蚂蚁系统(Ant System)模型,其目标函数是：,模型中会用到的变量:,在 t 时刻蚂蚁 k 由城市 i 转移到城市 j的状态转移概率,为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历（也即一个循环结束）后，要对残留信息进行更新处理。t+n时刻在路径(i,j)上的信息量可按照如下规则进行调整。,表示信息素挥发系数，则1-表示信息素残留因子，为了防止信息的无限积累，的取值范围为：含于0,1),根据信息素更新策略的不同，Dorigo M 提出了三种不同的基本蚁群算法模型，分别称之为Ant-Cycle 模型、Ant-Quantity 模型及Ant-Density模型,值的大小表明留在每个结点上的信息量受重视的程度，值越大，蚂蚁选择以前选过的点的可能性越大，但过大会使搜索过早陷入局部最小点,的大小表明启发式信息受重视的程度，越大，表明选择路径时越依赖启发式信息,表示挥发程度的 对收敛结果有很大的影响，实验表明，取值太大或太小，运行结果都不理想，一般取0.5左右,Q值会影响算法的收敛速度，Q过大会使算法收敛于局部最小值，过小又会影响算法的收敛速度，随着问题规模的增大Q的值也需随之变化,蚂蚁算法中 Q、等参数对算法性能有很大影响,基本蚁群算法的程序结构流程,4,改进ACO及TSP求解,蚁群算法的基本步骤：,基本蚁群算法的改进,一系列研究结果发现，用基本蚂蚁算法求解时容易如下出现两个问题：,改进算法中位于第i个结点的蚂蚁k，按以下选择策略移动到结点 j：,改进算法的转移规则,改进的蚁群算法采用确定性选择和随机选择相结合的选择策略，并且在搜索过程中动态调整确定性选择的概率。,改进算法的信息素局部更新规则,其中，称为学习率，称为挥发因子。通过引入蒸发因子，可以做到对过去信息的慢慢遗忘，因而能够强化后来学习得到的知识，这样可以使较少的路径得到更多的访问机会，搜索的范围会更加广，增加蚂蚁选择其它边的概率，防止算法收敛到局部最优解，有利于发现更好解，不致过早出现停滞现象。,局部更新是为了避免所有蚂蚁都选择同一条路径。,改进算法的信息素全局更新规则,在改进的蚁群算法的迭代过程中，全局更新原则只对获得最短路径的蚂蚁实施。当所有蚂蚁均完成一次循环时，信息素更新采用如下规则：,蚁群算法应用实例,以30个城市TSP问题为例，说明蚁群算法的应用。城市的位置信息如表所示：,计算结果,22-2123-25-30-29-9-24-27 26-1-28-6-2-3-5-7-8-4-10-12-11-14-18-19-20-16-17-15-13-22,每次迭代的最短距离与平均距离对比图,结果对比,原文,算法实现,5,CVRP问题及求解,CVRP 问题的蚁群算法实现,在VRP 问题中，每只蚂蚁所构造的回路仅是可行解的一个组成部分，各蚂蚁所构造的回路可能能够组成一些可行解，但也可能一个可行解都得不到。避免无可行解 可采取以下策略：,大蚂蚁数策略：增加算法的蚂蚁数量M，扩大组合范围，从而增加可行解产生的可能性。蚂蚁初始分布均匀策略：在每次迭代前，将蚂蚁随机均匀分布于各个结点，从而增加发现可行解的机会。近似解可行化策略：前两种策略的目的都是为了提高各蚂蚁所构造的子回路组合成可行解的可能性，是一些针对无可行解的“事前”预防性措施。,避免无可行解的策略,CVRP实例仿真,下面通过一个实例，进行仿真试验，检验上述算法的有效性及具体性能。结点数据如下：假设共有19个客户随机分布，配送中心位于坐标点(0,0)，每个客户的需求量由计算机随机产生，车辆限载9t，试验数据如下表所示。,运行过程界面,一次仿真运行的结果,原文结果,多配送中心的车辆路径问题 MDVRP,所谓的多配送中心的车辆路径问题，就是顾客点的配送工作不再仅由一个配送中心发出的车辆完成配送，而是由分散的多个配送中心供给的一种形式。多配送中心的车辆路径问题有以下特点：,1、顾客点分散2、配送中心分散3、一个顾客点可由任一配送中心一次供给满足4、配送中心可服务任意的顾客点群5、衡量配送方案优劣的标准是配送总代价的大小,MDVRP的数学模型,