《车辆路径问题》PPT课件.ppt

《《车辆路径问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《车辆路径问题》PPT课件.ppt（54页珍藏版）》请在装配图网上搜索。

1、2020/6/20,高开周,1,不同运输方式的技术和经济运作特征对比,2020/6/20,高开周,2,车辆路径问题,车辆路径问题概念 车辆路径问题的类型 车辆路径问题的方法 车辆路线问题研究现状,2020/6/20,高开周,3,车辆路径问题的概念,车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。,2020/6/20,高开周,4,车辆路径问题的概念,由此

2、定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题。 车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图1）：,2020/6/20,高开周,5,车辆路径问题的概念,2020/6/20,高开周,6,车辆路径问题的概念,设有一场站（depot），共有M 辆货车，车辆容量为Q，有N位顾客（customer），每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最

3、后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。 车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。,2020/6/20,高开周,7,车辆路径问题的类型,一般而言车辆路线问题大致可以分为以下三种类型（Ballou，1992）： 1、相异的单一起点和单一终点。 2、相同的单一起点和终点。 3、多个起点和终点。,2020/6/20,高开周,8,车辆路径问题的方法,数学解析法（Exact Procedure）； 人机互动法（Interactive Optimization）；

4、先分群再排路线（Cluster FirstRoute Second）； 先排路线再分群（Route FirstCluster Second）； 节省法或插入法（Saving or Insertion）； 改善或交换法（Improvement or Exchanges）； 数学规划近似法（Mathematical programming）。,2020/6/20,高开周,9,数学解析法,最佳解法又称“精确解法”、数学解析法，就是标准的”最佳化法”，将车辆配送问题，通过严谨的数学模型或计算机数据结构规划，利用数学法则或数据结构搜寻的方式，求得问题的解1。,2020/6/20,高开周,10,数学解析法

5、,常见的有: 分枝界限法（Branch and Bound）、 整数规划法（Integer Programming）、 动态规划法（Dynamic Programming）。,2020/6/20,高开周,11,数学解析法,1、分枝界限法把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。 2、整数规划法在数学模式中加入变量必须为整数的限制式，将问题列出目标方程序以及限制式来求解，能够将实际情形化做限制条件加入模式中，让一般人较容易理解及方便使用。这个解法会随限制式的增加而趋于复杂，使得演算复杂度大为提高。,2020/6/20,高开周,12,数学解析法,3、动态规划法主要是将一个大问题分解

6、成几个小问题来求解，以反向工作的方式，求解路径中连接两点的最短距离，但是动态规划法缺乏效率，比较适合小问题和批次问题。Bodin（1983）等人同时也指出，此类方法虽然可以求得最佳解，但其求解范围太小，当需求点数目大于25时便无法使用。,2020/6/20,高开周,13,人机互动法,人机互动法是利用人的经验和计算机的运算所合成的方法，而根据Bodin(1983)等人的描述，人机互动法是一种将人的反应能力，纳入问题求解过程的一般性解法。其具备人的实际情况和计算机强力的计算能力等综合优势，这种方法是先将使用者或是规划者的规划直觉、经验、及能力纳入求解的重要因子，并数据话统整后交由计算机依一定的公式

7、来运算其派车路线的最佳解，并在获得路线的解只后再重新由使用者依据现实层面的考虑因素进行修改更正。,2020/6/20,高开周,14,先分群再排路线,2,4,6,5,7,1,3,8,0,2020/6/20,高开周,15,先排路线再分群,2,4,6,5,7,1,3,8,0,2020/6/20,高开周,16,节省法,2,1,3,0,5,5,6,6,4,4,4,5+6-4=7,8,6+4-8=2,5+4-10=-1,10,2020/6/20,高开周,17,1.线路内路线交换或节点交换 2.路线间部分线路交换 3.路线间节点交换,改善或交换法,2020/6/20,高开周,18,车辆路线问题研究现状,经过

8、几十年的研究发展，车辆路线问题研究取得了大量成果。下面从车辆路线问题的现有研究型态和求解方法两个方面介绍车辆路线问题的研究现状。,2020/6/20,高开周,19,车辆路线问题研究现状,车辆路线问题型态 在基本车辆路线问题（VRP）的基础上，车辆路线问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括时窗限制车辆路线问题（vehicle routing problems with time windows，VRPTW）、追求最佳服务时间的车辆路线问题（VRPDT）、多车种车辆路线问题（fleet size and mix vehicle routing problems，FSVRP）

9、、,2020/6/20,高开周,20,车辆路线问题研究现状,车辆多次使用的车辆路线问题（vehicle routingproblems with multiple use of vehicle，VRPM）、考虑收集的车辆路线问题（vehicle routingproblems with backhauls，VRPB）、随机需求车辆路线问题（vehicle routing problem with stochastic demand，VRPSD）等。,2020/6/20,高开周,21,车辆路线问题研究现状,求解方法 综合过去有关车辆路线问题的求解方法，可以分为精确算法（exact algorit

10、hm）与启发式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁算法等。,2020/6/20,高开周,22,车辆路线问题研究现状,1995年，Fisher曾将求解车辆路线问题的算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包括有各种局部改善启发式算法和贪婪法（Greedy）等；第二阶段是从1970年到1980年，属于一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合涵盖法；第三阶段是从1990开始至今，属于较新的方法，包括利用严谨启发式方法、人

11、工智能方法等。,2020/6/20,高开周,23,【例】有一条公路AD，全长400km，其中B、D为煤炭供应点，以三角形表示；A、C为煤炭的销售点，以矩形表示，各站点煤炭供应数量及站点距离如下图所示。 试问如何组织更为合理？,物流实例,2020/6/20,高开周,24,2020/6/20,高开周,25,物流实例,假设某公司在甲地至乙地之间具有比较稳定的货流量。该企业的物流管理人员面临这样两种抉择：一方面，第三方物流服务公司按平均的市场价格进行了报价：吨公里0.45元。甲地至乙地距离计为1500公里，每趟运载能力为10吨，因此，每趟（10吨）报价为6750元（ 0.45 %1500 1O，含所有

12、的装卸费用）。同时，对于往返运输的回程，则按单程报价的50计算。而另一方面，该公司的管理人员也在考虑自己投资买车、配备司机、建自己的车队。他们进行了测算，投资购买一辆普通加长（10吨）卡车，并改装成厢式货车，一次性投资为人民币20万元。每辆车配备两名司机（按正式员工录用，并享受所有人事方面的福利），运营中的固定和可变成本见表1 （next）,2020/6/20,高开周,26,2020/6/20,高开周,27,他们再将每月的运输总支出，根据运送的次数进行了计算，并对单程与往返、自营与外包进行了比较，见表2。,结果发现，不论是以单程还是以往返计算，如果货流量足以使运送次数保持在3趟或以上，自营将比

13、“外包”更经济。由于自营车辆每辆每月的最大往返次数为5趟，所以只有在货流量在67趟时，对于自营车辆无力运送的部分才可能采取外包。,2020/6/20,高开周,28,成本比较法,某公司欲将产品从座落位置A的工厂运往座落位置B的公司自有仓库，年运量D为700,000件，每件产品的价格C为30元，每年的存货成本I为产品价格的30。公司希望选择使总成本最小的运输方式。据估计，运输时间每减少一天，平均库存可以减少1。各种运输服务的参数如图。 在途运输的年存货成本为ICDT/365，两端储存点的存货成本各为，但其中C值有差别，工厂的储存点C为产品的价格，购买者储存点的C为产品价格加上运费之和。 问题：选择

14、哪种运输方式的方案最优？,2020/6/20,高开周,29,2020/6/20,高开周,30,制定车辆运行路线,采用扫描法制定行车路线，由两个阶段组成： 将停留点的货运量分配给送货车； 安排停留点在路线上的顺序。 扫描法的步骤： 在地图上或者方格图中确定所有站点（含仓库）的位置；,2020/6/20,高开周,31,自仓库开始沿任一方向向外划一直线，沿着顺时针或者逆时针方向旋转该直线与某点相交。同时要考虑如果在某线路上再增加该站点，是否会超过车辆的载货能力？如没有，继续旋转该直线直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力（先使用最大的车辆）。如超过，就去掉最后的站点，并确定路

15、线。最后，从不包括在上一条路线中的站点开始，继续旋转以寻找新路线。直到所有点被安排在路线中； 排定各路线上每个站点的顺序，使行车路线最短。,2020/6/20,高开周,32,2020/6/20,高开周,33,安排车辆运行时间,将所有运输路线首尾相连顺序排列，使车辆的空闲时间最短，就此决定车辆数，并排出配车计划。,2020/6/20,高开周,34,2020/6/20,高开周,35,单一路线选择,运输线路的选择影响到运输设备和人员的利用，正确地确定合理的运输线路可以缩短运输时间，降低运输成本，因此运输线路的的选择是运输决策的一个重要领域。 运输线路选择问题尽管种类繁多，但我们可以简单划分为单一路线

16、选择和多起讫点路线选择两种类型。,2020/6/20,高开周,36,（一）起讫点不同的单一路线选择问题,对分离的、单个始发点和终点的网络运输路线选择问题，最简单和直观的方法是最短路线法。 网络由节点和线组成，点与点之间由线连接，线代表点与点之间运行的成本（距离、时间或时间和距离加权的组合）。 初始，除始发点外，所有节点都被认为是未解的，即均未确定是否在选定的运输路线上，始发点作为已解的点，计算从原点开始。,2020/6/20,高开周,37,（二）多起讫点路线选择问题,如果有多个货源地可以服务多个目的地，那么我们面临的问题是： 要指定各目的地的供货地、目的地之间的最佳路径。 该问题经常发生在多个

17、供应商、工厂或仓库服务于多个客户的情况下。如果各供货地能够满足的需求数据有限，则问题会更复杂。解决这类问题常常可以运输一类特殊的线性规划算法，即运输方法求解。 利用计算机软件TRANLP（这是LOGWARE软件包内的程序),任何运输方法的软件都能解决该问题.,2020/6/20,高开周,38,供应商B 供给700,供应商A 供给500,供应商c 供给300,工厂1需求量600,工厂2需求量500,工厂3需求量300,1 2 3 A 12 12 14 B 11 11 8 C 15 10 13,2020/6/20,高开周,39,最佳供货计划 至： 1 2 3 自： A 400 0 0 B 200

18、200 300 C 0 300 0 运送单位总量1400 最低总成本14600美元 对该结果的解释如下： 货运计划： 从供应商A运输400吨到工厂1。 从供应商B运输200吨到工厂1。 从供应商B运输200吨到工厂2。 从供应商B运输300吨到工厂3。 从供应商C运输300吨到工厂2。 该运行线路计划的成本最低，为14600美元。,2020/6/20,高开周,40,（三）起讫点重合的问题,物流管理人员经常会遇到起讫点相同的路径规划问题。 在企业自己拥有运输工具时，该问题是相当普遍的。我们熟悉的例子有：从某仓库送货到零售点然后返回的路线（从中央配送中心送货到食品店或药店）；从零售店到客户本地配送

19、的路线设计（商店送货上门）；校车、送报车、垃圾收集车和送餐车等的路线设计。 这类路径问题是起讫点不同的问题的扩展形式，但是由于要求车辆必须返回起点行程才能结束，这样问题的难度就提高了。 我们的目标是找出途径点的顺序，使其满足必须经过所有点且总出行时间或总距离最短的要求。,2020/6/20,高开周,41,不好的路线规划线路交叉,好的路线规划线路不交叉,2020/6/20,高开周,42,TSP的启发式算法,线路构造法 线路改进法 综合法,2020/6/20,高开周,43,TSP的启发式算法,线路构造法 节约算法 最临近法 几何启发式算法 最小生成树算法 最近插入算法,2020/6/20,高开周,

20、44,TSP的启发式算法,节约算法,2,1,3,0,5,5,6,6,4,4,4,5+6-4=7,8,6+4-8=2,5+4-10=-1,10,2020/6/20,高开周,45,TSP的启发式算法,2020/6/20,高开周,46,TSP的启发式算法,1-3-4-5-7-8-6-2-1 54,2020/6/20,高开周,47,TSP的启发式算法,最临近算法 Step1：取原点0作为线路的起点； Step2：寻找与上一次加入线路的点距离 最近的点， 把此点加入到线路中； Step3：重复Step2，知道所有点都被考虑,2020/6/20,高开周,48,TSP的启发式算法,1-3-7-8-6-2-4

21、-5-1 62,2020/6/20,高开周,49,TSP的启发式算法,最近插入算法 Step1：取原点0作为起点； Step2：找到点a使0到a 的距离最小，形成0-a-0; Step3：在不属于形成环路的点中寻找离线路上的点最近的点k; Step4：在线路上寻找弧（i,j）使k插入到i和j之间的节约值最大 Step5：返回step3，直到得到回路,2020/6/20,高开周,50,1-3-2-6-7-8-5-4-1 60 1-3-7-2-6-8-5-4-1 65 1-3-7-8-6-2-5-4-1 61,2020/6/20,高开周,51,排序问题,问题描述： 设有n个零件，需在机床A,B上加工，以ai,bi 分别表示零件在A,B 上的加工时间，求n个零件在A，B上的加工顺序，使从开始加工第一个零件起到加工完最后一个零件时刻止，总时间最小？,2020/6/20,高开周,52,排序问题,最有排序规则： 1）取时间矩阵中最小元素，如果该元素所对应的机床为A机床，则优先加工此零件，反之，若该元素所对应的机床为B机床，则将所对应的零件放在最后。 2）如果两个零件分别在A，B机床上加工所耗用的时间相等，则优先加工A机床上的零件，B机床上的零件加工顺序处于较靠后位置。,2020/6/20,高开周,53,排序问题,2020/6/20,高开周,54,排序问题,1-4-2-5-3 27,