问答题 设配送中心0向7个客户Pi(i=1,…,7)配送货物。从配送中心到客户的距离为d01(j=1,…,7)公里,各客户之间的距离为dij(i=1,…,7;j=1,…,7)公里,如表4-5所示(表中数字单位:公里)。
请用节约法求从配送中心出发配送货物的最短路线。
【正确答案】根据节约法的思想,设节约里程为Sij(i=1,…,4;j=1,…,4),则Sij为i和j两个用户离物流中心距离的之和再减去i和j之间的距离所得的值,即Sij=d0i+d0j-dij。那么S12=d01+d02-d12=9+6-9=6,S13=d01+d03-d13=9+10-16=3,依此类推,可以得到各用户之间的Sij值如表4-6所示。
{{B}}表4-6节约里程表 (单位:公里){{/B}}
  用户1 用户2 用户3 用户4 用户5 用户6 用户7
用户1 S12=6 S13=3 S14=4 S15=15 S16=10 S17=12
用户2   S23=8 S24=9 S25=9 S26=11 S27=11
用户3     S34=19 S35=6 S36=11 S37=11
用户4       S45=8 S46=14 S47=15
用户5         S56=18 S57=23
用户6           S67=25
用户7            
根据表4-6可得节约里程数的大小顺序如表4-7所示。
{{B}}表4-7节约里程数的排序表 (单位:公里){{/B}}
序号 路径 节约公里数(公里) 序号 路径 节约公里数(公里) 序号 路径 节约公里数(公里)
1 6~7 25 8 1~7 12 15 2~5 9
2 5~7 26 9 2~6 11 16 2~3 8
3 3~4 19 10 2~7 11 17 4~5 8
4 5~6 18 11 3~6 11 18 1~2 6
5 1~5 15 12 3~7 11 19 3~5 6
6 4~7 15 13 1~6 10 20 1~4 4
7 4~6 14 14 2~4 9 21 1~3 3
根据节约法的思想,首先选择节约里程数最大的路段,即(6~7),然后是(5~7),接下来依次为(1~5),(1~2),(2~4),(3~4);
因此,其配送路线为:0→6→7→5→1→2→4→3→0;
总路程为:d06+d67+d75+(d51+(d12+d24+d43+d30=13+6+9+8+9+10+4+10=69(公里);
则从配送中心出发的最短配送路线为:配送中心→用户(6)→用户(7)→用户(5)→用户(1)→用户(2)→用户(4)→用户(3)→配送中心;从中心出发最短的配送里程为69公里。
【答案解析】