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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,作者：,于芹,作者单位：上海交通大学,文献类型：硕士论文,基于蚁群算法的物流车辆路径优化问题的研究,01,车辆路径规划概述,03,蚁群算法简介,02,VRP,问题的相关研究,04,改进的,ACO,及,TSP,求解,05,CVRP,问题及求解,Contents,目,录,1,车辆路径问题概述,车辆路径规划概述,车辆,路径调度问题是由,G Dantzig,首先提出的,N Christofides,在后来总结,深化。,车辆路径问题（,VRP,），主要解决的是派多少辆车走什么样的路线进行运输的问题,。具体来讲，就是给定,了相互连通的若干有货物需求的顾客点，若干车辆从配送中心出发，完成对所有顾客点的配送任务后回到配送中心，要求所走的路线不能重复，目的是找到最小成本的配送方案,。,根据,实际约束条件的差异，车辆路径问题种类千变万化，并各具特色。,经典,车辆路径问题，其实就是在车辆路径的调度中，仅仅考虑最基本的货车载重量约束,(,或容量约束,),的最一般化的运输问题，即有容量约束的车辆路径问题,(Capacitated Vehicle Routing,Problem,）,。,经典,VRP,要求满足的条件及,假设：,经典车辆路径问题,CVRP,所有的配送车辆以配送中心为起点并最终回到配送中心,1,每条配送路径上各需求点的需求量之和不超过车辆的载重量。,2,每个需求点的需求由且仅由一辆车一次送货满足,3,CVRP,的数学模型,(1),(2),(3),(4),(5),(6),k,：第,k,辆车,：运输车辆的数量,：车辆,k,所走的路径的集合,带时间窗的车辆路径问题,VRPTW,在很多时候，会要求在一定,时间范围内到达顾客点,(,当然有时配送中心也有时间范围限制,),，否则将因停车等待或配送延迟而产生损失。比较,而言，时间窗,VRP,除了必须实现经典,VRP,的要求，还要考虑访问时间的限制，这样才能找到合理方案,。,软时间窗,VRP,：要求竟可能在时间窗内到达访问,硬时间窗,VRP,：必须在时间窗内到达访问,VRPTW,的数学模型,2,VRP,问题的相关研究,对,VRP,问题的相关研究,求解问题的精确算法,分支定界法,Laporte,等人利用,VRP,和其松弛形式,T-VRP,之间的关系,把,T-VRP,转化成了,TSP,的分枝定界算法求解了一般问题,动态规划算法,将,VRP,问题视为一个,n,阶段的决策问题,进而将其转化为依次求解,n,个具有递推关系的单阶段决策问题,.Eilon,通过递归的形式利用动态规划法求解具有固定车辆数的,VRP,问题,三下标车辆流方程,由,Fisher,等人提出,用以求解带能力约束、时间窗口以及无停留时间的,VRP,问题。在该方程中,两个下标表示弧或边,另一个下标表示车辆的序号。,二下标车辆流方程,Laporte,提出了用以求解对称的一般,VRP,问题,结合了爬山法的思想,核心依然是线性规划。,求解问题的元启发式算法,禁忌搜索算法,由,Glover,在,1986,年提出，是一种全局逐步寻优算法,此算法采用禁忌搜索表纪录已达到过的局部最优点,在下一次搜索中对于禁忌表中的节点有选择或是不再选择，以此来避免陷入局部最优解。,Gendrean,最先用此法解决,VRP,问题,模拟退火算法,解决,VRP,问题时，将物理退火中原子获得的能量相当于分配最优节点，将原子震动模拟为线路寻优空间的随机搜索。（,Laporte,和,Teodorovic,）,遗传算法,Berger,和,Barkaoui,（,2004,）利用并行混合遗传算法求解带时间窗的车辆路径问题。郎茂祥通过构建单亲遗传算法,有效改进了传统遗传算法对复杂问题搜索效率低,易陷入过早收敛的缺陷。,蚁群算法,Bullnheimer,B.,等人首先将蚁群算法的思想用于,VRP,问题。,Bell,John.E,等提出一种改进的蚁群算法用来求解,VRP,。,Alberbo V,等人改进蚁群算法求解,TDVRP,。刘志硕等人构造了求解的自适应蚁群算法。,3,蚁群算法简介,蚁群算法简史,2001,年至今,1996,年,-2001,年,意大利学者,Dorigo1991,年,启发,各种改进算法的提出，应用领域更广,引起学者关注，在应用领域得到拓宽,ACO,首次被系统的提出,自然界中真实蚁群集体行为,蚁群算法简史,蚁群算法（,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,调度问题，二次指派问题，背包问题等。,蚁群算法,是一种很有发展,前景的优化算法,蚁群算法原理,蚁群算法原理,蚂蚁能快速找到最佳觅食路径是因为在蚂蚁个体之间是通过一种称为信息素的物质进行信息传递的。蚂蚁在运动过程中，不但能够在它所经过的路径上留下该物质，而且能够感知这种物质的存在及其强度，并朝着该物质强度高的方向移动，以此指导自己的运动方向。,因此，由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈现象。在一定时间内较短路径通过的蚂蚁要多于较长路径，而某一路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大。,下图是一个形象化的图示，用以说明蚁群的路径搜索过程,蚂蚁觅食协作本质可概括成如下三点,：,路径概率选择机制：信息素踪迹越浓的路径，被选中的概率越大；,信息素更新机制：路径越短，路径上的信息素踪迹增长得越快,；,协同工作机制：蚂蚁个体通过信息素进行信息交流。,蚂蚁算法采用人工蚂蚁模拟自然界蚂蚁的寻径方式，每个人工蚂蚁的行为符合下列规律,人工蚂蚁的寻径规律,根据路径上的信息素浓度，以相应的概率来选取下一步路径；,01,不再选取自己本次循环已经走过的路径为下一步路径，用一个数据结构,(tabu list),来控制这一点；,02,当完成了一次循环后，根据整个路径长度来释放相应浓度的信息素，并更新走过的路径上的信息素浓度,03,基于,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模型,Ant-Cycle,模型,Ant-Quantity,模型,Ant-Density,模型,值的大小表明留在每个结点上的信息量受重视的程度，值越大，蚂蚁选择以前选过的点的可能性越大，但过大会使搜索过早陷入局部最小,点,的大小表明启发式信息受重视的程度，越大，表明选择路径时越依赖启发式信息,表示挥发程度的,对收敛结果有很大的影响，实验表明，取值太大或太小，运行结果都不理想，一般取0.5,左右,Q值会影响算法的收敛速度，Q过大会使算法收敛于局部最小值，过小又会影响算法的收敛速度，随着问题规模的增大Q的值也需随之变化,蚂蚁算法中 Q、等参数对算法性能有很大影响,基本蚁群算法的程序结构流程,4,改进,ACO,及,TSP,求解,蚁群算法的基本步骤：,初始化,路径构造,信息更新,输出结果,基本蚁群算法的改进,一系列,研究结果发现，用基本蚂蚁算法求解时,容易如下出现,两个,问题：,搜索进行到一定程度后，所有的个体发现的解基木完全一致，出现停滞现象，不能再对解空间进一步搜索，导致可能无法找到全局最优解,搜索陷入局部最优解,收敛到全局最优解的时间长，求解结果反复在局部最优解和全局最优解之间震荡。,时间长,改进算法中位于第i个结点的蚂蚁k，按以下选择策略移动到结点 j：,改进算法的转移规则,改进的蚁群算法采用确定性选择和随机选择相结合的选择策略，并且在搜索过程中动态调整确定性选择的概率。,改进算法的信息素,局部更新规则,其中，,称为学习,率，称为挥发因子。,通过,引入蒸发因子，可以做到对过去信息的慢慢遗忘，因而能够强化后来学习得到的知识，这样可以使较少的路径得到更多的访问机会，搜索的范围会更加广，增加蚂蚁选择其它边的概率，防止算法收敛到局部最优解，有利于发现更好解，不致过早出现停滞现象。,局部更新是为了避免所有蚂蚁都选择同一条路径。,改进算法的信息素全局更新规则,在改进的蚁群算法的,迭代过程中，全局更新原则只对获得最短路径的蚂蚁实施。当所有蚂蚁均完成一次循环时，信息素更新采用如下规则：,蚁群算法应用实例,以,30个城市TSP问题为例，说明蚁群算法的应用。城市的位置信息如,表所示：,计算结果,2,2-,21,23,-2,5,-,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 与 TSP 蚁群算法的区别,子路径构造过程的区别 在TSP 中，每只蚂蚁均要经过所有结点，而在VRP 中，每只蚂蚁并不需要遍历所有结点。,2,allowedk 的区别在,TSP,中，蚂蚁转移时只需考虑路径的距离和信息浓度即可，但在,VRP,中，蚂蚁转移时不但要考虑上述因素，还需要考虑车辆容量的限制。这一差异在算法中的具体体现就是,allowedk,的确定问题。,1,可行解结构的区别 在求解TSP问题中，每只蚂蚁所构造出来的路径均是一个可行解，但在VRP问题中，每只蚂蚁所构造的回路仅是可行解的“零部件”,3,在,VRP,