第3个回答 2019-11-18
节约里程法基本原理是几何学中三角形一边之长必定小于另外两边之和。往返发货与巡回发货车辆行走距离∆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