物流工程-节约里程法.ppt

物流配送——节约里程法(Saving Algorithm)•车辆调度程序法(Vehicle Scheduling Program:VSP)•又称节约算法，是指用来解决运输车辆数目不确定的问题的最有名的启发式算法 核心思想:•节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化优化过程分为并行方式和串行方式两种节约里程法•利用节约法制定出的配送方案除了使配送总吨公里数最小外，还应满足以下条件：– 满足所有用户的需求–不使任何一辆车超载–每辆车每天的总运行时间或行驶里程不超过规定的上限；–用户到货时间要求不得超过规定时间节约里程法PA（客户）B（客户）ab(配送中心)P A（客户）B（客户）(配送中心)bac运行距离为：2a+2b运行距离为：a+b+c节约行程：节约行程：a + b－－c节约里程法例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有3台2t卡车和2台4t两种车辆可供使用利用节约里程法制定最优的配送方案。

1.4)P0P2P3P4P5P1( 2.4 )( 0.9 )(1.7））(1.5 )101275124136812168节约里程法•第第1 1 步：作运输里程表，列出配送中心到用户步：作运输里程表，列出配送中心到用户及用户间的最短距离及用户间的最短距离　需求量P0　P11.58P1P21.7812P2P30.96134P3P41.471595P4P52.41016181612P5节约里程法第第2 2步：按节约里程公式求得相应的节约里程数步：按节约里程公式求得相应的节约里程数需求量P0　1.58P11.7812P240.96134P31101.471595P40682.41016181612P52005如：P0 P1+ P0P2 -P1P2 =8+8 -12 =4节约里程法第第 3 步：将节约里程按从大到小顺序排列步：将节约里程按从大到小顺序排列序号路线节约里程1P2P3102P3P483P2P464P4P555P1P246P1P527P1P318P2P509P3P5010P1P40节约里程法第第4 4步：根据载重量约束与节约里程大小，顺序连接各客户步：根据载重量约束与节约里程大小，顺序连接各客户结点结点, ,形成二个配送路线形成二个配送路线 . .（（1.4））P0P2P3P4P5P1（（2.4））（（0.9））（（1.7））(1.5)10768845优先考虑节约里程最大的路线，以此类推，如果前面涉及了某些路线，往后就考虑未涉及的路线P2P3----P3P4-----P1P5节约里程法（（1.4））P0P2P3P4P5P1（（2.4））（（0.9））（（1.7））(1.5)1078845配送线路1节约里程法（（1.4））P0P2P3P4P5P1（（2.4））（（0.9））（（1.7））(1.5)1078845配送线路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.9t<4t 运行距离＝8＋10＋16＝34km 用一辆 4t车运送 节约距离=2km（即2*18-34）节约里程法（（1.4））P0P2P3P4P5P1（（2.4））（（0.9））（（1.7））(1.5)107688初始方案：配送线路5条， 需要车5辆 配送距离=39×2=78KM 节约里程法•初始方案：初始方案：–配送线路配送线路5 5条，条， 需要车需要车5 5辆辆–配送距离：配送距离：39×2=78KM39×2=78KM•优化后的方案：优化后的方案：–2 2条配送线路，条配送线路，2 2辆辆4t4t车车–配送距离：配送距离：2424＋＋3434＝＝58km58km节约里程法案例：•宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优化方法。

公司客户分布在全国各地,这里主要以广东省内7家客户及省外一家特殊客户的一次配送为例客户客户(i)东莞东莞江门江门惠州惠州阳江阳江汕尾汕尾揭阳揭阳汕头汕头漳州漳州货运量(qi)4.31.80.72.23.63.61.62节约里程法•广州配送中心为这次配送提供了三种车型,载重量分别为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 P和和1010个连个连锁分店锁分店A A～～J J，配送中心和各连锁分店及各连锁分店之，配送中心和各连锁分店及各连锁分店之间的位置关系如下图间的位置关系如下图1 1所示，两点间连线上的数字为所示，两点间连线上的数字为两点间的路线长度（单位：公里）各连锁分店对某两点间的路线长度（单位：公里）各连锁分店对某种商品的需求量见表种商品的需求量见表1 1，该商品由配送中心统一采购，该商品由配送中心统一采购并进行配送配送中心备用并进行配送配送中心备用2t2t和和4t4t的货车，限定送货的货车，限定送货车辆一次巡回距离不超过车辆一次巡回距离不超过3535公里，设送到时间均符合公里，设送到时间均符合用户要求，求配送中心的最优送货方案。

用户要求，求配送中心的最优送货方案图图1 配送网络图配送网络图 表1 各连锁分店需求量 重量单位：吨。