两个例子---节约里程法.pptVIP

节约法的基本原理 假如由一家配送中心P向两个用户A、B送货，配送中心到两客户的最短距离分别是L1和L2，A和B间的最短距离为L3，AB的货物需求量分别是Q1和Q2，且Q1+Q2小于车辆装载量Q，如下图所示。 A B P L1 L2 L3 图8－1 节约法原理示意图 如果配送中心用两辆汽车分别对A、B两个用户各自往返送货时，汽车行驶的总里程L是 L=2（L1+ L2） 如果用一辆汽车向A、B两个用户巡回送货，则汽车行驶总里程L′为 L′= L1+ L2 + L3 根据三角形的一边之长必定小于另外两边之和的原理，后一种配送方案比前一种方案节约里程△L为 △L=2（L1+ L2）-（L1+ L2 + L3）= L1+ L2 -L3 示例 位于市内的百家姓配送中心（P0）向它旗下的10家连锁商店pi(i=1,2,…,10)配送商品，其配送网络如下图所示。 图中括号内的数字表示每一家连锁店的需求量（t），线路上的数字表示两节点之间的距离（km）。配送中心现有2t和4t车辆可供使用，并且每辆车配送距离不得超过30km。 请为百家姓配送中心制定最优的配送方案。 配送网络图 P0 9 e 1.4 8 6 10 7 6 f 1.5 8 g 0.6 3 2 9 h 0.8 4 i 0.5 10 j 0.6 7 a 0.7 10 b 1.5 9 c 0.8 7 d 0.4 8 5 5 4 4 11 8 百家姓配送中心交通图 配送网络图 P0 e 1.4 8 f 1.5 8 g 0.6 3 h 0.8 4 i 0.5 10 j 0.6 7 a 0.7 10 b 1.5 9 c 0.8 7 d 0.4 8 初始方案：从P点向各点分别派车送货。 初始方案运行结果： 1、从百家姓配送中心出发，需要设计10条配送线路，分别向10家连锁店配送商品； 2、需要10辆2t的配送车辆（每家连锁店的需要量都低于2t），总配送距离为148km。 P 10 9 4 7 9 5 8 14 10 5 8 18 14 9 6 8 18 17 15 13 7 3 13 12 10 11 10 6 4 14 13 11 12 12 8 2 10 11 15 17 18 18 17 11 9 a b c d e f g h i j 7 4 8 13 15 15 15 10 11 8 a b c d e f g h i j 最短距离矩阵 第一步：作出最短距离矩阵，从配送网络图中列出配送中心至用户相互间的最短距离矩阵 。 准备相关资料： 第二步：从最短矩阵中，计算用户相互间的节约里程。 15 8 11 4 7 10 0 3 6 10 0 0 0 3 9 0 0 0 0 1 5 0 0 0 0 0 4 5 9 4 0 0 0 1 2 5 a b c d e f g h i P b c d e f g h i j 13 8 1 0 0 0 0 0 9 节约里程计算过程 准备相关资料： 第三步：将节约里程按大小顺序排列分类。 1 a—b 15 2 a—j 13 3 b—c 11 13 f—g 5 13 g—h 5 13 h—i 5 16 a—d 4 16 b—i 4 16 f—h 4 4 c—d 10 4 d—e 10 6 a—i 9 6 e—f 9 6 i—j 9 9 a—c 8 9 b—j 8 11 b—d 7 12 c—e 6 21 g—i 2 19 b—e 3 19 d—f 3 22 c—j 1 22 e—g 1 22 f—i 1 节约里程排序表 序号 连接点 节约里程 序号 连接点 节约里程 修正初始方案：按节约里程大小顺序，组成配送线路。 P0 J I H G F E D C B A 5 4 7 4 7 8 8 8 3 4 10 （0.7） （1.5） （0.8） （0.6） 线路1：运距27km，4t车一辆 修正结果：运距——109km，车辆——4t1辆，2t6辆 9 10 （0.4） （0.5） 5 修正1套方案：按节约里程大小顺序，组成配送线路。 P0 J I H G F E D C B A 5 4 7 4 7