节约里程法
节约里程法(Saving Algorithm)
目录 |
什么是节约里程法[1]
节约里程法又称节约算法，是指用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。
节约里程法的基本原理[2]
节约里程法的基本思路如下图,已知O点为配送中心,它分别向用户A和B送货。
设O点到用户A和用户B的距离分别为a和b。用户A和用户B之间的距离为c,现有两种送货方案,如图下(a)和(b)所示。
在上图(a)中配送距离为2(a+b)；图上(b)中,配送距离为a+b+c。对比这两个方案,哪个更合理呢？这就要看哪个配送距离最小,配送距离越小,则说明方案越合理。由上图(a)中的配送距离,减去图1(b)中的配送距离可得出:
2(a+b)－(a+b+c)=(2a+2b)－a－b－c=a+b－c(1)
如果把上图(b)看成一个三角形,那么a、b、c则是这个三角形三条边的长度。由三角形的几何性质可知,三角形中任意两条边的边长之和,大于第三边的边长。因此,可以认定(1)式中结果是大于零的。
即:a+b－c＞0(2)
由(2)式可知,(b)方案优于(a)方案,节约了(a+b-c)的里程,这种分析方案的优劣式的思想,就是节约里程法的基本思想。
节约里程法核心思想[1]
节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。
节约里程法的应用[2]
1.基本资料介绍
①宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优化方法。公司客户分布在全国各地,这里主要以广东省内7家客户及省外一家特殊客户的一次配送为例。
城市和货运量
| 客户(i) | 东莞 | 江门 | 惠州 | 阳江 | 汕尾 | 揭阳 | 汕头 | 漳州 |
| 货运量(qi) | 4.3 | 1.8 | 0.7 | 2.2 | 3.6 | 3.6 | 1.6 | 2 |
②广州配送中心为这次配送提供了三种车型,载重量分别为2吨、5吨和8吨,不同车型的运输单价不一样,具体见运输单价表。配送中心的配送是由外协商提供车辆,因此汽车的数量没有限制。
运输单价表
| 车辆载重 | 2T | 5T | 8T |
| 运价(元/公里) | 2.4 | 2.7 | 3.65 |
2.步骤
第一步:各城市之间的距离见上表。
第二步:计算连接城市到同一线路上的距离节约值,具体见下表。
第三步:确定初始方案的运输线路及运输费用,现安排4辆2吨、4辆5吨的车给每个客户送货。运输线路及运输费用见下表所示。
运输线路及运输费用
| 运输路线 | 车型 | 距离 | 单价 | 运费 |
| 广州-东莞 | 5T | 50 | 2.7 | 135 |
| 广州-江门 | 2T | 53 | 2.4 | 127.2 |
| 广州-惠州 | 2T | 116 | 2.4 | 278.4 |
| 广州-阳江 | 5T | 173 | 2.7 | 467.1 |
| 广州-汕尾 | 5T | 221 | 2.7 | 596.7 |
| 广州-揭阳 | 5T | 333 | 2.7 | 899.1 |
| 广州-汕头 | 2T | 344 | 2.4 | 825.6 |
| 广州-漳州 | 2T | 478 | 2.4 | 1147.2 |
| 合计 | 1768 | 4476.3 |
第四步:进行线路第一次优化。
第一次修改后的车辆调度结果
| 运输路线 | 车型 | 距离 | 单价 | 运费 |
| 广州-东莞 | 5T | 50 | 2.7 | 135 |
| 广州-江门 | 2T | 53 | 2.4 | 127.2 |
| 广州-惠州 | 2T | 116 | 2.4 | 278.4 |
| 广州-阳江 | 5T | 173 | 2.7 | 467.1 |
| 广州-汕尾 | 5T | 221 | 2.7 | 596.7 |
| 广州-揭阳 | 5T | 333 | 2.7 | 899.1 |
| 广州-汕头-漳州 | 5T | 502 | 2.7 | 1355.4 |
| 合计 | 1148 | 3858.9 |
第五步:继续进行线路优化。
第二次修改后的车辆调度结果
| 运输路线 | 车型 | 距离 | 单价 | 运费 |
| 广州-东莞 | 5T | 50 | 2.7 | 135 |
| 广州-江门 | 2T | 53 | 2.4 | 127.2 |
| 广州-惠州 | 2T | 116 | 2.4 | 278.4 |
| 广州-阳江 | 5T | 173 | 2.7 | 467.1 |
| 广州-汕尾 | 5T | 221 | 2.7 | 596.7 |
| 广州-揭阳-汕头-漳州 | 8T | 526 | 3.65 | 1919.19 |
| 合计 | 1139 | 3523.59 |
从表中可以看出,广州-惠州-揭阳-汕头-漳州路线上的总货运量达到7.9吨,再连接任何一个城市都将使货运量超过最高限制(8吨),则不能继续配载,所以可以首先确定的是这一条线路。然后在剩下的东莞、江门、阳江和汕尾重复以上的优化步骤。得到最终配送计划。
第六步:最终方案的确定。
最终修改后的车辆调度结果
| 运输路线 | 车型 | 距离 | 单价 | 运费 |
| 广州-东莞 | 5T | 50 | 2.7 | 135 |
| 广州-江门-阳江 | 5T | 189 | 2.7 | 510.3 |
| 广州-汕尾 | 5T | 221 | 2.7 | 596.7 |
| 广州-惠州-揭阳-汕头-漳州 | 8T | 587 | 3.65 | 2142.55 |
| 合计 | 1047 | 3384.55 |
通过对比初始方案与最终方案可知,通过优化可节约里程(1768-1047)=721(公里),节约成本(4476.3-3384.55)=1091.75(元),仅8家客户的一次配送就节约了物流配送成本1091.75。从这里我们不难明白,中国的物流行业是一座金山。
只有利用先进的管理方法,不断的提高效率,才可能大幅降低整个业务成本。