节约里程法例题.ppt

《节约里程法例题.ppt》由会员分享，可在线阅读，更多相关《节约里程法例题.ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

如下图所示某物流中心的配送网络图。由配送中心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。