节约里程法例题

如下图所示某物流中心的配送网络图。由配送中心P向A、B、C、D、E5个用户配送物品。图中连线上的数字表示运距（km）。图中靠近各用户括号里的数字，表示对货物的需求量（t）。配送中心备有2t和4t载重量的汽车，且汽车一次巡回行驶里程不能超过30km。请用节约算法求解该物流中心满意的配送方案。解：（1）由题意绘制表一最短距离表PABCDEP-831087A-817159B-91110C-713D-6E--ABCDEA-3116B-400C-114D-9E-（2）由上表得表二节约里程表如下：（3）将上表二中数据降序排序得表三：节约里程数额排序表序号路程节约数额1C-D112D-E93A-E64B-C45C-E46A-B37A-C18A-D1（4）配送路线如下：从上图中可以看出，依次确定的3条路径均符合配送中心的约束条件。最后选择的方案是：使用2辆4t车，1辆2t车，行驶里程共52km。其中：路径1：4t车，载货量3.5t，行驶里程30km；路径2：2t车，载货量1.5t，行驶里程16km；路径3：4t车，载货量3t，行驶里程6km。