车辆路径问题剖析.ppt

* 高开周 * 自仓库开始沿任一方向向外划一直线，沿着顺时针或者逆时针方向旋转该直线与某点相交。同时要考虑如果在某线路上再增加该站点，是否会超过车辆的载货能力？如没有，继续旋转该直线直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力（先使用最大的车辆）。如超过，就去掉最后的站点，并确定路线。最后，从不包括在上一条路线中的站点开始，继续旋转以寻找新路线。直到所有点被安排在路线中； 排定各路线上每个站点的顺序，使行车路线最短。 * 高开周 * 汽车站 1000 4000 2000 3000 2000 2000 2000 1000 2000 2000 3000 3000 停留点提货量数据 汽车站 1000 4000 2000 3000 2000 2000 2000 1000 2000 2000 3000 3000 扫描法解决方案 * 高开周 * 安排车辆运行时间 将所有运输路线首尾相连顺序排列，使车辆的空闲时间最短，就此决定车辆数，并排出配车计划。 * 高开周 * 最优运输计划安排表 1号线 10号线 6号线 9号线 4号线 5号线 8号线 2号线 7号线 3号线 * 高开周 * 单一路线选择 运输线路的选择影响到运输设备和人员的利用，正确地确定合理的运输线路可以缩短运输时间，降低运输成本，因此运输线路的的选择是运输决策的一个重要领域。 运输线路选择问题尽管种类繁多，但我们可以简单划分为单一路线选择和多起讫点路线选择两种类型。 * 高开周 * （一）起讫点不同的单一路线选择问题 对分离的、单个始发点和终点的网络运输路线选择问题，最简单和直观的方法是最短路线法。 网络由节点和线组成，点与点之间由线连接，线代表点与点之间运行的成本（距离、时间或时间和距离加权的组合）。 初始，除始发点外，所有节点都被认为是未解的，即均未确定是否在选定的运输路线上，始发点作为已解的点，计算从原点开始。 * 高开周 * （二）多起讫点路线选择问题 如果有多个货源地可以服务多个目的地，那么我们面临的问题是： 要指定各目的地的供货地、目的地之间的最佳路径。 该问题经常发生在多个供应商、工厂或仓库服务于多个客户的情况下。如果各供货地能够满足的需求数据有限，则问题会更复杂。解决这类问题常常可以运输一类特殊的线性规划算法，即运输方法求解。 利用计算机软件TRANLP（这是LOGWARE软件包内的程序),任何运输方法的软件都能解决该问题. * 高开周 * 供应商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 * 高开周 * 最佳供货计划 至： 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美元。 * 高开周 * （三）起讫点重合的问题 物流管理人员经常会遇到起讫点相同的路径规划问题。 在企业自己拥有运输工具时，该问题是相当普遍的。我们熟悉的例子有：从某仓库送货到零售点然后返回的路线（从中央配送中心送货到食品店或药店）；从零售店到客户本地配送的路线设计（商店送货上门）；校车、送报车、垃圾收集车和送餐车等的路线设计。 这类路径问题是起讫点不同的问题的扩展形式，但是由于要求车辆必须返回起点行程才能结束，这样问题的难度就提高了。 我们的目标是找出途径点的顺序，使其满足必须经过所有点且总出行时间或总距离最短的要求。 * 高开周 * 不好的路线规划—线路交叉 好的路线规划—线路不交叉 * 高开周 * TSP的启发式算法 线路构造