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

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