车辆路径问题

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

2、一样数量货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当行车路线，目标是使得客户需求得到满足，并能在一定约束下，到达诸如旅程最短、成本最小、花费时间最少等目标。 车辆路径问题第4页/10/10高开周5车辆路径问题概念 由此定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP特例，因为Gaery已证实TSP问题是NP难题，所以，VRP也属于NP难题。 车辆路线问题自1959年提出以来，一直是网络优化问题中最基本问题之一，因为其应用广泛性和经济上重大价值，一直受到国内外学者广泛关注。车辆路线问题能够描述以下（如图1）： 车辆路径问题第5页

3、/10/10高开周6车辆路径问题概念车辆路径问题第6页/10/10高开周7车辆路径问题概念 设有一场站（depot），共有M 辆货车，车辆容量为Q，有N位用户（customer），每位用户有其需求量D。车辆从场站出发对客户进行配送服务最终返回场站，要求全部用户都被配送，每位用户一次配送完成，且不能违反车辆容量限制，目标是全部车辆路线总距离最小。 车辆路线实际问题包含配送中心配送、公共汽车路线制订、信件和报纸投递、航空和铁路时间表安排、工业废品搜集等。 车辆路径问题第7页/10/10高开周8车辆路径问题类型 普通而言车辆路线问题大致能够分为以下三种类型（Ballou，1992）： 1、相异单一起

4、点和单一终点。 2、相同单一起点和终点。 3、多个起点和终点。 车辆路径问题第8页/10/10高开周9车辆路径问题方法数学解析法（Exact Procedure）； 人机互动法（Interactive Optimization）； 先分群再排路线（Cluster FirstRoute Second）； 先排路线再分群（Route FirstCluster Second）； 节约法或插入法（Saving or Insertion）； 改进或交换法（Improvement or Exchanges）； 数学规划近似法（Mathematical programming）。 车辆路径问题第9页/10/

5、10高开周10数学解析法 最正确解法又称“准确解法”、数学解析法，就是标准”最正确化法”，将车辆配送问题，经过严谨数学模型或计算机数据结构规划，利用数学法则或数据结构搜寻方式，求得问题解1。车辆路径问题第10页/10/10高开周11数学解析法常见有:分枝界限法（Branch and Bound）、整数规划法（Integer Programming）、动态规划法（Dynamic Programming）。车辆路径问题第11页/10/10高开周12数学解析法1、分枝界限法把问题可行解展开如树分枝，再经由各个分枝中寻找最正确解。2、整数规划法在数学模式中加入变量必须为整数限制式，将问题列出目标方程序

6、以及限制式来求解，能够将实际情形化做限制条件加入模式中，让普通人较轻易了解及方便使用。这个解法会随限制式增加而趋于复杂，使得演算复杂度大为提升。车辆路径问题第12页/10/10高开周13数学解析法3、动态规划法主要是将一个大问题分解成几个小问题来求解，以反向工作方式，求解路径中连接两点最短距离，不过动态规划法缺乏效率，比较适合小问题和批次问题。Bodin（1983）等人同时也指出，这类方法即使能够求得最正确解，但其求解范围太小，当需求点数目大于25时便无法使用。 车辆路径问题第13页/10/10高开周14人机互动法 人机互动法是利用人经验和计算机运算所合成方法，而依据Bodin(1983)等人

7、描述，人机互动法是一个将人反应能力，纳入问题求解过程普通性解法。其具备人实际情况和计算机强力计算能力等综合优势，这种方法是先将使用者或是规划者规划直觉、经验、及能力纳入求解主要因子，并数据话统整后交由计算机依一定公式来运算其派车路线最正确解，并在取得路线解只后再重新由使用者依据现实层面考虑原因进行修改更正。 车辆路径问题第14页/10/10高开周15先分群再排路线246571380车辆路径问题第15页/10/10高开周16先排路线再分群246571380车辆路径问题第16页/10/10高开周17节约法213055664445+6-4=786+4-8=25+4-10=-110车辆路径问题第17页

8、/10/10高开周181.线路内路线交换或节点交换2.路线间部分线路交换3.路线间节点交换改进或交换法车辆路径问题第18页/10/10高开周19车辆路线问题研究现实状况 经过几十年研究发展，车辆路线问题研究取得了大量结果。下面从车辆路线问题现有研究型态和求解方法两个方面介绍车辆路线问题研究现实状况。 车辆路径问题第19页/10/10高开周20车辆路线问题研究现实状况车辆路线问题型态 在基本车辆路线问题（VRP）基础上，车辆路线问题在学术研究和实际应用上产生了许多不一样延伸和改变型态，包含时窗限制车辆路线问题（vehicle routing problems with time windows，

9、VRPTW）、追求最正确服务时间车辆路线问题（VRPDT）、多车种车辆路线问题（fleet size and mix vehicle routing problems，FSVRP）、车辆路径问题第20页/10/10高开周21车辆路线问题研究现实状况车辆屡次使用车辆路线问题（vehicle routingproblems with multiple use of vehicle，VRPM）、考虑搜集车辆路线问题（vehicle routingproblems with backhauls，VRPB）、随机需求车辆路线问题（vehicle routing problem with stochast

10、ic demand，VRPSD）等。车辆路径问题第21页/10/10高开周22车辆路线问题研究现实状况求解方法 综合过去相关车辆路线问题求解方法，能够分为准确算法（exact algorithm）与启发式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁算法等。车辆路径问题第22页/10/10高开周23车辆路线问题研究现实状况 1995年，Fisher曾将求解车辆路线问题算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包含有各种局部改进启发式算法和贪婪法（

11、Greedy）等；第二阶段是从1970年到1980年，属于一个以数学规划为主启发式解法，包含指派法、集合分割法和集合涵盖法；第三阶段是从1990开始至今，属于较新方法，包含利用严谨启发式方法、人工智能方法等。 车辆路径问题第23页/10/10高开周24 【例】有一条公路AD，全长400km，其中B、D为煤炭供给点，以三角形表示；A、C为煤炭销售点，以矩形表示，各站点煤炭供给数量及站点距离以下列图所表示。 试问怎样组织更为合理？100km100km200kmAD-3000t-500t500t3000t物流实例车辆路径问题第24页/10/10高开周25ADBC3000t500t甲方案ADBC250

12、0t乙方案500t500t车辆路径问题第25页/10/10高开周26物流实例 假设某公司在甲地至乙地之间具有比较稳定货流量。该企业物流管理人员面临这样两种抉择：一方面，第三方物流服务公司按平均市场价格进行了报价：吨公里0.45元。甲地至乙地距离计为1500公里，每趟运载能力为10吨，所以，每趟（10吨）报价为6750元（ 0.45 %1500 1O，含全部装卸费用）。同时，对于往返运输回程，则按单程报价50计算。而其次，该公司管理人员也在考虑自己投资买车、配备司机、建自己车队。他们进行了测算，投资购买一辆普通加长（10吨）卡车，并改装成厢式货车，一次性投资为人民币20万元。每辆车配备两名司机（

13、按正式员工录用，并享受全部人事方面福利），运营中固定和可变成本见表1 （next）车辆路径问题第26页/10/10高开周27车辆路径问题第27页/10/10高开周28 他们再将每个月运输总支出，依据运输次数进行了计算，并对单程与往返、自营与外包进行了比较，见表2。 结果发觉，不论是以单程还是以往返计算，假如货流量足以使运输次数保持在3趟或以上，自营将比“外包”更经济。因为自营车辆每辆每个月最大往返次数为5趟，所以只有在货流量在67趟时，对于自营车辆无力运输部分才可能采取外包。 车辆路径问题第28页/10/10高开周29成本比较法 某企业欲将产品从座落位置A工厂运往座落位置B企业自有仓库，年运量

14、D为700,000件，每件产品价格C为30元，每年存货成本I为产品价格30。企业希望选择使总成本最小运输方式。据预计，运输时间每降低一天，平均库存能够降低1。各种运输服务参数如图。 在途运输年存货成本为ICDT/365，两端储存点存货成本各为，但其中C值有差异，工厂储存点C为产品价格，购置者储存点C为产品价格加上运费之和。 问题：选择哪种运输方式方案最优？车辆路径问题第29页/10/10高开周30车辆路径问题第30页/10/10高开周31制订车辆运行路线采取扫描法制订行车路线，由两个阶段组成： 将停留点货运量分配给送货车； 安排停留点在路线上次序。扫描法步骤： 在地图上或者方格图中确定全部站点

15、（含仓库）位置；车辆路径问题第31页/10/10高开周32自仓库开始沿任一方向向外划一直线，沿着顺时针或者逆时针方向旋转该直线与某点相交。同时要考虑假如在某线路上再增加该站点，是否会超出车辆载货能力？如没有，继续旋转该直线直到与下一个站点相交。再次计算累计货运量是否超出车辆运载能力（先使用最大车辆）。如超出，就去掉最终站点，并确定路线。最终，从不包含在上一条路线中站点开始，继续旋转以寻找新路线。直到全部点被安排在路线中； 排定各路线上每个站点次序，使行车路线最短。车辆路径问题第32页/10/10高开周33汽车站100040003000100030003000停留点提货量数据汽车站1000400

16、03000100030003000扫描法处理方案车辆路径问题第33页/10/10高开周34安排车辆运行时间 将全部运输路线首尾相连次序排列，使车辆空闲时间最短，就此决定车辆数，并排出配车计划。车辆路径问题第34页/10/10高开周35最优运输计划安排表1号线10号线6号线9号线4号线5号线8号线2号线7号线3号线车辆路径问题第35页/10/10高开周36单一路线选择运输线路选择影响到运输设备和人员利用，正确地确定合理运输线路能够缩短运输时间，降低运输成本，所以运输线路选择是运输决议一个主要领域。运输线路选择问题尽管种类繁多，但我们能够简单划分为单一路线选择和多起讫点路线选择两种类型。车辆路径问

17、题第36页/10/10高开周37（一）起讫点不一样单一路线选择问题对分离、单个始发点和终点网络运输路线选择问题，最简单和直观方法是最短路线法。网络由节点和线组成，点与点之间由线连接，线代表点与点之间运行成本（距离、时间或时间和距离加权组合）。初始，除始发点外，全部节点都被认为是未解，即均未确定是否在选定运输路线上，始发点作为已解点，计算从原点开始。 车辆路径问题第37页/10/10高开周38（二）多起讫点路线选择问题假如有多个货源地能够服务多个目标地，那么我们面临问题是：要指定各目标地供货地、目标地之间最正确路径。该问题经常发生在多个供给商、工厂或仓库服务于多个客户情况下。假如各供货地能够满足

18、需求数据有限，则问题会更复杂。处理这类问题经常能够运输一类特殊线性规划算法，即运输方法求解。利用计算机软件TRANLP（这是LOGWARE软件包内程序),任何运输方法软件都能处理该问题.车辆路径问题第38页/10/10高开周39供给商B 供给700供给商A 供给500供给商c 供给300工厂1需求量600工厂2需求量500工厂3需求量300 1 2 3A 12 12 14B 11 11 8 C 15 10 13车辆路径问题第39页/10/10高开周40最正确供货计划至： 1 2 3自： A 400 0 0 B 200 200 300 C 0 300 0运输单位总量1400最低总成本14600美

19、元对该结果解释以下：货运计划：从供给商A运输400吨到工厂1。从供给商B运输200吨到工厂1。从供给商B运输200吨到工厂2。从供给商B运输300吨到工厂3。从供给商C运输300吨到工厂2。该运行线路计划成本最低，为14600美元。车辆路径问题第40页/10/10高开周41（三）起讫点重合问题物流管理人员经常会碰到起讫点相同路径规划问题。在企业自己拥有运输工具时，该问题是相当普遍。我们熟悉例子有：从某仓库送货到零售点然后返回路线（从中央配送中心送货到食品店或药店）；从零售店到客户当地配送路线设计（商店送货上门）；校车、送报车、垃圾搜集车和送餐车等路线设计。这类路径问题是起讫点不一样问题扩展形式

20、，不过因为要求车辆必须返回起点行程才能结束，这么问题难度就提升了。我们目标是找出路径点次序，使其满足必须经过全部点且总出行时间或总距离最短要求。车辆路径问题第41页/10/10高开周42不好路线规划线路交叉 好路线规划线路不交叉 车辆路径问题第42页/10/10高开周43TSP启发式算法线路结构法线路改进法综正当车辆路径问题第43页/10/10高开周44TSP启发式算法线路结构法 节约算法 最临近法 几何启发式算法 最小生成树算法 最近插入算法车辆路径问题第44页/10/10高开周45TSP启发式算法节约算法 213055664445+6-4=786+4-8=25+4-10=-110车辆路径问题第45页/10/10高开周46TSP启发式算法1234567818591213121728851771114358791071249157317111651217931811156137101718887121171111858171412161585车辆路径问题第46页/10/10高开周47TSP启发式算法1-3-4-5-7-8-6-2-1 54车辆路径问题第47页/10/10高开周48TSP启发式算法最临近算法 Step1：取原点0作为线路起点； Step2：寻找与上一次加入线路点距