车辆路径问题.ppt

《车辆路径问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、车辆路径问题（VRP）作者：高开周2021/10/2高开周12021/10/2高开周2铁路公路航空水路管道成本中中高低很低速度快快很快慢很慢频率高很高高有限连续可靠性很好好好有限很好可用性广泛有限有限很有限专业化距离长中，短很长很长长规模大小小大大能力强强弱最强最弱不同运输方式的技术和经济运作特征对比2021/10/2高开周3车辆路径问题车辆路径问题概念车辆路径问题的类型车辆路径问题的方法车辆路线问题研究现状2021/10/2高开周4车辆路径问题的概念车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它

2、是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。2021/10/2高开周5车辆路径问题的概念由此定义不难看出，旅行商问题（TravelingSalemanProblem,TSP）是VRP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题。车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，

3、一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图1）：2021/10/2高开周6车辆路径问题的概念2021/10/2高开周7车辆路径问题的概念设有一场站（depot），共有M辆货车，车辆容量为Q，有N位顾客（customer），每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。2021/10/2高

4、开周8车辆路径问题的类型一般而言车辆路线问题大致可以分为以下三种类型（Ballou，1992）：1、相异的单一起点和单一终点。2、相同的单一起点和终点。3、多个起点和终点。2021/10/2高开周9车辆路径问题的方法数学解析法（ExactProcedure）；人机互动法（InteractiveOptimization）；先分群再排路线（ClusterFirst–RouteSecond）；先排路线再分群（RouteFirst–ClusterSecond）；节省法或插入法（SavingorInsertion）；改善或交换法（Improv

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

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

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

8、开周15先分群再排路线2465713802021/10/2高开周16先排路线再分群2465713802021/10/2高开周17节省法213055664445+6-4=786+4-8=25+4-10=-1102021/10/2高开周1