节约里程法练习答案

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,节约里程法练习答案,练习,1,有一配送中心（,Q,）要向,10,个用户配送，配送距离（公里）和需用量（吨）如下图所示。,假设：采用最大载重量,2,吨、,4,吨、,8,吨三种汽车，并限定车辆一次运行距离,50,公里。,用,节约里程法,选择最佳配送路线和车辆的调度。,配送网络图,Q,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,第一步：选择初始方案：从,Q,点向各点分别派车送货。,P0,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,P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,7,4,8,13,15,15,15,10,11,8,P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,0.7,1.5,0.8,0.4,1.4,1.5,0.6,0.8,0.5,0.6,需要量,最短距离矩阵,第二步：作出最短距离矩阵，从配送网络图中列出配送中心至用户相互间的最短距离矩阵 。,第三步：从最短矩阵中，计算用户相互间的节约里程。,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,P1,P2,P3,P4,P5,P6,P7,P8,P9,P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,13,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,3,XIII,cj,1,XIII,eg,1,XIII,fi,1,节约里程顺序表,分类,用户连接线,节约里程,分类,用户连接线,节约里程,第五步：按节约里程大小顺序，组成配送线路。,d,c,a,e,Q,f,g,h,b,j,i,8,8,8,7,3,4,5,4,4,7,10,初始配送路线图,按上述方法，逐次选代，优化配送线路 。,d,c,a,Q,f,g,h,b,j,i,e,5,5,4,6,7,8,3,7,2,9,10,4,最佳配送线路,练习,2,设一配送中心向,13,个客户配送商品，配送中心及客户间的最短距离如表,1,所示，如果配送的车辆载重为,200,吨，那么利用节约法求解的配送路线的步骤如下：,第一步，计算配送中心到库户间的最短距离，画出距离表。因为本例已给出，所以可以直接进行第二步。,表,1,配送中心到客户间的最短距离表,DC,1,2,3,4,5,6,7,8,9,10,11,12,13,1,12,0,2,8,9,0,3,17,8,10,0,4,15,9,8,4,0,5,15,17,9,14,11,0,6,20,23,15,20,16,6,0,7,17,22,13,20,16,5,4,0,8,8,17,9,19,16,11,14,10,0,9,6,18,12,22,20,17,20,16,6,0,10,16,23,14,22,19,9,8,4,8,14,0,11,21,28,18,26,22,11,7,6,13,19,5,0,12,11,22,14,24,21,14,16,12,5,7,9,13,0,13,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=（L,a,+L,b,）L,ab,12：L,1,+L,2,-L,12,=12+8-9=11,13：L,1,+L,3,-L,13,=12+17-8=21,14：L,1,+L,4,-L,14,=12+15-9=18,15：L,1,+L,5,-L,15,=12+15-17=10,16：L,1,+L,6,-L,16,=12+20-23=9,17：L,1,+L,7,-L,17,=12+17-22=7,18：L,1,+L,8,-L,18,=12+8-17=3,19：L,1,+L,9,-L,19,=12+6-18=0,110：L,1,+L,10,-L,1、10,=12+16-23=7,111：L,1,+L,11,-L,1、12,=12+21-28=5,112：L,1,+L,12,-L,1、12,=12+11-22=1,113：L,1,+L,13,-L,1、13,=12+15-27=0,23：L,2,+L,3,-L,23,=8+17-10=15,24：L,2,+L,4,-L,24,=8+15-8=15,25：L,2,+L,5,-L,25,=8+15-9=14,26：L,2,+L,6,-L,26,=8+20-15=13,27：L,2,+L,7,-L,27,=8+17-13=12,28：L,2,+L,8,-L,28,=8+8-9=7,29：L,2,+L,9,-L,29,=8+6-12=2,210：L,2,+L,10,-L,2、10,=8+16-14=10,211：L,2,+L,11,-L,2、11,=8+21-18=11,212：L,2,+L,12,-L,2、12,=8+11-14=5,213：L,2,+L,13,-L,2、13,=8+15-20=3,34：L,3,+L,4,-L,34,=17+15-4=28,35：L,3,+L,5,-L,35,=17+15-14=18,36：L,3,+L,6,-L,36,=17+20-20=17,表,2,节约里程表,序号,路程,节约里程,（,L,a,+L,b,）,L,ab,序号,路程,节约里程,（,L,a,+L,b,）,L,ab,序号,路程,节约里程,（,L,a,+L,b,）,L,ab,1,6,11,34,11,5,10,22,21,11,13,16,2,6,7,33,12,1,3,21,22,8,10,16,3,7,1,1,32,13,11,12,19,23,7,12,16,4,10,11,32,14,4,5,19,24,4,7,16,5,7,10,29,15,4,6,19,25,8,11,16,6,5,6,29,16,1,4,18,26,2,3,15,7,3,4,28,17,3,5,18,27,2,4,15,8,6,10,28,18,12,13,18,28,7,8,15,9,5,7,27,19,10,12,18,29,6,12,15,10,5,11,25,20,3,6,17,第三步，根据节约里程顺序表和配送中心的约束条件，绘制配送路线。其具体步骤如下：首先选择最节约里程的路段（6,11），然后是（6,7），由于配送路线必须包含DC，且每条循环路线上的客户需求量之和要小于200吨，在接下的选择中满足条件的只有路段（11,8），此时载重总量为193吨，因为在余下选择中没有满足条件的客户，所以，第一回合的配送路线为（DC,7,6,11,8,DC）。,按此方法类推，其余的配送路线分别是（DC,1,3,4,DC）、（DC,5,10,12,13,DC）、（DC,2,9,DC）。,总路程为：（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,