节约里程法理解练习答案解析.ppt

节约里程法练习答案,练习1 有一配送中心（Q）要向10个用户配送，配送距离（公里）和需用量（吨）如下图所示。 假设：采用最大载重量2吨、4吨、8吨三种汽车，并限定车辆一次运行距离50公里。 用节约里程法选择最佳配送路线和车辆的调度。,配送网络图,Q,第一步：选择初始方案：从Q点向各点分别派车送货。,最短距离矩阵,第二步：作出最短距离矩阵，从配送网络图中列出配送中心至用户相互间的最短距离矩阵 。,第三步：从最短矩阵中，计算用户相互间的节约里程。,节约里程计算过程,第四步：将节约里程按大小顺序排列分类。,节约里程顺序表,第五步：按节约里程大小顺序，组成配送线路。,按上述方法，逐次选代，优化配送线路 。,练习2,设一配送中心向13个客户配送商品，配送中心及客户间的最短距离如表1所示，如果配送的车辆载重为200吨，那么利用节约法求解的配送路线的步骤如下： 第一步，计算配送中心到库户间的最短距离，画出距离表。因为本例已给出，所以可以直接进行第二步。,表1 配送中心到客户间的最短距离表,第二步，根据最短距离表，利用节约法计算出用户间的节约里程，并由大到小排列，编制节约里程顺序表，如表2所示。 L=（La+Lb）Lab 12：L1+L2-L12=12+8-9=11 13：L1+L3-L13=12+17-8=21 14：L1+L4-L14=12+15-9=18 15：L1+L5-L15=12+15-17=10 16：L1+L6-L16=12+20-23=9 17：L1+L7-L17=12+17-22=7,18：L1+L8-L18=12+8-17=3 19：L1+L9-L19=12+6-18=0 110：L1+L10-L1、10=12+16-23=7 111：L1+L11-L1、12=12+21-28=5 112：L1+L12-L1、12=12+11-22=1 113：L1+L13-L1、13=12+15-27=0,23：L2+L3-L23=8+17-10=15 24：L2+L4-L24=8+15-8=15 25：L2+L5-L25=8+15-9=14 26：L2+L6-L26=8+20-15=13 27：L2+L7-L27=8+17-13=12 28：L2+L8-L28=8+8-9=7 29：L2+L9-L29=8+6-12=2,210：L2+L10-L2、10=8+16-14=10 211：L2+L11-L2、11=8+21-18=11 212：L2+L12-L2、12=8+11-14=5 213：L2+L13-L2、13=8+15-20=3 34：L3+L4-L34=17+15-4=28 35：L3+L5-L35=17+15-14=18 36：L3+L6-L36=17+20-20=17 ,表2 节约里程表,第三步，根据节约里程顺序表和配送中心的约束条件，绘制配送路线。其具体步骤如下：首先选择最节约里程的路段（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,