车辆路径问题详解课件.ppt

《车辆路径问题详解课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、车辆路径问题车辆路径问题概念车辆路径问题的方法车辆路线问题研究现状2021/7/281车辆路径问题的概念车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。2021/7/282车辆路径问题的概念由此定义不难看出，旅行商问题（TravelingSalemanProblem,TSP）是V

2、RP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题。车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图1）：2021/7/283车辆路径问题的概念2021/7/284车辆路径问题的概念设有一场站（depot），共有M辆货车，车辆容量为Q，有N位顾客（customer），每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送

3、完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。2021/7/285车辆路径问题的方法数学解析法（ExactProcedure）；人机互动法（InteractiveOptimization）；先分群再排路线（ClusterFirst–RouteSecond）；先排路线再分群（RouteFirst–ClusterSecond）；节省法或插入法（SavingorInsertion）；改善或交换法（Imp

4、rovementorExchanges）；数学规划近似法（Mathematicalprogramming）。2021/7/286数学解析法最佳解法又称“精确解法”、数学解析法，就是标准的”最佳化法”，将车辆配送问题，通过严谨的数学模型或计算机数据结构规划，利用数学法则或数据结构搜寻的方式，求得问题的解1。2021/7/287数学解析法常见的有:分枝界限法（BranchandBound）、整数规划法（IntegerProgramming）、动态规划法（DynamicProgramming）。2021/7/288数学解析法1

5、、分枝界限法把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。2、整数规划法在数学模式中加入变量必须为整数的限制式，将问题列出目标方程序以及限制式来求解，能够将实际情形化做限制条件加入模式中，让一般人较容易理解及方便使用。这个解法会随限制式的增加而趋于复杂，使得演算复杂度大为提高。2021/7/289数学解析法3、动态规划法主要是将一个大问题分解成几个小问题来求解，以反向工作的方式，求解路径中连接两点的最短距离，但是动态规划法缺乏效率，比较适合小问题和批次问题。Bodin（1983）等人同时也指出，此类方法虽然可

6、以求得最佳解，但其求解范围太小，当需求点数目大于25时便无法使用。2021/7/2810人机互动法人机互动法是利用人的经验和计算机的运算所合成的方法，而根据Bodin(1983)等人的描述，人机互动法是一种将人的反应能力，纳入问题求解过程的一般性解法。其具备人的实际情况和计算机强力的计算能力等综合优势，这种方法是先将使用者或是规划者的规划直觉、经验、及能力纳入求解的重要因子，并数据话统整后交由计算机依一定的公式来运算其派车路线的最佳解，并在获得路线的解只后再重新由使用者依据现实层面的考虑因素进行修改更正。2021/7/2

7、811先分群再排路线2465713802021/7/2812先排路线再分群2465713802021/7/2813节省法213055664445+6-4=786+4-8=25+4-10=-1102021/7/28141.线路内路线交换或节点交换2.路线间部分线路交换3.路线间节点交换改善或交换法2021/7/2815车辆路线问题研究现状经过几十年的研究发展，车辆路线问题研究取得了大量成果。下面从车辆路线问题的现有研究型态和求解方法两个方面介绍车辆路线问题的研究现状。2021/7/2816车辆路线问题研究现状车辆路线问题型

8、态在基本车辆路线问题（VRP）的基础上，车辆路线问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括时窗限制车辆路线问题、追求最佳服务时间的车辆路线问题、多车种车辆路线问题、2021/7/2817车辆路线问题研究现状车辆多次使用的车辆路线问题、考虑收集的车辆路线问题、随机需求车辆路线问题等。2021/7/2