节约里程法基本原理是几何学中三角形一边之长必定小于另外两边之和。往返发货与巡回发货车辆行走距离∆l=[2(l1+l2)]-(l1+l2+l3)=l1+l2-l3。
例题:
已知配送中心P0向5个用户Pj配送货物,其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示,配送中心有3台2t卡车和2台4t两种车辆可供使用。利用节约里程法制定最优的配送方案。
第一步,作运输里程表,列举出配送中心到用户及用户间的最短距离。
第二步,按节约里程公式求出相应的节约里程数。
第三步,将节约里程按从大到小顺序排列。
第四步,根据载重量约束与节约里程大小,顺序连接各客户结点,形成两个配送线。
P2P3-P3P4-P2P4-P4P5-P1P2-P1P5-P1P3-P2P5-P3P5-P1P4
得出结果:
配送线路一:
运量=1.7+0.9+1.4=4t
运行距离=8+4+5+7=24km
用一辆4t车运送,节约距离为18km
配送线路二:
运量=2.4+1.5=3.9t<4t
运行距离=8+10+16=34km
用一辆4t车运送,节约距离为2km
初始方案:配送线路有5条,需要车有5辆,配送的距离=39*2=78km
优化方案:2条配送路线,2辆4t车,配送的距离=24+34=58km
1、节约里程法是用来解决运输车辆数目不确定的问题的最有名的启发式算法。又称节约算法或节约法,可以用并行方式和串行方式来优化行车距离。
2、典型例题:
例题:已知配送中心P0向5个用户Pj配送货物,其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示,配送中心有3台2t卡车和2台4t两种车辆可供使用。利用节约里程法制定最优的配送方案。
第一步,作运输里程表,列出配送中心到用户及用户间的最短距离。
第二步,按节约里程公式求得相应的节约里程数。
第三步,将节约里程按从大到小顺序排列。
第四步,根据载重量约束与节约里程大小,顺序连接各客户结点,形成两个配送线。
P2P3-P3P4-P2P4-P4P5-P1P2-P1P5-P1P3-P2P5-P3P5-P1P4
得出结果:
配送线路一:
运量=1.7+0.9+1.4=4t
运行距离=8+4+5+7=24km
用一辆4t车运送,节约距离为18km
配送线路二:
运量=2.4+1.5=3.9t<4t
运行距离=8+10+16=34km
用一辆4t车运送,节约距离为2km
初始方案:配送线路5条,需要车5辆,配送距离=39*2=78km
优化后的方案:2条配送路线,2辆4t车,配送距离=24+34=58km