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

《基于蚁群算法的物流车辆路径优化问题的研究.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、作者：于芹作者单位：上海交通大学文献类型：硕士论文基于蚁群算法的物流车辆路径优化问题的研究01车辆路径规划概述03蚁群算法简介02VRP问题的相关研究04改进的ACO及TSP求解05CVRP问题及求解Contents目录1车辆路径问题概述车辆路径规划概述车辆路径调度问题是由GDantzig首先提出的,NChristofides在后来总结深化。车辆路径问题（VRP），主要解决的是派多少辆车走什么样的路线进行运输的问题。具体来讲，就是给定了相互连通的若干有货物需求的顾客点，若干车辆从配送中心出发，完成对所有顾客

2、点的配送任务后回到配送中心，要求所走的路线不能重复，目的是找到最小成本的配送方案。根据实际约束条件的差异，车辆路径问题种类千变万化，并各具特色。经典车辆路径问题，其实就是在车辆路径的调度中，仅仅考虑最基本的货车载重量约束(或容量约束)的最一般化的运输问题，即有容量约束的车辆路径问题(CapacitatedVehicleRoutingProblem）。经典VRP要求满足的条件及假设：经典车辆路径问题CVRP所有的配送车辆以配送中心为起点并最终回到配送中心1每条配送路径上各需求点的需求量之和不超过车辆的载重量。

3、2每个需求点的需求由且仅由一辆车一次送货满足3CVRP的数学模型(1)(2)(3)(4)(5)(6)k：第k辆车：运输车辆的数量：车辆k所走的路径的集合带时间窗的车辆路径问题VRPTW在很多时候，会要求在一定时间范围内到达顾客点(当然有时配送中心也有时间范围限制)，否则将因停车等待或配送延迟而产生损失。比较而言，时间窗VRP除了必须实现经典VRP的要求，还要考虑访问时间的限制，这样才能找到合理方案。软时间窗VRP：要求竟可能在时间窗内到达访问硬时间窗VRP：必须在时间窗内到达访问VRPTW的数学模型2VRP

4、问题的相关研究对VRP问题的相关研究求解问题的精确算法分支定界法Laporte等人利用VRP和其松弛形式T-VRP之间的关系,把T-VRP转化成了TSP的分枝定界算法求解了一般问题动态规划算法将VRP问题视为一个n阶段的决策问题,进而将其转化为依次求解n个具有递推关系的单阶段决策问题.Eilon通过递归的形式利用动态规划法求解具有固定车辆数的VRP问题三下标车辆流方程由Fisher等人提出,用以求解带能力约束、时间窗口以及无停留时间的VRP问题。在该方程中,两个下标表示弧或边,另一个下标表示车辆的序号。二下

5、标车辆流方程Laporte提出了用以求解对称的一般VRP问题,结合了爬山法的思想,核心依然是线性规划。求解问题的元启发式算法禁忌搜索算法由Glover在1986年提出，是一种全局逐步寻优算法,此算法采用禁忌搜索表纪录已达到过的局部最优点,在下一次搜索中对于禁忌表中的节点有选择或是不再选择，以此来避免陷入局部最优解。Gendrean最先用此法解决VRP问题模拟退火算法解决VRP问题时，将物理退火中原子获得的能量相当于分配最优节点，将原子震动模拟为线路寻优空间的随机搜索。（Laporte和Teodorovic）

6、遗传算法Berger和Barkaoui（2004）利用并行混合遗传算法求解带时间窗的车辆路径问题。郎茂祥通过构建单亲遗传算法,有效改进了传统遗传算法对复杂问题搜索效率低,易陷入过早收敛的缺陷。蚁群算法BullnheimerB.等人首先将蚁群算法的思想用于VRP问题。BellJohn.E等提出一种改进的蚁群算法用来求解VRP。AlberboV等人改进蚁群算法求解TDVRP。刘志硕等人构造了求解的自适应蚁群算法。3蚁群算法简介蚁群算法简史2001年至今1996年-2001年意大利学者Dorigo1991年启发各

7、种改进算法的提出，应用领域更广引起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为蚁群算法简史蚁群算法（AntAlgorithm)是一种由自然界真实蚂蚁觅食行为提炼而成的优化算法，于1991年，由意大利学者MacroDorigo在其博士论文中提出，并成功的解决了旅行商（TSP）问题。1996年,MacroDorigo等人在《IEEE系统、人、控制论汇刊》上发表了”Antsystem:optimizationbyacolonyofcooperatingagents”一文，系统地阐述了

8、蚁群算法的基本原理和数学模型，蚁群算法逐渐引起了世界许多国家研究者的关注，其应用领域也得到了迅速拓宽。1998年10月在比利时布鲁塞尔召开了第一届蚁群算法国际研讨会（ANTS），标志着蚁群算法的正式国际化。2000年，MarcoDorigo和BonabeauE等人在国际顶级学术刊物《Nature》上发表了蚁群算法的研究综述，从而把这一领域的研究推向了国际数学的最前沿。在我国，最早关于蚁群算法的研究见于1997年1