节约里程法练习答案.ppt

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