车辆路径问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高开周,*,铁路,公路,航空,水路,管道,成本,中,中,高,低,很低,速度,快,快,很快,慢,很慢,频率,高,很高,高,有限,连续,可靠性,很好,好,好,有限,很好,可用性,广泛,有限,有限,很有限,专业化,距离,长,中，短,很长,很长,长,规模,大,小,小,大,大,能力,强,强,弱,最强,最弱,不同运输方式的技术和经济运作特征对比,3/6/2026,1,高开周,车辆路径问题,车辆路径问题概念,车辆路径问题的类型,车辆路径问题的方法,车辆路线问题研究现状,3/6/2026,2,高开周,车辆路径问题的概念,车辆路线问题（,VRP,）最早是由,Dantzig,和,Ramser,于,1959,年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，,配送中心,向客户提供货物，由一个车队负责分送货物，,组织,适当的行车路线，目标是使得客户的,需求,得到满足，并能在一定的约束下，达到诸如路程最短、,成本,最小、耗费时间最少等目的。,3/6/2026,3,高开周,车辆路径问题的概念,由此定义不难看出，,旅行商问题,（,Traveling,Saleman,Problem,TSP,）是,VRP,的特例，由于,Gaery,已证明,TSP,问题,是,NP,难题,，因此，,VRP,也属于,NP,难题。,车辆路线问题自,1959,年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和,经济,上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图,1,）：,3/6/2026,4,高开周,车辆路径问题的概念,3/6/2026,5,高开周,车辆路径问题的概念,设有一场站（,depot,），共有,M,辆货车，车辆容量为,Q,，有,N,位,顾客,（,customer,），每位顾客有其需求量,D,。车辆从,场站,出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。,车辆路线的实际问题包括,配送中心配送,、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。,3/6/2026,6,高开周,车辆路径问题的类型,一般而言车辆路线问题大致可以分为以下三种类型（,Ballou,，,1992,）：,1,、相异的单一起点和单一终点。,2,、相同的单一起点和终点。,3,、多个起点和终点。,3/6/2026,7,高开周,车辆路径问题的方法,数学解析法,（,Exact Procedure,）；,人机互动法,（,Interactive Optimization,）；,先分群再排路线,（,Cluster FirstRoute Second,）；,先排路线再分群,（,Route FirstCluster Second,）；,节省法,或,插入法,（,Saving or Insertion,）；,改善或交换法,（,Improvement or Exchanges,）；,数学规划近似法,（,Mathematical programming,）。,3/6/2026,8,高开周,数学解析法,最佳解法,又称“精确解法”、数学解析法，就是标准的”最佳化法”，将车辆配送问题，通过严谨的,数学模型,或计算机数据结构规划，利用数学法则或数据结构搜寻的方式，求得问题的解,1,。,3/6/2026,9,高开周,数学解析法,常见的有,:,分枝界限法,（,Branch and Bound,）、,整数规划法,（,Integer Programming,）、,动态规划法,（,Dynamic Programming,）。,3/6/2026,10,高开周,数学解析法,1,、分枝界限法把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。,2,、整数规划法在数学模式中加入变量必须为整数的限制式，将问题列出目标方程序以及限制式来求解，能够将实际情形化做限制条件加入模式中，让一般人较容易理解及方便使用。这个解法会随限制式的增加而趋于复杂，使得演算复杂度大为提高。,3/6/2026,11,高开周,数学解析法,3,、动态规划法主要是将一个大问题分解成几个小问题来求解，以反向工作的方式，求解路径中连接两点的最短距离，但是动态规划法缺乏效率，比较适合小问题和批次问题。,Bodin,（,1983,）等人同时也指出，此类方法虽然可以求得最佳解，但其求解范围太小，当需求点数目大于,25,时便无法使用。,3/6/2026,12,高开周,人机互动法,人机互动法是利用人的经验和计算机的运算所合成的方法，而根据,Bodin(1983),等人的描述，人机互动法是一种将人的反应能力，纳入问题求解过程的一般性解法。其具备人的实际情况和计算机强力的计算能力等综合优势，这种方法是先将使用者或是规划者的规划直觉、经验、及能力纳入求解的重要因子，并数据话统整后交由计算机依一定的公式来运算其派车路线的最佳解，并在获得路线的解只后再重新由使用者依据现实层面的考虑因素进行修改更正。,3/6/2026,13,高开周,先分群再排路线,2,4,6,5,7,1,3,8,0,3/6/2026,14,高开周,先排路线再分群,2,4,6,5,7,1,3,8,0,3/6/2026,15,高开周,节省法,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,3/6/2026,16,高开周,1.,线路内路线交换或节点交换,2.,路线间部分线路交换,3.,路线间节点交换,改善或交换法,3/6/2026,17,高开周,车辆路线问题研究现状,经过几十年的研究发展，车辆路线问题研究取得了大量成果。下面从车辆路线问题的现有研究型态和求解方法两个方面介绍车辆路线问题的研究现状。,3/6/2026,18,高开周,车辆路线问题研究现状,车辆路线问题型态,在基本车辆路线问题（,VRP,）的基础上，车辆路线问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括,时窗限制车辆路线问题,（,vehicle routing problems with time windows,，,VRPTW,）、,追求最佳服务时间的车辆路线问题,（,VRPDT,）、,多车种车辆路线问题,（,fleet size and mix vehicle routing problems,，,FSVRP,）、,3/6/2026,19,高开周,车辆路线问题研究现状,车辆多次使用的车辆路线问题,（,vehicle,routingproblems,with multiple use of vehicle,，,VRPM,）、,考虑收集的车辆路线问题,（,vehicle,routingproblems,with backhauls,，,VRPB,）、,随机需求车辆路线问题,（,vehicle routing problem with stochastic demand,，,VRPSD,）等。,3/6/2026,20,高开周,车辆路线问题研究现状,求解方法,综合过去有关车辆路线问题的求解方法，可以分为,精确算法,（,exact algorithm,）与,启发式解法,（,heuristics,），其中精密算法有,分支界限法,、,分支切割法,、,集合涵盖法,等；启发式解法有,节约法,、,模拟退火法,、,确定性退火法,、,禁忌搜寻法,、,基因算法,、,神经网络,、,蚂蚁算法,等。,3/6/2026,21,高开周,车辆路线问题研究现状,1995,年，,Fisher,曾将求解车辆路线问题的算法分成三个阶段。第一阶段是从,1960,年到,1970,年，属于简单启发式方式，包括有各种局部改善启发式算法和贪婪法（,Greedy,）等；第二阶段是从,1970,年到,1980,年，属于一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合涵盖法；第三阶段是从,1990,开始至今，属于较新的方法，包括利用严谨启发式方法、人工智能方法等。,3/6/2026,22,高开周,【,例,】,有一条公路,A,D,，,全长,400km,，,其中,B,、,D,为煤炭供应点，以三角形表示；,A,、,C,为煤炭的销售点，以矩形表示，各站点煤炭供应数量及站点距离如下图所示。,试问如何组织更为合理？,100km,100km,200km,A,D,-3000t,-500t,500t,3000t,物流实例,3/6/2026,23,高开周,A,D,B,C,3000t,500t,甲,方案,A,D,B,C,2500t,乙方案,500t,500t,3/6/2026,24,高开周,物流实例,假设某公司在甲地至乙地之间具有比较稳定的货流量。该企业的物流管理人员面临这样两种抉择：一方面，第三方物流服务公司按平均的市场价格进行了报价：吨公里,0.45,元。甲地至乙地距离计为,1500,公里，每趟运载能力为,10,吨，因此，每趟（,10,吨）报价为,6750,元（,0.45%,1500,1O,，,含所有的装卸费用）。同时，对于往返运输的回程，则按单程报价的,50,计算。而另一方面，该公司的管理人员也在考虑自己投资买车、配备司机、建自己的车队。他们进行了测算，投资购买一辆普通加长（,10,吨）卡车，并改装成厢式货车，一次性投资为人民币,20,万元。每辆车配备两名司机（按正式员工录用，并享受所有人事方面的福利），运营中的固定和可变成本见表,1,（,next,）,3/6/2026,25,高开周,3/6/2026,26,高开周,他们再将每月的运输总支出，根据运送的次数进行了计算，并对单程与往返、自营与外包进行了比较，见表,2,。,结果发现，不论是以单程还是以往返计算，如果货流量足以使运送次数保持在,3,趟或以上，自营将比,“,外包,”,更经济。由于自营车辆每辆每月的最大往返次数为,5,趟，所以只有在货流量在,6,7,趟时，对于自营车辆无力运送的部分才可能采取外包。,3/6/2026,27,高开周,成本比较法,某公司欲将产品从座落位置,A,的,工厂运往座落位置,B,的公司自有仓库，年运量,D,为,700,000,件，每件产品的价格,C,为,30,元，每年的存货成本,I,为产品价格的,30,。公司希望选择使总成本最小的运输方式。据估计，运输时间每减少一天，平均库存可以减少,1,。各种运输服务的参数如图。,在途运输的年存货成本为,ICDT/365,，,两端储存点的存货成本各为，但其中,C,值有差别，工厂的储存点,C,为产品的价格，购买者储存点的,C,为产品价格加上运费之和。,问题：选择哪种运输方式的方案最优？,3/6/2026,28,高开周,3/6/2026,29,高开周,制定车辆运行路线,采用扫描法制定行车路线，由两个阶段组成：,将停留点的货运量分配给送货车；,安排停留点在路线上的顺序。,扫描法的步骤：,在地图上或者方格图中确定所有站点（含仓库）的位置；,3/6/2026,30,高开周,自仓库开始沿任一方向向外划一直线，沿着顺时针或者逆时针方向旋转该直线与某点相交。同时要考虑如果在某线路上再增加该站点，是否会超过车辆的载货能力？如没有，继续旋转该直线直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力（先使用最大的车辆）。如超过，就去掉最后的站点，并确定路线。最后，从不包括在上一条路线中的站点开始，继续旋转以寻找新路线。直到所有点被安排在路线中；,排定各路线上每个站点的顺序，使行车路线最短。,3/6/2026,31,高开周,汽车站,1000,4000,2000,3000,2000,2000,2000,1000,2000,2000,3000,3000,停留点提货量数据,汽车站,1000,4000,2000,3000,2000,2000,2000,1000,2000,2000,3000,3000,扫描法解决方案,3/6/2026,32,高开周,安排车辆运行时间,将所有运输路线首尾相连顺序排列，使车辆的空闲时间最短，就此决定车辆数，并排出配车计划。,3/6/2026,33,高开周,最优运输计划安排表,1号线,10,号,线,6,号,线,9,号,线,4,号,线,5,号,线,8,号,线,2,号,线,7,号,线,3,号,线,3/6/2026,34,高开周,单一路线选择,运输线路的选择影响到运输设备和人员的利用，正确地确定合理的运输线路可以缩短运输时间，降低运输成本，因此运输线路的的选择是运输决策的一个重要领域。,运输线路选择问题尽管种类繁多，但我们可以简单划分为,单一路线选择,和,多起讫点路线选择,两种类型。,3/6/2026,35,高开周,（一）起讫点不同的单一路线选择问题,对分离的、单个始发点和终点的网络运输路线选择问题，最简单和直观的方法是最短路线法。,网络由节点和线组成，点与点之间由线连接，线代表点与点之间运行的成本（距离、时间或时间和距离加权的组合）。,初始，除始发点外，所有节点都被认为是未解的，即均未确定是否在选定的运输路线上，始发点作为已解的点，计算从原点开始。,3/6/2026,36,高开周,（二）多起讫点路线选择问题,如果有多个货源地可以服务多个目的地，那么我们面临的问题是：,要指定各目的地的供货地、目的地之间的最佳路径,。,该问题经常发生在多个供应商、工厂或仓库服务于多个客户的情况下。如果各供货地能够满足的需求数据有限，则问题会更复杂。解决这类问题常常可以运输一类特殊的线性规划算法，即运输方法求解。,利用计算机软件,TRANLP,（这是,LOGWARE,软件包内的程序,),任何运输方法的软件都能解决该问题,.,3/6/2026,37,高开周,供应商,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,3/6/2026,38,高开周,最佳供货计划,至：,1 2 3,自：,A 400 0 0,B 200,200,300,C 0 300 0,运送单位总量,1400,最低总成本,14600,美元,对该结果的解释如下：,货运计划：,从供应商,A,运输,400,吨到工厂,1,。,从供应商,B,运输,200,吨到工厂,1,。,从供应商,B,运输,200,吨到工厂,2,。,从供应商,B,运输,300,吨到工厂,3,。,从供应商,C,运输,300,吨到工厂,2,。,该运行线路计划的成本最低，为,14600,美元。,3/6/2026,39,高开周,（三）起讫点重合的问题,物流管理人员经常会遇到起讫点相同的路径规划问题。,在企业自己拥有运输工具时，该问题是相当普遍的。我们熟悉的例子有：从某仓库送货到零售点然后返回的路线（从中央配送中心送货到食品店或药店）；从零售店到客户本地配送的路线设计（商店送货上门）；校车、送报车、垃圾收集车和送餐车等的路线设计。,这类路径问题是起讫点不同的问题的扩展形式，但是由于要求车辆必须返回起点行程才能结束，这样问题的难度就提高了。,我们的目标是找出途径点的顺序，使其满足必须经过所有点且总出行时间或总距离最短的要求。,3/6/2026,40,高开周,不好的路线规划,线路交叉,好的路线规划,线路不交叉,3/6/2026,41,高开周,TSP,的启发式算法,线路构造法,线路改进法,综合法,3/6/2026,42,高开周,TSP,的启发式算法,线路构造法,节约算法,最临近法,几何启发式算法,最小生成树算法,最近插入算法,3/6/2026,43,高开周,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,3/6/2026,44,高开周,TSP,的启发式算法,1,2,3,4,5,6,7,8,1,8,5,9,12,13,12,17,2,8,8,5,17,7,11,14,3,5,8,7,9,10,7,12,4,9,15,7,3,17,11,16,5,12,17,9,3,18,11,15,6,13,7,10,17,18,8,8,7,12,11,7,11,11,8,5,8,17,14,12,16,15,8,5,3/6/2026,45,高开周,TSP,的启发式算法,1-3-4-5-7-8-6-2-1 54,3/6/2026,46,高开周,TSP,的启发式算法,最临近算法,Step1,：取原点,0,作为线路的起点；,Step2,：寻找与上一次加入线路的点距离 最近的点，把此点加入到线路中；,Step3,：重复,Step2,，知道所有点都被考虑,3/6/2026,47,高开周,TSP,的启发式算法,1-3-7-8-6-2-4-5-1 62,3/6/2026,48,高开周,TSP,的启发式算法,最近插入算法,Step1,：取原点,0,作为起点；,Step2,：找到点,a,使,0,到,a,的距离最小，形成,0-,a,-0;,Step3,：在不属于形成环路的点中寻找离线路上的点最近的点,k,;,Step4,：在线路上寻找弧（,i,j,）使,k,插入到,i,和,j,之间的节约值最大,Step5,：返回,step3,，直到得到回路,3/6/2026,49,高开周,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,3/6/2026,50,高开周,排序问题,问题描述：,设有,n,个零件，需在机床,A,B,上加工，以,a,i,b,i,分别表示零件在,A,B,上的加工时间，求,n,个零件在,A,，,B,上的加工顺序，使从开始加工第一个零件起到加工完最后一个零件时刻止，总时间最小？,3/6/2026,51,高开周,排序问题,最有排序规则：,1,）取时间矩阵中最小元素，如果该元素所对应的机床为,A,机床，则优先加工此零件，反之，若该元素所对应的机床为,B,机床，则将所对应的零件放在最后。,2,）如果两个零件分别在,A,，,B,机床上加工所耗用的时间相等，则优先加工,A,机床上的零件，,B,机床上的零件加工顺序处于较靠后位置。,3/6/2026,52,高开周,排序问题,1,2,3,4,5,A,2,6,5,3,8,B,6,7,3,4,5,3/6/2026,53,高开周,排序问题,1-4-2-5-3 27,3/6/2026,54,高开周,