19
优选
练习
位于牡丹江市内的百家姓配送中心（P0） 向它旗下的10家连锁商店pi(i=1,2,…,10) 配送商品，其配送网络如下图所示。
图中括号内的数字表示每一家连锁店的需 求量（t），线路上的数字表示两节点之间 的距离（km）。配送中心现有2t和4t车辆 可供使用，并且每辆车配送距离不得超过 30km。
P2P3－ P3P4－P2P4－P4P5－ P1P2－ P1P5－ P1P3 －P2P5 －P3P5－ P1P4
（0.9）
P3
4
（1.7）
P2
5
6
8
（1.4）
P4
7
P0
10
8
P5
（2.4）
15
P1 (1.5)
优选
节约里程法
（0.9）
P3
4
5
（1.4）
P4
配送线路1
7

8
P5
（2.4）
P4 1.4 7 15 9
5
P4
P5 2.4 10 16 18 16 12 P5
12
优选
节约里程法
第2步：按节约里程公式求得相应的节约里程数
需求量 P0
1.5 8
P1
12
1.7 8 4
P2
13 0.9 6
1
4
10
P3
15
9
5
1.4 7 0
6
8
P4
16
18
16
12
2.4 10 2
0
0
5
P5
13
优选
节约里程法
1.满足客户配送需要
2.减少配送车辆使用
3.缓解交通紧张压力
6
优选
节约里程法(Saving Algorithm)
车辆调度程序法(Vehicle Scheduling Program:VSP) 又称节约算法，是指用来解决运输车辆数目不确定的问题
的最有名的启发式算法。
核心思想: 节约里程法核心思想是依次将运输问题中的两个回路合并
适用条件：
1、由配送中心向多位客户开展拼装送货；
2、每位客户的送货量都不能满足配送车辆
满载。 配送效果：
供应商 客户
1.配送车辆满载运输；
2.配送运输路线距离最短。
5
优选
节约里程法的意义
送货时，由一辆车装载所有客户的货物，沿着 一条精心设计的最佳路线依次将货物送到各位客 户手中，这样既保证按时按量将用户需要的货物 及时送达，又节约了车辆，节省了费用，缓解了 交通紧张的压力，并减少了运输对环境造成的污 染。
限； 用户到货时间要求。不得超过规定时间。
8
优选
节约里程法
A（客户）
a
A（客户）
a
c
P
(配送中心)
b
B（客户） P
b
(配送中心)
B（客户）
运行距离为：2a+2b
运行距离为：a+b+c
节约行程：a + b－c
9
优选
节约里程法
例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网 络、配送中心与用户的距离以及用户之间的距离如下图所 示，配送中心有3台2t卡车和2台4t两种车辆可供使用。利 用节约里程法制定最优的配送方案。
为一个回路，每次使合并后的总运输距离减小的幅度最大， 直到达到一辆车的装载限制时，再进行下一辆车的优化。 优化过程分为并行方式和串行方式两种。
7
优选
节约里程法
利用节约法制定出的配送方案除了使配送总吨公里数最小 外，还应满足以下条件：
满足所有用户的需求 不使任何一辆车超载 每辆车每天的总运行时间或行驶里程不超过规定的上
第 3 步：将节约里程按从大到小顺序排列
序号
路线
1
P2P3
2
P3P4
3
P2P4
4
P4P5
5
P1P2
6
P1P5
7
P1P3
8
P2P5
9
P3P5
10
P1P4
14
节约里程 10 8 6 5 4 2 1 0 0 0
优选
节约里程法
第4步：根据载重量约束与节约里程大小，顺 序连接各客户结点,形成二个配送路线 .
17
优选
节约里程法 （0.9） P3
6
（1.4）
P4
7
P0
10
（1.7）
P2
8
8
P5
（2.4）
初始方案：配送线路5条， 需要车5辆
配送距离=39×2=78KM
18
P1 (1.5)
优选
节约里程法
• 初始方案： –配送线路5条， 需要车5辆 –配送距离：39×2=78KM
• 优化后的方案： –2条配送线路，2辆4t车 –配送距离：24＋34＝58km
请为百家姓配送中心制定最优的配送方案。
20
优选
21
优选
第一步：计算最短距离。根据配送网络中的已知条件， 计算配送中心与客户及客户之间的最短距离，结果见表 11-11。 第二步：计算节约里程sij,结果见表11-12。
22
优选
第三步：将节约sij,进行分类，按从大到小的顺序排 列，得表11-13
10
优选
(1.4)
P4
( 0.9 )
P3
5 6
9
7
12
10
P5
( 2.4 )
4 (1.7）
P2
8 12
13
P0
8
16
P1 (1.5 )
11
优选
节约里程法
第1 步：作运输里程表，列出配送中心到用户 及用户间的最短距离。
需求 量
P0
P1 1.5 8
P1
P2 1.7
8
12
P2
P3 0.9 6
13
4
P3
3
供应商 客户
优选
首先求出从1出发的一条最短路径（1-2：4），求 次短路径（2-5：2）， 依次类推： （5-6：8），
（5-4-6：7）， （5-4-3-6：6），最短距离 求得的最短路径是：1-2-5-4-3-6 距离是：4+2+6=12
4
优选
（二）分送式配送运输
一对多配送的最短路线问题
适用方法——节约里程法
P1 (1.5)
16
优选
节约里程法 （0.9）
P3
4
5
（1.4）
P4
配送线路1
7
P0
10
（1.7）
P2
8
8
P5
P1 (1.5)
配送线路1：
（2.4）
运量 = 1.7+0.9+1.4= 4t
运行距离＝8＋4＋5＋7＝24km
用一辆 4t车运送
节约距离 =18km
配送线路2: 运量=2.4+1.5=3.9t<4t 运行距离＝8＋10＋16＝34km 用一辆 4t车运送 节约距离=2km
配送线路优化方法
1
优选
（一）直送式配送运输
一对一配送的最短路线问题
适用方法——最短路径法
适用条件：
标点法设计 最短线路
1、由配送中心向每一位客户开展专门送货；
2、该客户的送货量一般必须满足配送车辆满载。
配送效果：
1.配送车辆满载运输；
2.配送运输路线距离最短。
2
优选
【例】 求1-6的 最短距 离。
23
优选
第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图
24
优选
（1）初始方案：对每一客户分别单独派车 送货，结果如图11-10。
25
优选
修正方案4
26
优选