节约里程法例题ppt课件.pptx

如下图所示某物流中心的配送网络图。由配送中心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 3条路径均符条路径均符合配送中心的约束条件。最后选择的方案是：合配送中心的约束条件。最后选择的方案是：使用使用2 2辆辆4t4t车，车，1 1辆辆2t2t车，行驶里程共车，行驶里程共52km52km。其中：其中：路径路径1 1：4t4t车，载货量车，载货量3.5t3.5t，行驶里程，行驶里程30km30km；路径路径2 2：2t2t车，载货量车，载货量1.5t1.5t，行驶里程，行驶里程16km16km；路径路径3 3：4t4t车，载货量车，载货量3t3t，行驶里程，行驶里程6km6km。