(0.9)
C
4 (1.2) 6 (1.6) 9 (1.1) 10 4 5 7 6 7 5 11 5 8
D
B (0.5)
5
E
A (1.7)
3 6 4 5 7
P
10
F
14 (0.9)
I (0.6)
G
12
H
(0.9)
• 计算配送中心至各用户以及各用户之 间的最短距离，列表得最短距离表：
P P A B C D E F G H I
第二步，根据最短距离表，利用节约法计算出用 户间的节约里程，并由大到小排列，编制节约里 程顺序表，如表2所示。
ΔL=（La+Lb）－Lab 1—2：L1+L2-L12=12+8-9=11 1—3：L1+L3-L13=12+17-8=21 1—4：L1+L4-L14=12+15-9=18 1—5：L1+L5-L15=12+15-17=10 1—6：L1+L6-L16=12+20-23=9 1—7：L1+L7-L17=12+17-22=7 1—8：L1+L8-L18=12+8-17=3 1—9：L1+L9-L19=12+6-18=0 1—10：L1+L10-L1、10=12+16-23=7 1—11：L1+L11-L1、12=12+21-28=5 1—12：L1+L12-L1、12=12+11-22=1 1—13：L1+L13-L1、13=12+15-27=0
顺位 里程 号
节约里 程
顺位 里程 号
节约里 程
顺位 里程 号
节约里 程
1 2 3 4 5
A-B B-C A-I C-D A-C
16 14 12 11 10
6 8 8 10 10
H-I B-D D-E A-H B-I
8 7 7 6 6
10
F-G
6 6 3 2 1
10 G-H 15 16 17 A-D B-E D-F
A—B:LA+LB—LAB=11+10-5=16 A—C:LA+LC—LAC=11+9-10=10 A—D:LA+LD—LAD=11+6-14=3 A—E:LA+LE—LAE=11+7-18=0 A—F:LA+LF—LAF=11+10-21=0 A—G:LA+LG—LAG=11+10-21=0 ……
16 16 16 16 16 15 15 15 15 …
第三步，根据节约里程顺序表和配送中心的约束 条件，绘制配送路线。其具体步骤如下：首先选 择最节约里程的路段（6—11），然后是（6—7）， 由于配送路线必须包含DC，且每条循环路线上的 客户需求量之和要小于200吨，在接下的选择中满 足条件的只有路段（11—8），此时载重总量为 193吨，因为在余下选择中没有满足条件的客户， 所以，第一回合的配送路线为（DC—7—6—11— 8—DC）。按此方法类推，其余的配送路线分别是 （DC—1—3—4—DC）、（DC—5—10—12—13— DC）、（DC—2—9—DC）。 总路程为：（17+4+7+13+8）+（12+8+4+15） +(15+9+9+8+15)+(8+12+6)=170 原路程为：2× （12+8+17+15+15+20+17+8+6+16+21+11+15） =362
最后值得一提的是，节约法计算的配送路线并不 是总路程最短。由上面的案例可知,如若采用配送 路线(DC - 1 - 3 - 4 - DC) ， (DC - 2 - 5 6 - DC)， (DC - 10 - 7 - 11 - DC) 和(DC - 8 - 12 - 13 - 9 -DC) ,总路程为165 km ,比采用 节约法的计算结果少11 km. 原因是节约法一方面 要缩短总路程,另一方面又要充分利用车辆的运输 空间(载重 / 容积) ，减少配送车次，而且只要 在前一条预设路线上运行的配送车辆的运输空间 允许，就必须按着节约路程的大小顺序进行选择 而不考虑其它的预设路线，在事实情况下选择的 路线并不能“节约”路程和有效利用运输空间， 而且运输的车次也不一定减少，对比上例中两种 方案就会发现这一问题。
节约里程法
目录
基本原理
案例分析
优缺点分析
改进建议
基本原理
• 基本原理是几何学中三角形一边之长必定小于另 外两边之和。 • 节约里程法核心思想是依次将运输问题中的两个 回路合并为一个回路，每次使合并后的总运输距 离减小的幅度最大，直到达到一辆车的装载限制 时，再进行下一辆车的优化。优化过程分为并行 方式和串行方式两种。
节约里程表 A B C D E F G H I
A B C D E F G H I
16
10 14
3 7 11
0 2 6 7
0 0 0 1 8
0 0 0 0 0 6
6 0 0 0 0 0 6
12 6 0 0 0 0 0 8
根据节约里程表中节约里程多少的顺 序，由大到小排列，编制节约里程顺 序表，以便尽量使节约里程最多的点 组合装车配送。
实例分析
设一配送中心向13个客户配送商品，配送中心及 客户间的最短距离如表1所示，如果配送的车辆载 重为200吨，那么利用节约法求解的配送路线的 步骤如下： 第一步，计算配送中心到库户间的最短距离，画 出距离表。因为本例已给出，所以可以直接进行 第二步。
表1 配送中心到客户间的最短距离表
DC 1 2 3 4 5 6 7 8 9 10 11 12 13 需求量 12 8 17 15 15 20 17 8 6 16 21 11 15 1 0 9 8 9 17 23 22 17 18 23 28 22 27 48 0 10 8 9 15 13 9 12 14 18 14 20 36 0 4 14 20 20 19 22 22 26 24 30 43 0 11 16 16 16 20 19 22 21 28 92 0 6 5 11 17 9 11 14 22 57 0 4 14 20 8 7 16 23 16 0 10 16 4 6 12 20 56 0 6 8 13 5 12 30 0 14 19 7 9 57 0 5 9 16 47 0 13 20 91 0 8 55 0 38 2 3 4 5 6 7 8 9 10 11 12 13
表2 节约里程表
序 号 路程 节约里程（来自a+Lb）－Lab序号
路程
节约里程
（La+Lb）－Lab
序号
路程
节约里程
（La+Lb）－Lab
1 2 3 4 5 6 7 8 9 10
6—11 6—7 7—11 10—11 7—10 5—6 3—4 6—10 5—7 5—11
34 33 32 32 29 29 28 28 27 25
• 假如一家配送中心（DC）向两个用户A、B运货， 配送中心到两用户的最短距离分别是La和Lb，A和 B间的最短距离为Lab，A、B的货物需求量分别是 Qa和Qb，且（Qa+Qb）小于运输装载量Q，如图 所示，如果配送中心分别送货，那么需要两个车 次，总路程为：L1=2（La+Lb）。
A
B A Lab B
11 12 13 14 15 16 17 18 19 20
5—10 1—3 11—12 4—5 4—6 1—4 3—5 12—13 10—12 3—6
22 21 19 19 19 18 18 18 18 17
21 22 23 24 25 26 27 28 29 …
11—13 8—10 7—12 4—7 8—11 2—3 2—4 7—8 6—12 …
2—3：L2+L3-L23=8+17-10=15 2—4：L2+L4-L24=8+15-8=15 2—5：L2+L5-L25=8+15-9=14 2—6：L2+L6-L26=8+20-15=13 2—7：L2+L7-L27=8+17-13=12 2—8：L2+L8-L28=8+8-9=7 2—9：L2+L9-L29=8+6-12=2 2—10：L2+L10-L2、10=8+16-14=10 2—11：L2+L11-L2、11=8+21-18=11 2—12：L2+L12-L2、12=8+11-14=5 2—13：L2+L13-L2、13=8+15-20=3 3—4：L3+L4-L34=17+15-4=28 3—5：L3+L5-L35=17+15-14=18 3—6：L3+L6-L36=17+20-20=17 ……
A 11
B 10 5
C 9 10 5
D 6 14 9 4
E 7 18 15 10 6
F 10 21 20 19 15 9
G 10 21 20 19 16 17 14
H 8 13 18 17 14 15 18 12
I 7 6 11 16 13 14 17 17 7
由最短距离表，利用节约法计算出各 用户之间的节约里程，编制节约里程 表：
总共节约里程为：362－170=192 或（33+34+16）+（28+21）+（22+18+18）+2=192
例：由配送中心P向A—I等9个用户配送货物。图中
连线上的数字表示公路里程（km）。靠近各用户 括号内的数字，表示各用户对货物的需求量（t）。 配送中心备有2t和4t载重量的汽车，且汽车一次 巡回走行里程不能超过35km，设送到时间均符合 用户要求，求该配送中心的最优送货方案。