物流工程——节约里程法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,物流配送,节约里程法,(Saving Algorithm),车辆调度程序法,(Vehicle Scheduling Program:VSP),又称节约算法，是指用来解决运输车辆数目不确定的问题的最有名的启发式算法。,核心思想:,节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。,节约里程法,利用节约法制定出的配送方案除了使配送总吨公里数最小外，还应满足以下条件：,满足所有用户的需求,不使任何一辆车超载,每辆车每天的总运行时间或行驶里程不超过规定的上限；,用户到货时间要求。不得超过规定时间。,节约里程法,P,A,（客户）,B,（客户）,a,b,(,配送中心,),P,A,（客户）,B,（客户）,(,配送中心,),b,a,c,运行距离为：,2a+2b,运行距离为：,a+b+c,节约行程：,a + b,c,节约里程法,例题：已知配送中心,P,0,向,5,个用户,P,j,配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有,3,台,2t,卡车和,2,台,4t,两种车辆可供使用。利用节约里程法制定最优的配送方案。,(1.4),P,0,P,2,P,3,P,4,P,5,P,1,( 2.4 ),( 0.9 ),(1.7,）,(1.5 ),10,12,7,5,12,4,13,6,8,12,16,8,节约里程法,第,1,步：作运输里程表，列出配送中心到用户及用户间的最短距离。,需求量,P,0,P,1,1.5,8,P,1,P,2,1.7,8,12,P,2,P,3,0.9,6,13,4,P,3,P,4,1.4,7,15,9,5,P,4,P,5,2.4,10,16,18,16,12,P,5,节约里程法,第,2,步：按节约里程公式求得相应的节约里程数,需求量,P,0,1.5,8,P,1,1.7,8,12,P,2,4,0.9,6,13,4,P,3,1,10,1.4,7,15,9,5,P,4,0,6,8,2.4,10,16,18,16,12,P,5,2,0,0,5,如：,P,0,P,1,+ P,0,P,2,-P,1,P2,=8+8 -12,=4,节约里程法,第,3,步：将节约里程按从大到小顺序排列,序号,路线,节约里程,1,P,2,P,3,10,2,P,3,P,4,8,3,P,2,P,4,6,4,P,4,P,5,5,5,P,1,P,2,4,6,P,1,P,5,2,7,P,1,P,3,1,8,P,2,P,5,0,9,P,3,P,5,0,10,P,1,P,4,0,节约里程法,第,4,步：根据载重量约束与节约里程大小，顺序连接各客户结点,形成二个配送路线,.,（,1.4,）,P,0,P,2,P,3,P,4,P,5,P,1,（,2.4,）,（,0.9,）,（,1.7,）,(1.5),10,7,6,8,8,4,5,优先考虑节约里程最大的路线，以此类推，如果前面涉及了某些路线，往后就考虑未涉及的路线,P,2,P,3-,P,3,P,4-,P,1,P,5,节约里程法,（,1.4,）,P,0,P,2,P,3,P,4,P,5,P,1,（,2.4,）,（,0.9,）,（,1.7,）,(1.5),10,7,8,8,4,5,配送线路,1,节约里程法,（,1.4,）,P,0,P,2,P,3,P,4,P,5,P,1,（,2.4,）,（,0.9,）,（,1.7,）,(1.5),10,7,8,8,4,5,配送线路,1,配送线路,1,：,运量,= 1.7+0.9+1.4= 4t,运行距离,8,4,5,7,24km,用一辆,4t,车运送,节约距离,=18km,（即,2*21-24,）,配送线路,2:,运量,=2.4+1.5=3.9t4t,运行距离,8,10,16,34km,用一辆,4t,车运送,节约距离,=2km,（即,2*18-34,）,节约里程法,（,1.4,）,P,0,P,2,P,3,P,4,P,5,P,1,（,2.4,）,（,0.9,）,（,1.7,）,(1.5),10,7,6,8,8,初始方案：配送线路,5,条， 需要车,5,辆,配送距离,=392=78KM,节约里程法,初始方案：,配送线路,5,条， 需要车,5,辆,配送距离：,39,2=78KM,优化后的方案：,2,条配送线路，,2,辆,4t,车,配送距离：,24,34,58km,节约里程法,案例：,宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优化方法。公司客户分布在全国各地,这里主要以广东省内7家客户及省外一家特殊客户的一次配送为例。,客户(i),东莞,江门,惠州,阳江,汕尾,揭阳,汕头,漳州,货运量(qi),4.3,1.8,0.7,2.2,3.6,3.6,1.6,2,节约里程法,广州配送中心为这次配送提供了三种车型,载重量分别为2吨、5吨和8吨,不同车型的运输单价不一样,具体见运输单价表。配送中心的配送是由外协商提供车辆,因此汽车的数量没有限制,车辆载重 2T5T 8T,运价(元/公里)2.42.73.65,节约里程法,2.步骤,第一步:各城市之间的距离：,节约里程法,第二步,:,计算连接城市到同一线路上的距离节约值,节约里程法,第三步,:,确定初始方案的运输线路及运输费用,现安排,4,辆,2,吨、,4,辆,5,吨的车给每个客户送货。运输线路及运输费用见下表所示。,节约里程法,第四步,:,进行线路第一次优化。,节约里程法,第一次修改后的车辆调度结果：,节约里程法,第五步,:,继续进行线路优化。,节约里程法,第二次修改后的车辆调度结果：,节约里程法,节约里程法,从表中可以看出,广州,-,惠州,-,揭阳,-,汕头,-,漳州路线上的总货运量达到,7.9,吨,再连接任何一个城市都将使货运量超过最高限制,(8,吨,),则不能继续配载,所以可以首先确定的是这一条线路。然后在剩下的东莞、江门、阳江和汕尾重复以上的优化步骤。得到最终配送计划。,节约里程法,第六步,:,最终方案的确定。,节约里程法,最终修改后的车辆调度结果：,节约里程法,通过对比初始方案与最终方案可知,通过优化可节约里程,(1768-1047)=721(,公里,),节约成本,(4476.3-3384.55)=1091.75(,元,),仅,8,家客户的一次配送就节约了物流配送成本,1091.75,。,练习题,某连锁零售店，下设有一个配送中心,P,和,10,个连锁分店,A,J,，配送中心和各连锁分店及各连锁分店之间的位置关系如下图,1,所示，两点间连线上的数字为两点间的路线长度（单位：公里）。各连锁分店对某种商品的需求量见表,1,，该商品由配送中心统一采购并进行配送。配送中心备用,2t,和,4t,的货车，限定送货车辆一次巡回距离不超过,35,公里，设送到时间均符合用户要求，求配送中心的最优送货方案。,图,1,配送网络图,表,1,各连锁分店需求量 重量单位：吨,