B (3)
配送线路1： 运量 = 1+0.5+2= 3.5t 运行距离＝10＋7＋6＋7＝30km 用一辆 4t车运送 节约距离 =30km
配送线路2: 运量=1.5<2t 运行距离＝16km 用一辆 2t车运 送 配送线路3: 运量=3<4t 运行距离＝16km 用一辆 4t车运 送
(2) D C 8 10 (1.5) E 7 P0 (1）
节约里程法
第六步:最终方案的确定。
节约里程法
• 最终修改后的车辆调度结果：
节约里程法
• 通过对比初始方案与最终方案可知,通过优化可节约里程 (1768-1047)=721(公里),节约成本(4476.33384.55)=1091.75(元),仅8家客户的一次配送就节约了物 流配送成本1091.75。
客户(i) 货运量 (qi) 东莞 江门 4.3 1.8 惠州 0.7 阳江 2.2 汕尾 3.6 揭阳 3.6 汕头 1.6 漳州 2
节约里程法
• 广州配送中心为这次配送提供了三种车型,载重量分别为2 吨、5吨和8吨,不同车型的运输单价不一样,具体见运输单 价表。配送中心的配送是由外协商提供车辆,因此汽车的 数量没有限制 • 车辆载重 • 运价(元/公里) 2T 2.4 5T 2.7 8T 3.65
节约里程法
2.步骤 第一步:各城市之间的的距离节约值
节约里程法
第三步:确定初始方案的运输线路及运输费用,现安排4辆2吨、4辆5吨的车给 每个客户送货。运输线路及运输费用见下表所示。
节约里程法
第四步:进行线路第一次优化。
节约里程法
第一次修改后的车辆调度结果：
节约里程法
第五步:继续进行线路优化。
节约里程法
第二次修改后的车辆调度结果：
节约里程法
节约里程法
• 从表中可以看出,广州-惠州-揭阳-汕头-漳州路线上的 总货运量达到7.9吨,再连接任何一个城市都将使货运量超 过最高限制(8吨),则不能继续配载,所以可以首先确定的 是这一条线路。然后在剩下的东莞、江门、阳江和汕尾重 复以上的优化步骤。得到最终配送计划。
节约里程法(Saving Algorithm)
• 车辆调度程序法(Vehicle Scheduling Program:VSP) • 又称节约算法，是指用来解决运输车辆数目不确定的问题 的最有名的启发式算法。 核心思想: • 节约里程法核心思想是依次将运输问题中的两个回路合并 为一个回路，每次使合并后的总运输距离减小的幅度最大， 直到达到一辆车的装载限制时，再进行下一辆车的优化。 优化过程分为并行方式和串行方式两种。
送方案。
(2) D 6 8 10 9 E 7 P0
7
C
(1）
(1.5)
9
A （3）
8
8
3 B (0.5 )
• 第1 步：作运输里程表，列出配送中心到用户及 用户间的最短距离。
需求量
P0
A B C D E
1.5 3 0.5 1 2
8 3 10 8 7
A
8 17 15 9
B
9 11 10
C
7 13
D
6
E
第2步：按节约里程公式求得相应的节约里程数
需求量 P0
1.5
3
8
3
A
8 3 17 B 9 4 11 0 C 7 11 D
0.5
10
0 15
1
8
1
9
2 7 6
10
0
13
4
6
9 E
第3步：将节约里程按从大到小顺序排列
序号 路线 节约里程
1
2 3 4 5 6 7 8 9 10
C-D
D-E A-E C-E B-C A-B A-D A-C B-D B-E
11
9 6 4 4 3 1 0 0 0
第4步：根据载重量约束与节约里程大小，顺序连接 各客户结点,形成二个配送路线。
（1） D 6
7
（ 0.5 ）
C 配送线路1
（2） E 7 10
P0
8
3
A
（ 1.5 ）
B (3)
（1） D 6
7
C 配送线路1
10
（ 0.5 ）
（2） E
7
8
P0
3
A （ 1.5 ）
8
A （3）
3 B (0.5 )
初始方案：配送线路5条， 需要车5辆
配送距离=36×2=72KM
节约里程法
• 初始方案： –配送线路5条， 需要车5辆 –配送距离：36×2=72KM • 优化后的方案： –3条配送线路，2辆4t车, 1辆2t车. –配送距离：30＋8+3＝41km
练习作业题
• 求节约里程法的线路设计，该公司有2T和4T的车，每次 运行的距离不超过60KM,其线路图如下所示：
（ 1.2 ） A 6 15 （ 0.8 ） B 21 10
P
23
7 C （ 1.5 ）
10
D (1.6)
节约里程法
案例： • 宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见 下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优 化方法。公司客户分布在全国各地,这里主要以广东省内7家客户 及省外一家特殊客户的一次配送为例。
P
(配送中心)
b
B（客户）
运行距离为：2a+2b 节约行程：a + b－c
运行距离为：a+b+c
节约里程法 例题：
已知配送中心P0向5个用户A、B、C、D、E、F配送货物，其配
送路线网络、配送中心与用户的距离以及用户之间的距离如下
图所示，配送中心有2t卡车和4t两种车辆可供使用。且汽车一 次巡回行驶的里程不超过30km，利用节约里程法制定最优的配
节约里程法
• 利用节约法制定出的配送方案除了使配送总吨公 里数最小外，还应满足以下条件：
– 满足所有用户的需求 –不使任何一辆车超载 –每辆车每天的总运行时间或行驶里程不超过规定的上 限； –用户到货时间要求。不得超过规定时间。
节约里程法
A（客户）
a a c
A（客户）
P
(配送中心) b
B（客户）