节约里程法练习答案课件.ppt

《节约里程法练习答案课件.ppt》由会员分享，可在线阅读，更多相关《节约里程法练习答案课件.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、节约里程法练习答案练习1有一配送中心（Q）要向10个用户配送，配送距离（公里）和需用量（吨）如下图所示。假设：采用最大载重量2吨、4吨、8吨三种汽车，并限定车辆一次运行距离50公里。用节约里程法选择最佳配送路线和车辆的调度。配送网络图Q9e1.4861076f1.58g0.6329h0.84i0.510j0.67a0.710b1.59c0.87d0.485 544118第一步：选择初始方案：从Q 点向各点分别派车送货。P0109 47 9 58 14 10 58 18 14 9 68 18 17 15 13 73 13 12 10 11 10 64 14 13 11 12 12 8 210 1

2、1 15 17 18 18 17 11 9P1P2P3P4P5P6P7P8P9P107 4 8 13 15 15 15 10 11 8P1P2P3P4P5P6P7P8P9P10 0.7 1.50.8 0.4 1.4 1.5 0.60.80.5 0.6需要量最短距离矩阵第二步：作出最短距离矩阵，从配送网络图中列出配送中心至用户相互间的最短距离矩阵。第三步：从最短矩阵中，计算用户相互间的节约里程。158 114 7 100 3 6 100 0 0 3 90 0 0 0 1 50 0 0 0 0 4 59 4 0 0 0 1 2 5P1P2P3P4P5P6P7P8P9P1P2P3P4P5P6P7P8

3、P9P1013 8 1 0 0 0 0 0 9节约里程计算过程第四步：将节约里程按大小顺序排列分类。ab 15 aj 13 bc 11 fg 5 gh 5 hi 5 ad 4 bi 4 fh 4 cd 10 de 10 ai 9 ef 9 ij 9 ac 8 bj 8 bd 7 ce 6 gi 2 be 3 df 3XIII cj 1XIII eg 1XIII fi 1节约里程顺序表分类用户连接线 节约里程分类用户连接线 节约里程第五步：按节约里程大小顺序，组成配送线路。dcaeQfg hbji88873 4544710初始配送路线图按上述方法，逐次选代，优化配送线路。d caQfghbjie

4、5 54678372 9104最佳配送线路练习2设一配送中心向13个客户配送商品，配送中心及客户间的最短距离如表1所示，如果配送的车辆载重为200吨，那么利用节约法求解的配送路线的步骤如下：第一步，计算配送中心到库户间的最短距离，画出距离表。因为本例已给出，所以可以直接进行第二步。表1 配送中心到客户间的最短距离表DC 1 2 3 4 5 6 7 8 9 10 11 12 131 12 02 8 9 03 17 8 10 04 15 9 8 4 05 15 17 9 14 11 06 20 23 15 20 16 6 07 17 22 13 20 16 5 4 08 8 17 9 19 16

5、11 14 10 09 6 18 12 22 20 17 20 16 6 010 16 23 14 22 19 9 8 4 8 14 011 21 28 18 26 22 11 7 6 13 19 5 012 11 22 14 24 21 14 16 12 5 7 9 13 013 15 27 20 30 28 22 23 20 12 9 16 20 8 0需求量 48 36 43 92 57 16 56 30 57 47 91 55 38 第二步，根据最短距离表，利用节约法计算出用户间的节约里程，并由大到小排列，编制节约里程顺序表，如表2所示。L=（La+Lb）Lab12：L1+L2-L12

6、=12+8-9=1113：L1+L3-L13=12+17-8=2114：L1+L4-L14=12+15-9=1815：L1+L5-L15=12+15-17=1016：L1+L6-L16=12+20-23=917：L1+L7-L17=12+17-22=718：L1+L8-L18=12+8-17=319：L1+L9-L19=12+6-18=0110：L1+L10-L1、10=12+16-23=7111：L1+L11-L1、12=12+21-28=5112：L1+L12-L1、12=12+11-22=1113：L1+L13-L1、13=12+15-27=023：L2+L3-L23=8+17-10=1

7、524：L2+L4-L24=8+15-8=1525：L2+L5-L25=8+15-9=1426：L2+L6-L26=8+20-15=1327：L2+L7-L27=8+17-13=1228：L2+L8-L28=8+8-9=729：L2+L9-L29=8+6-12=2210：L2+L10-L2、10=8+16-14=10211：L2+L11-L2、11=8+21-18=11212：L2+L12-L2、12=8+11-14=5213：L2+L13-L2、13=8+15-20=334：L3+L4-L34=17+15-4=2835：L3+L5-L35=17+15-14=1836：L3+L6-L36=17

8、+20-20=17表2 节约里程表序号路程 节约里程（La+Lb）Lab序号 路程 节约里程（La+Lb）Lab序号 路程 节约里程（La+Lb）Lab161134 1151022 2111131626733 121321 22810163 711 32 13111219 23712164101132 144519 244716571029 154619 258111665629 161418 26231573428 173518 272415861028 18121318 28781595727 19101218 29612151051125 203617 第三步，根据节约里程顺序表和配送中

9、心的约束条件，绘制配送路线。其具体步骤如下：首先选择最节约里程的路段（611），然后是（67），由于配送路线必须包含DC，且每条循环路线上的客户需求量之和要小于200吨，在接下的选择中满足条件的只有路段（118），此时载重总量为193吨，因为在余下选择中没有满足条件的客户，所以，第一回合的配送路线为（DC76118DC）。按此方法类推，其余的配送路线分别是（DC134DC）、（DC5101213DC）、（DC29DC）。总路程为：（17+4+7+13+8）+（12+8+4+15）+(15+9+9+8+15)+(8+12+6)=170 原路程为：2（12+8+17+15+15+20+17+8+6+16+21+11+15）=362总共节约里程为：362170=192 或（33+34+16）+（28+21）+（22+18+18）+2=192