节约算法例题.pdfVIP

例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距

离以及用户之间的距离如下图所示，配送中心有3台2t卡车和2台4t两种车辆可供使用。

利用节约里程法制定最优的配送方案。

第一步，作运输里程表，列出配送中心到用户及用户建的最短距离。

第二步，按节约里程公式求得相应的节约里程数。

第三步，将节约里程按从大到小顺序排列。

第四步，根据载重量约束与节约里程大小，顺序连接各客户结点，形成两个配送线。

得出结果：

配送线路一：

运量=1.7+0.9+1.4=4t

运行距离=8+4+5+7=24km

用一辆4t车运送，节约距离为18km

配送线路二：

运量=2.4+1.5=3.9t4t

运行距离=8+10+16=34km

用一辆4t车运送，节约距离为2km

初始方案：配送线路5条，需要车5辆，配送距离=39*2=78km

优化后的方案：2条配送路线,2辆4t车，配送距离=24+34=58km