节约里程法的算法

图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所示。

表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

节约里程法案例详解

假如由一家配送中心P向两个用户A、B送货，配送中心

到两客户的最短距离分别是L

1和L

2，A和B间的最短距离为

L

3，AB的货物需求量分别是Q1和Q2，且Q1+Q2小于车辆

装载量Q

【如果Q1+Q2大于车辆装载量Q，那一辆车就无法装完两

位客户的货物】。

如下图所示：

如果配送中心用两辆汽车分别对A、B两个用户各自往返送货时，汽车

行驶的总里程L

是

L

=2（L

1+ L

2）

如果用一辆汽车向A、B两个用户巡回送货，则汽车行

驶总里程L

′为

L

′= L

1+ L

2+L

3

根据三角形的一边之长必定小于另外两边之和的原理，

后一种配送方案比前一种方案节约里程△L

为

△L

=2（L

1+ L

2）-（L

1+ L

2+L

3）

= L

1+ L

2-L

3

【这就是节约里程法产生的初衷，以最短距离最优配载完成送货作业】

案例

：

位于市内的百家姓配送中心（P0）向它旗下的10家连锁商店

p

i(i=1,2,…,10)配送商品，其配送网络如下图所示。

图中括号内的数字表示每一家连锁店的需求量（t），线路上的数字表示两节点之间的距离（km）。配送中心现有2t和4t车辆可供使用（无数量限制），并且每辆车配送距离不得超过

30km。

请为百家姓配送中心制定最优的配送方案。

分析：

初始方案：如果从P点向各点分别派车送货。

第一种：初始方案运行结果：

1、从百家姓配送中心出发，需要设计10条配送线路，分别向10

家连锁店配送商品；

2、需要10辆2t的配送车辆（每家连锁店的需要量都低于2t），

总配送距离为148km。

第二种：节约里程法解题思路：

相互间的节约里程计算根据 △L

== L

1+ L

2-L

3 原理，例如以“百家姓配送

中心交通图”中的P0（配送中心）到客户d、客户c的节约里程为例：

dc△L

== P0d(L

1)+P0c (L2)-dc(L

3 )

==8 + 7 - 5=10

如此计算出客户d和客户c间的节约里程数为10，以此方法计算出各个节

点的节约里程数。

节约里程法及举例1

当由一个配送中心向多个客户进行共同送货，在一条线路上的所有客户的需求量总和不大于一辆车的额定载重量时，由这一辆车配装着所有客户需求的货物，按照一条预先设计好的最正确路线依次将货物送到每一客户手中，这样既可保证按需将货物及时送交，同时又能节约行驶里程，缩短整个送货时间，节约费用。节约里程法正是用来解决这类问题的较成熟的方法。

用节约里程法确定配送路线的主要思路是，根据配送中心的运输能力及其到各客户之间的距离和各客户之间的相对距离，来制定使总的配送车辆吨公里数到达或接近最小的配送方案。

节约里程法的根本思路如下图，P为配送中心所在地，A和B为客户所在地，相互之间道路距离分别为a、b、c。最简单的配送方法是利用两辆车分别为A、B客户配送，此时，如图〔b〕所示，车辆运行距离为2a2b。然而，如果按图〔c〕所示改用一辆车巡回配送，运行距离为abc。如果道路没有什么特殊情况，可以节省的车辆运行距离为2a2b–abc=ab–c>0，这个节约量“ab–c〞被称为“节约里程〞。

A A

A

B B P P P B

（a）物流网络 （b）用两辆车配送 （c）用一辆车配送 a c

b a

b a c

b a

b c

图 配送中心配送路线的选择

1 郑克俊仓储与配送管理〔第四版〕科学出版社 修订。 步骤：实际上如果给数十家、数百家客户配送，〔1〕应首先计算包括配送中心在内的相互之间的最短距离，〔2〕然后计算各客户之间的可节约的运行距离，〔3〕按照节约运行距离的大小顺序连结各配送地并设计出配送路线。下面举例说明节约里程法的求解过程。

节约里程法举例

图为某配送网络，P为配送中心所在地，A～J为客户所在地，共10个客户，括号内的数字为配送量〔单位：吨〕，路线上的数字为道路距离〔单位：千米〕。现有可以利用的车辆是最大装载量为2吨和4吨的两种厢式货车，并限制车辆一次运行距离在30千米以内。为了尽量缩短车辆运行距离，试用节约里程法设计出最正确配送路线。