27
节约里程法的基本思想
说明：
因为三角形的两条边之和总是大于第三 条的，因此，它从不为负，最小为零； 将客户连接起来，增加了节约； 客户之间的距离越近，而且它们距离配 送中心越远，那么节约就会越大； 这个方法也可以用时间来代替距离计算
28
节约里程法的使用条件
适用于有稳定客户群的配送中心； 各配送线路的负荷要尽量均衡； 要考虑客户要求的交货时间（即一条线路的送 货总里程不能太长，否则会影响向客户交货时 间的准确性 还要考虑货物总量不能超过车辆的额定载重量 。
6
第一节 配送线路优化设计
技能目标 • 能够在配送中心与单个客户之间的线路中选 择最短（时间或里程或综合成本）线路；能 够规划出单个配送中心向多个客户送货的优 化路线 相关知识 • 送路线确定的原则、配送路线约束条件、配 送路线规划计算的主要方法（两点间最短路 线法及节约里程法）
7
配送线路合理优化的意义
请同学们根据“配送路线优化设计实训”第二 部分实训资料；使用实训动画同步进行自己的 计算
31
节约里程法实例
32
14
9 8
11
15
8
12 5 4 13 18 8
3
9
33
节约里程法计算（步骤一）
O A B C D E F G H 5 4 6 15 10 12 7 15 A 8 11 15 15 17 8 18 B 9 11 14 16 11 19 C 14 8 12 13 13 D 22 27 22 27 E 4 13 5 F 9 3 G 12 H
14
两点间最短路问题
• 下面使用计算表进行计算
• 请同学们根据“配送路线优化设计实训”第
一部分实训资料；同步进行自己的计算
15
步骤
已解节点
与该已解节点 直接连接的未 解节点
对应线路
对应总运行时间
最短路 线时间
新增的 已解节 点
选中的路 径
1
2
3
16
两点间最短路问题计算（步骤一）
步 骤 已解节 点 与该已解 节点直接 连接的未 解节点
12
两点间最短路问题
• 实例资料
12
A
18
C
32
O
17 28 17 32 11
P
B
4
D
13
两点间最短路问题
• 上图是某配送中心与一个客户之间的公路网
络示意图，O起点为配送中心所在位置，P终 点为客户所在位置，其它A、B、C、D代表从 O到P途中要经过的节点，节点与节点之间有 线路连接 , 线路上标明了两个节点之间的距 离，以运行时间 ( 分钟 ) 表示（当然也可以 用距离表示）。现在要在该图找出一条从配 送中心（O起点）到客户（J终点）之间的最 短路线。
A
18
C
32Oຫໍສະໝຸດ 17 28 17 329 11
P
B
4
D
22
练习
V1
1
V4
3
O
8 7 3
A
11
V2
2 4
V3
1
23
同学们的结果应该如下
1 V1 3 V4
8
O
7
3
A
11
2
4 V2 V3
1
成本最小路线O-V1-V4-V3-V2-A，成本值为10
24
两点间最短路计算的方法
始发点作为已解点，计算从始发点开始。 （1）第 n 次迭代的目标。寻求第 n 次最近始发点的节点 , 重复n ＝1,2, … , 直到最近的节点是终点为止。 (2) 第 n 次迭代的输入值。 (n-1) 个最近始发点的节点是由以前 的迭代根据离始发点最短路线和距离计算而得的。这些节点以及 始发点称为己解的节点 , 其余的节点是尚未解的点。 (3) 第 n 次最近节点的候选点。每个己解的节点由线路分支通向 一个或多个尚未解的节点 , 这些未解的节点中有一个以最短路线 分支连接的是候选点。 (4) 第 n 个最近的节点的计算。将每个己解的节点及其候选点之 间的距离和从始发点到该已解节点之间的距离加起来，总距离最 短的候选点即是第 n 个最近的节点 , 也就是始发点到达该点最短 距离的路径。
20
两点间最短路问题计算（步骤五）
步 骤
1
已解节点
与该已解节 点直接连接 的未解节点
A
B B C B B B P B 无 无 P D P 无 无 P P
对应线路
对应总运行时 间
18
32 32 30 46 32 46 62 47 无 无 62 36 49 无 无 62 49
最短 路线 时间
18
新增的 已解节 点
A
选中的路 径
O O A
OA
OB OB OAC OAB OB OAB OACP OACB 无 无 OACP OBD OBP 无 无 OACP OBP
OA
2
30
C
OAC
3
O A C
32
B
OB
4
O A C B
36
D
OBD
5
O
A C B D
47
P
OBDP
P
OBDP
47
21
最终计算结果（规划出的路线）
12
9
以成本为中心确定配送路线
• 从以上几个目标来看，路程最短、吨公里最
小、劳动消耗最低都直接与成本相关，而准 时性最高、运力运用最合理两项也间接地与 成本有联系，且由于成本的降低最终也影响 到效益目标的实现，以成本为目标与以效益 为目标上事实上是相辅相成的，成本控制在 配送路线的选择与确定工作中，占有核心地 位。
34
节约里程法计算（步骤二）
根据最短路结果和节约里程 法的基本原理，计算出各客 户之间的节约里程。计算方 法是：i,j是任意相邻两客户节 点，Oi=a，Oj=b，ij=c，则 i—j节约的里程为：a+b-c 。 例如：A，B两点的节约里程 为，OA+OB-AB＝5+4-8＝1 。按照同样的算法，可求出 任意两点的节约里程数，汇 总结果如表所示。
25
节约里程法
解决单起点多回路最短路线问题的方法最常用的方法 是“节约里程法”，它是形成人工和计算机计算单起 点多回路最短路线的基础。
26
节约里程法的基本思想
见下图：
O
a
b
A
B
c
O点为配送中心所在地，A 和 B 为客户所在地 , 三者相互间的道路距离分别为 a、b、c。从配送中心 O 要运送货物给客户 A 和 B。第一条路线是从 O-A-O, 然后再从 O-B-O, 总距离为a+a +b+b=2a+2b，还可以选择另外一种路线，从 O-A-B-O。总距离为：a+b +c 。结合客户综合考虑,在第二种方案下行驶路线 的节约里程数是：(2a+2b) - (a+b+c) 即：a+b-c
OA OB OB OAC OAB OB OAB OACP OACB
18 32 32 30 46 32 46 62 47
18
OA
2
30
C
OAC
3
O A C
32
B
OB
19
两点间最短路问题计算（步骤四）
步骤 已解节点 与该已解节 点直接连接 的未解节点
A O 2 O A 3 O A C 4 O A C B B B C
18 32 32 30 46 30 C OAC
O
2
B B C
18
A
OA
O
A
B
18
两点间最短路问题计算（步骤三）
步 骤 已解节 点 与该已解 节点直接 连接的未 解节点 A B B C B B B P B 对应线路 对应总运 行时间 最短 路线 时间 新增 的已 解节 点 A 选中的 路径
1
O O A
29
节约里程法实例
30
节约里程法实例
下图所示为某配送中心的配送网络，图中O点为配送中 心，A—J 为配送客户，共有 8 位客户。括号内为配送 货物重量（单位：吨），线路上的数字为道路距离（ 单位：公里）。配送中心有额定载重分别为2吨和4吨 两种厢式货车可供送货（即每条线路每次送货总重量 不能超过4吨），考虑到达客户后装卸交付时间、送货 路上时间、员工上下班时间等因素，每条线路送货总 里程不能超过35公里。下面用节约里程法设计最佳送 货路线。
第五章 送货作业管理
本章内容
• 送货作业总体介绍
• 第一节
• 第二节 • 第三节
配送线路优化设计 车辆配载 送货作业计划与调度
2
送货作业
送货作业是指把客户订购的物品从供应商、批发商、零售商或配 送中心 , 通过配送车辆送到客户手中的过程。配送送货的特点是 距离短、批量小、频率高。根据日本的配送送货经验 , 配送送货 半径最好在50 公里以内 , 而中国国内配送中心、物流中心的配送 有效距离大约在30 公里以内。送货的本质是一种服务客户的活动， 尽可能满足客户需求让客户满意是送货服务的目标，但是送货费 用在配送成本中的比例也是最高的，约占配送总成本的35%-60%， 降低送货费用对提高配送业务的总体效益有极为重要的意义。因 此，客户对送货服务满意与控制送货成本两者之间的均衡是送货 作业管理活动的核心内容。要组织好配送活动中的送货作业，必 须解决好送货路线的优化设计、车辆货物的配载、送货作业计划 及作业计划执行过程中的调度等问题。
5
案例小结
通过前面案例的内容可以看出，送货作业是配 送作业流程的重要环节，送货费用的高低对配 送总成本的影响很大。送货作业是以短途汽车 运输为主，压缩成本的选择范围相对较少，难 度相对较大，案例中采取的措施主要涉及到路 线优化、车辆配载、送货作业计划及调度等三 个方面，通过这些措施降低了配送的总成本， 增加了利润。而路线优化、车辆配载、送货作 业计划及调度这三个配送送货方面的核心作业 这也正是本章要介绍的内容。