车辆路径问题PPT课件.ppt

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