最短路与节约里程法.ppt

V5 例如 从上图中找出V1与V8之间的最短路线 V2 V1 V4 V6 V7 V9 V8 V3 1 6 3 1 2 2 6 2 6 3 4 10 2 4 3 1 最短路与最大流 起点 终点 例题1 标号算法 解 从终点开始逐步逆向推算 与终点V8联接的结点有三个 即结点V9 V5和V7 V9到结点V8的最短线路为3 记为 9 8 3 V5到结点V8的最短线路为6 记为 5 8 6 V7到结点V8的最短线路为4 记为 7 8 4 V5 V2 V1 V4 V6 V7 V9 V8 V3 1 6 3 1 2 2 6 2 6 3 4 10 2 4 3 起点 终点 结点V6 V6至V7再至终点的最短里程为2十4 6 V6至V5再至终点的最短里程为4十6 10 6 10 所以V6 至终点V8的最短里程为6 记为 6 7 8 6 V5 V2 V1 V4 V6 V7 V9 V8 V3 1 6 3 1 2 2 6 2 6 3 4 10 2 4 3 终点 结点V4 V4至V5再至终点的最短里程为6十6 12 V4至V6再至终点的最短里程为10十6 16 12 16 所以V4至终点的最短里程为12 记为 4 5 8 12 V5 V2 V1 V4 V6 V7 V9 V8 V3 1 6 3 1 2 2 6 2 6 3 4 10 2 4 3 终点 结点V2 V2至V5再至终点的最短里程为1十6 7 记为 2 5 8 7 V5 V2 V1 V4 V6 V7 V9 V8 V3 1 6 3 1 2 2 6 2 6 3 4 10 2 4 3 终点 结点V3与V3联接的结点有V2和V4两个 V3至V2再至终点的最短里程为2十7 9 V3至V4再至终点的最短里程为2十12 14 9 12 所以V3至终点的最短里程为9 记为 3 2 5 8 9 V5 V2 V1 V4 V6 V7 V9 V8 V3 1 6 3 1 2 2 6 2 6 3 4 10 2 4 3 终点 结点V1 V1至V2再至终点的最短里程为6十7 13 V1至V3再至终点的最短里程为3十9 12 V1至V4再至终点的最短里程为1十12 13 12 13 所以V1至终点的最短里程为12 记为 1 3 2 5 8 9 V5 V2 V1 V4 V6 V7 V9 V8 V3 1 6 3 1 2 2 6 2 6 3 4 10 2 4 3 终点 例题2要把A市的一批货物运送到B市 根据两个城市之间可选择的行车路线地图 绘制了图5 13的公路网络 要求寻找一条线路最短的运输路线 图中为结点 代表起点 目的地和与行车路线相交的其他城市 其中的数字为结点编号 箭头为分支 代表两个结点之间的公路 箭头上标明的数字为运输里程 公路网络 1 解 从终点开始逐步逆向推算 1 与终点10联接的结点有两个 即结点9和8 从结点9到结点10只有一条线路 该线路为最短线路 长度100 记为 9 10 100 同样 结点8到结点10的最短线路为150 记为 8 10 150 2 结点6 与6联接的只有一个结点9 6至9的最短里程为200 而9至终点10的最短里程为100 因此6至终点10的最短里程为200十100 300 记为 6 9 10 300 3 结点5 与5联接的结点有9 8两个 5至9再至终点的最短里程为400十100 500 5至8再至终点的最短里程为250十155 400 400 500 所以5至终点的最短里程为400 记为 5 8 10 400 4 结点7 至终点的最短里程为125十150 275 记为 7 8 10 275 300 5 结点4 与4联接的结点有5 6 7三个 结点4至6再到终点的最短里程为200十300 500 结点4至5再到终点的最短里程为175十400 575 结点4至7再到终点的最短里程为275十275 550 三个里程中以500为最小 所以结点4至l0的最短里程记为 4 6 9 10 500 6 结点2和3 用同样的方法 得到 结点2到终点的最短里程为600 记为 2 6 9 10 600 结点3到终点的最短里程为575 记为 3 7 8 10 575 5 最后看结点1 结点1可以通过三个结点2 3 4连接到终点 结点1通过结点2再到终点的最短里程100十600 700 路径为 1 2 6 9 10 700 结点1通过结点4再到终点的最短里程150十500 650 路径为 1 4 6 9 10 650 结点1通过结点3再到终点的最短里程175十575 750 路径为 1 3 7 8 10 750 以上三个里程中以650为最小 即A币到B市的最短里程 对应的最短路线为 1 4 6 9 10 2 一对多配送的路线优化问题一对多配送是指由一个配送中心向多个客户进行送货 这种配送运输模式要求 同一条线路上所有客户的需求总量不大于一辆车的额定载重量 其基本思路是由一辆车装载所有客户的货物 沿一条优选的线路 依次将货物送到各个客户的货物接收点 既保证客户按时收货 又节约运输费 解决这种模式的优化设计问题可以采用 节约里程 法 二 配送线路的选择和优化的方法 1 节约里程法的基本思想 如下图所示 假设P为配送中心 A和B为客户接货点 各点之间的道路距离分别用a b c表示 比较两种运输路线方案 一种是派两辆车分别向客户A B点送货 总的运输里程为2 a b 另一种是将A B两地的货物装在同一辆车上 采用巡回配送方式 即从P出发经由A到B 再返回 总的运输里程为a b c 若不考虑道路特殊情况等因素的影响 第二种方式与第一种方式运输距离之差为2 a b a b c a b c 基本原理是几何学中三角形一边之长必定小于另外两边之和a b c 0 第一步 计算配送中心到库户间的最短距离 画出距离表 第一步 计算配送中心到库户间的最短距离 画出距离表 如表7 22 D 第二步 根据表7 22计算各用户的节约里程 得出结果计算距离 A B的节约里程为 pa pb ab 5 8 4 9 请你计算以下几个点 c d的节约里程 e f的节约里程f g的节约里程 第三步 对节约里程按照大小顺序进行排序 得出以下结果 第四步 根据节约里程排序表和配送车辆载重量及行驶里程等约束条件 逐步求出最优配送路线 1 初始解 从P向各个用户配送 共有9条路线 总的运行距离为136开门 需要2t汽车7辆 5t汽车2辆 如图7 8所示 2 二次解 按照节约里程的大小顺序连接F G F H G H 由于G和H已经在一条配送线路中 因而不再连接G H 如图所示配送路线为7条 需要2t汽车5辆 5t车2辆 节约里程是F G F H的和17 17 34km 总运行距离为136 34 102km 4 7 91km 83km 节约里程法计算 例 由配送中心P向A I等9个用户配送货物 图中连线上的数字表示公路里程 km 靠近各用户括号内的数字 表示各用户对货物的需求量 t 配送中心备有2t和4t载重量的汽车 且汽车一次巡回走行里程不能超过35km 设送到时间均符合用户要求 求该配送中心的最优送货方案 计算配送中心至各用户以及各用户之间的最短距离 列表得最短距离表 由最短距离表 利用节约法计算出各用户之间的节约里程 编制节约里程表 A B LA LB LAB 11 10 5 16A C LA LC LAC 11 9 10 10A D LA LD LAD 11 6 14 3A E LA LE LAE 11 7 18 0A F LA LF LAF 11 10 21 0A G LA LG LAG 11 10 21 0 节约里程表 根据节约里程表中节约里程多少的顺序 由大到小排列 编制节约里程顺序表 以便尽量使节约里程最多的点组合装车配送 根据节约里程排序表和配车 车辆的载重和容积因素 车辆行驶里程等约束条件 渐进绘出配送路径 路径A 4t车 走行32km 载重量3 7t 路径B 4t车 走行31km 载重量3 9t 路径C 2t车 走行30km 载重量1 8t 总共走行里程93km 共节约里程 16 14 12 8 7 6 63km 本章小结 配送运输管理对降低物流成本 提高物流效率具有重要意义 本章涉及配送车辆的调度 配送车辆积载与配载 配送线路的选择与优化