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

1、 于芹作者单位：上海交通大学文献类型：硕士论文基于蚁群算法的物流车辆途径优化问题的研讨01车辆途径规划概述03蚁群算法简介02VRP问题的相关研讨04改良的ACO及TSP求解05CVRP问题及求解Contents目录1车辆途径问题概述车辆途径规划概述 车辆途径调度问题是由 G Dantzig 首先提出的, N Christofides 在后来总结深化。 车辆途径问题VRP，主要处理的是派多少辆车走什么样的道路进展运输的问题。详细来讲，就是给定了相互连通的假设干有货物需求的顾客点，假设干车辆从配送中心出发，完成对一切顾客点的配送义务后回到配送中心，要求所走的道路不能反复，目的是找到最小本钱的配送

2、方案。 根据实践约束条件的差别，车辆途径问题种类千变万化，并各具特征。经典车辆途径问题，其实就是在车辆途径的调度中，仅仅思索最根本的货车载分量约束(或容量约束)的最普通化的运输问题，即有容量约束的车辆途径问题(Capacitated Vehicle Routing Problem。经典VRP要求满足的条件及假设： 经典车辆途径问题CVRP一切的配送车辆以配送中心为起点并最终回到配送中心1每条配送途径上各需求点的需求量之和不超越车辆的载分量。2每个需求点的需求由且仅由一辆车一次送货满足3CVRP的数学模型(1)(2)(3)(4)(5)(6)k：第k辆车 ：运输车辆的数量 ：车辆k所走的途径的集合

3、带时间窗的车辆途径问题VRPTW 在很多时候，会要求在一定时间范围内到达顾客点(当然有时配送中心也有时间范围限制)，否那么将因停车等待或配送延迟而产生损失。比较而言，时间窗VRP除了必需实现经典 VRP 的要求，还要思索访问时间的限制，这样才干找到合理方案。 软时间窗VRP：要求竟能够在时间窗内到达访问硬时间窗VRP：必需在时间窗内到达访问VRPTW 的数学模型2VRP问题的相关研讨对VRP问题的相关研讨求解问题的精确算法分支定界法Laporte等人利用VRP和其松弛形式T-VRP之间的关系,把T-VRP转化成了TSP的分枝定界算法求解了一般问题动态规划算法将VRP问题视为一个n阶段的决策问题

4、,进而将其转化为依次求解n个具有递推关系的单阶段决策问题.Eilon通过递归的形式利用动态规划法求解具有固定车辆数的VRP问题三下标车辆流方程由Fisher等人提出,用以求解带能力约束、时间窗口以及无停留时间的VRP问题。在该方程中,两个下标表示弧或边,另一个下标表示车辆的序号。二下标车辆流方程Laporte提出了用以求解对称的一般VRP问题,结合了爬山法的思想,核心依然是线性规划。求解问题的元启发式算法禁忌搜索算法由Glover在1986年提出，是一种全局逐步寻优算法,此算法采用禁忌搜索表纪录已达到过的局部最优点,在下一次搜索中对于禁忌表中的节点有选择或是不再选择，以此来避免陷入局部最优解。

5、Gendrean最先用此法解决VRP问题模拟退火算法解决VRP问题时，将物理退火中原子获得的能量相当于分配最优节点，将原子震动模拟为线路寻优空间的随机搜索。（Laporte和Teodorovic）遗传算法Berger和Barkaoui（2004）利用并行混合遗传算法求解带时间窗的车辆路径问题。郎茂祥通过构建单亲遗传算法,有效改进了传统遗传算法对复杂问题搜索效率低,易陷入过早收敛的缺陷。蚁群算法Bullnheimer B.等人首先将蚁群算法的思想用于VRP问题。Bell John.E等提出一种改进的蚁群算法用来求解VRP。Alberbo V等人改进蚁群算法求解TDVRP。刘志硕等人构造了求解的自

6、适应蚁群算法。3蚁群算法简介蚁群算法简史2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改良算法的提出，运用领域更广 引起学者关注，在运用领域得到拓宽ACO初次被系统的提出自然界中真实蚁群集体行为蚁群算法简史蚁群算法Ant Algorithm)是一种由自然界真实蚂蚁寻食行为提炼而成的优化算法，于1991年，由意大利学者Macro Dorigo在其博士论文中提出，并胜利的处理了游览商TSP问题。1996年,Macro Dorigo等人在上发表了Ant system:optimization by a colony of cooperating agents一文，系统地

7、论述了蚁群算法的根本原理和数学模型，蚁群算法逐渐引起了世界许多国家研讨者的关注，其运用领域也得到了迅速拓宽。1998年10月在比利时布鲁塞尔召开了第一届蚁群算法国际研讨会ANTS，标志着蚁群算法的正式国际化。2000年，Marco Dorigo和Bonabeau E等人在国际顶级学术刊物上发表了蚁群算法的研讨综述，从而把这一领域的研讨推向了国际数学的最前沿。在我国，最早关于蚁群算法的研讨见于1997年10月张纪会与徐心和发表的论文“一种新的进化算法蚁群算法中。蚁群算法简史蚁群算法的研讨现状 目前，人们对蚁群算法的研讨曾经由当初的TSP领域浸透到多个运用领域，由处理一维静态优化问题开展到处理多维

8、动态优化组合问题，由离散域范围内研讨逐渐拓展到了延续域范围内研讨。同时在蚁群算法的模型改良以及其他仿生优化算法的交融方面也获得了相当丰富的研讨成果，从而使这种新兴的仿生优化算法展现出前所未有的活力。有学者经过对比实验发现，在组合优化问题中，蚁群算法的优化性能要好于遗传算法等算法。蚁群算法是一种基于种群的启发式搜索算法 。蚁群算法广泛运用于求解TSP问题，Job-Shop调度问题，二次指派问题，背包问题等。 蚁群算法 是一种很有开展前景的优化算法 蚁群算法原理蚁群算法原理 蚂蚁能快速找到最正确寻食途径是由于在蚂蚁个体之间是经过一种称为信息素的物质进展信息传送的。蚂蚁在运动过程中，不但可以在它所经

9、过的途径上留下该物质，而且可以感知这种物质的存在及其强度，并朝着该物质强度高的方向挪动，以此指点本人的运动方向。 因此，由大量蚂蚁组成的蚁群集体行为表现出一种信息正反响景象。在一定时间内较短途径经过的蚂蚁要多于较长途径，而某一途径上走过的蚂蚁越多，那么后来的蚂蚁选择该途径的概率就越大。以下图是一个笼统化的图示，用以阐明蚁群的途径搜索过程蚂蚁寻食协作本质可概括成如下三点： 途径概率选择机制：信息素踪迹越浓的途径，被选中的概率越大； 信息素更新机制：途径越短，途径上的信息素踪迹增长得越快； 协同任务机制：蚂蚁个体经过信息素进展信息交流。蚂蚁算法采用人工蚂蚁模拟自然界蚂蚁的寻径方式，每个人工蚂蚁的行

10、为符合以下规律人工蚂蚁的寻径规律根据途径上的信息素浓度，以相应的概率来选取下一步途径； 01不再选取本人本次循环曾经走过的途径为下一步途径，用一个数据构造( tabu list )来控制这一点；02当完成了一次循环后，根据整个途径长度来释放相应浓度的信息素，并更新走过的途径上的信息素浓度03基于TSP的根本蚁群算法的数学模型以TSP为例阐明 Dorigo等人提出的蚂蚁系统(Ant System)模型,其目的函数是：模型中会用到的变量:在 t 时辰蚂蚁 k 由城市 i 转移到城市 j的形状转移概率 为了防止残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对一切n个城市的遍历也即

11、一个循环终了后，要对残留信息进展更新处置。t+n时辰在途径(i, j)上的信息量可按照如下规那么进展调整。 表示信息素挥发系数，那么1-表示信息素残留因子，为了防止信息的无限积累， 的取值范围为： 含于0,1) 根据信息素更新战略的不同，Dorigo M 提出了三种不同的根本蚁群算法模型，分别称之为Ant-Cycle 模型、Ant-Quantity 模型及Ant-Density模型Ant-Cycle 模型Ant-Quantity模型Ant-Density模型 值的大小阐明留在每个结点上的信息量受注重的程度， 值越大，蚂蚁选择以前选过的点的能够性越大，但过大会使搜索过早堕入部分最小点 的大小阐明

12、启发式信息受注重的程度， 越大，阐明选择途径时越依赖启发式信息表示挥发程度的 对收敛结果有很大的影响，实验阐明，取值太大或太小，运转结果都不理想，普通取0.5左右Q值会影响算法的收敛速度，Q过大会使算法收敛于部分最小值，过小又会影响算法的收敛速度，随着问题规模的增大Q的值也需随之变化蚂蚁算法中 Q 、 、 、 等参数对算法性能有很大影响根本蚁群算法的程序构造流程4改良ACO及TSP求解蚁群算法的根本步骤： 根本蚁群算法的改良 一系列研讨结果发现，用根本蚂蚁算法求解时容易如下出现两个问题： 搜索进展到一定程度后，一切的个体发现的解基木完全一致，出现停滞景象，不能再对解空间进一步搜索，导致能够无法

13、找到全局最优解搜索堕入部分最优解收敛到全局最优解的时间长，求解结果反复在部分最优解和全局最优解之间震荡。时间长 改良算法中位于第i个结点的蚂蚁k，按以下选择战略挪动到结点 j：改良算法的转移规那么 改良的蚁群算法采用确定性选择和随机选择相结合的选择战略，并且在搜索过程中动态调整确定性选择的概率。改良算法的信息素部分更新规那么 其中， 称为学习率， 称为挥发因子。经过引入蒸发因子，可以做到对过去信息的渐渐遗忘，因此可以强化后来学习得到的知识，这样可以使较少的途径得到更多的访问时机，搜索的范围会更加广，添加蚂蚁选择其它边的概率，防止算法收敛到部分最优解，有利于发现更好解，不致过早出现停滞景象。部分

14、更新是为了防止一切蚂蚁都选择同一条途径。改良算法的信息素全局更新规那么 在改良的蚁群算法的迭代过程中，全局更新原那么只对获得最短途径的蚂蚁实施。当一切蚂蚁均完成一次循环时，信息素更新采用如下规那么：蚁群算法运用实例 以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每次迭代的最短间隔与平均间隔对比图结果对比原文算法实现5CVRP问题及求解CV

15、RP 问题的蚁群算法实现VRP 与 TSP 蚁群算法的区别子途径构造过程的区别 在TSP 中，每只蚂蚁均要经过一切结点，而在VRP 中，每只蚂蚁并不需求遍历一切结点。2allowedk 的区别在TSP中，蚂蚁转移时只需思索途径的间隔和信息浓度即可，但在VRP中，蚂蚁转移时不但要思索上述要素，还需求思索车辆容量的限制。 这一差别在算法中的详细表达就是allowedk 确实定问题。1可行解构造的区别 在求解TSP问题中，每只蚂蚁所构造出来的途径均是一个可行解，但在VRP问题中，每只蚂蚁所构造的回路仅是可行解的“零部件3 在VRP 问题中，每只蚂蚁所构造的回路仅是可行解的一个组成部分，各蚂蚁所构造的回路能够可以组成一些可行解，但也能够一个可行解都得不到。防止无可行解 可采取以下战略：大蚂蚁数战略：添加算法的蚂蚁数量M ，扩展组合范围，从而添加可行解产生的能够性。 蚂蚁初始分布均匀战略：在每次迭代前，将蚂蚁随机均匀分布于各个结点，从而添加发现可行解的时机。近似解可行化战略：前两种战略的目的都是为了提高各蚂蚁所构造的子回路组合成可行解的能够性，是一些针对无可行解的“事前预防性措施。防止无可行解的战略CVRP实例仿真 下面经过一个实例，进展仿真实验，检验上述算法的有效性及详细性能。 结点数据如下：假设共有19个客户随机分布，配送中心位