图3-17 配送中心网络图
分送式运输是指由一个供应点对多个客户的共同送货。其基本条件是所有客户的需求量总和不大于一辆车的额定载重量。送货时，由这一辆车装着所有客户的货物，沿着一条精心选择的最佳线路一次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，又节约了车辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。
例：图3-17所示为某配送中心的配送网络，图中P0点为配送中心，P1、P2、P3、P4、P5、P6、P7、P8、P9、P10为配送客户，共10位客户，括号内为配送货物吨数，线路上的数值为道路距离，单位为km。现配送中心有额定载重量分别为2吨和4吨两种厢式货车可供送货使用，试用节约法设计最佳送货路线。
第一步 计算最短距离
首先计算网络结点之间的最短距离（可采用最短路求解法）。计算结果如表3-16所示。表3-16 最短距离表
P0
10 P1
9 4 P2
7 9 5 P3
8 14 10 5 P4
8 18 14 9 6 P5
8 18 17 15 13 7 P6
3 13 12 10 11 10 6 P7 4 14 13 11 12 12 8 2 P8
10 11 15 17 18 18 17 11 9 P9
7 4 8 13 15 15 15 10 11 8 P10
第二步 计算节约里程
根据最短距离结果，计算出各客户之间的节约行程，结果见表3-17所示。
表3-17 节约里程表
P1
15 P2
8 11 P3
4 7 10 P4
0 3 6 10 P5
0 0 0 3 9 P6
0 0 0 0 1 5 P7
0 0 0 0 0 4 5 P8
1
"节约里程法"
英文翻译：节约里程法(Saving Algorithm)
内容摘要：节约里程法又称节约算法，是指用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。
什么是节约里程法
节约里程法又称节约算法，是指用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。
节约里程法的基本原理
节约里程法的基本思路如下图,已知O点为配送中心,它分别向用户A和B送货。
设O点到用户A和用户B的距离分别为a和b。用户A和用户B之间的距离为c,现有两种送货方案,如图下(a)和(b)所示。
在上图(a)中配送距离为2(a+b)；图上(b)中,配送距离为a+b+c。对比这两个方案,哪个更合理呢？这就要看哪个配送距离最小,配2
送距离越小,则说明方案越合理。由上图(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)的里程,这种分析方案的优劣式的思想,就是节约里程法的基本思想。、
拓展资料：
一、节约里程法核心思想
节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。
二、节约里程法示例
例:有一配送P具有如图所示的配送网络,其中A-J表示收货站,()内数字表示发送量(吨),路线上的数字表示道路距离(公里)。问为使行走距离尽量小,应该如何去求配送线路?假设能够利用的车是2吨车(即最大载重量是2吨)和4吨车两种,并限制车辆一次运行的初步距离是30公里。 3
算例：节约里程法
以上一个二维码扫描算法算例为例，用节约里程法计算配送线路的安排。
解：① 首先根据上一个二维码扫描算法算例中的距离矩阵表计算出各点间的节约值矩阵表，如表1所示。
表1 节约值矩阵表
sij v1 v2 v3 v4 v5 v6 v7 最大值
v1
v2 6
v3 13 14
v4 2 2 5
v5 9 6 9 12
v6 9 5 10 15 23
v7 6 13 9 14 13 13
v8 9 11 12 12 16 16 20
最大值 13 14 12 15 23 16 20 23
② 从表1中选出节约值最大值为23，其对应的两个顶点为5、6。5、6两处的需求量之和为8，未超过一辆车的运输能力14，因此，连接5、6成回路，即0—5—6—0。再将顶点5与6的节约值赋为0，结果如表2所示。
表2 节约矩阵表计算过程1
sij v1 v2 v3 v4 v5 v6 v7 最大值
v1
v2 6
v3 13 14
v4 2 2 5
v5 9 6 9 12
v6 9 5 10 15 0
v7 6 13 9 14 13 13
v8 9 11 12 12 16 16 20
最大值 13 14 12 15 16 16 20 20
③ 从表2中再选出节约值最大值为20，其对应的两个顶点为7、8。7、8两处的需求量之和为7，未超过一辆车的运输能力14，因此，连接7、8成回路，即0—7—8—0。再将顶点7与8的节约值赋为0，结果如表3所示。
表3 节约矩阵表计算过程2
sij v1 v2 v3 v4 v5 v6 v7 最大值
v1
v2 6
v3 13 14
v4 2 2 5
节约里程法概述
整体来看，节约里程法是物流配送领域中一种相当实用的优化方法。
大致分这么几个部分来理解吧。
首先，它的核心目标就是要减少总的配送里程，从而降低配送成本。这很好理解，就像你送快递或者运货，如果能少跑些冤枉路，那油费、时间成本都能降下来。比如一个快递公司，在一个小区有好几个收件地址，如果不规划好路线，可能就会来回跑，东一家西一家地送。但用节约里程法，就能先把这些收件地址的相对位置关系算清楚，规划出一条既能把货都送到，又走最少路的路线。
那它主要包括这些关键要素。一个是构建配送体系中的各个节点，这些节点就是一个个的发货地、收货地之类的。然后，得算出任意两个节点之间的距离。这里的距离不单纯只是地理直线距离，它可能涉及到实际的道路通行情况，比如有的路是单行道，就得多绕一绕，那这个绕的路程也得算进去。
在计算的过程当中，核心内容是这个节约里程数的计算。怎么算呢？简单说，就是把两个点单独配送时的里程和，减去把这两个点串起来配送的里程，得到的值就是节约里程数。然后根据这个节约里程数的大小来对线路进行组合优化。
对了还有个方面，在具体操作的时候，这个方法得考虑车辆的载重限制。你不能光为了省里程，结果把车装得超载了，那样是不符合规定的。比如说，一辆小货车载重1吨，计算路线的时候就只能安排总重量不超过1吨的货物在这条路线上配送。
实际理解这个框架的时候，可以这样去梳理思路。先确定配送的各个点，像棋盘上的棋子那样标出来，然后算出相互之间的距离。开始可能会在计算节约里程数这里有点困惑，那多做几个简单的例子就好理解了。比如说三个点A、B、C，分别算出A到B单独配送和串起来配送的节约里程数，然后依次类推。整个过程就像是玩拼图一样，不断把合适的模块拼接起来，构建出最简短里程的配送线路。而且这个过程往往不是一次就能做到最优化的，要不断调整、尝试不同的组合，就像走迷宫一样，可能走几步发现不对又得退回来重新规划路线，直到得到一套整体比较节省里程的配送方案为止。
