例题：节约里程法

定义

节约里程法又称节约算法或节约法，是指用来解决运输车辆数目不确定的问题的最有名的启发式算法。[1]

2核心思想

节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。[1]

3基本规定

利用节约法确定配送路线的主要出发点是，根据配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。另还需满足以下条件；（1）所有用户的要求；（2）不使任何一辆车超载；（3）每辆车每天的总运行时间或行驶里程不超过规定的上限；（4）用户到货时间要求。[2]

4基本思想

为达到高效率的配送，使配送的时间最小距离最短成本最低，而寻找的最佳配送路线。[2]

5典型例题

例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有3台2t卡车和2台4t两种车辆可供使用。利用节约里程法制定最优的配送方案。[1]

节约里程法例题用图

第一步，作运输里程表，列出配送中心到用户及用户建的最短距离。[1]

第二步，按节约里程公式求得相应的节约里程数。[1]

第三步，将节约里程按从大到小顺序排列。[1]

第四步，根据载重量约束与节约里程大小，顺序连接各客户结点，形成两个配送线。[1]

P2P3－P3P4－P2P4－P4P5－P1P2－P1P5－P1P3－P2P5－P3P5－P1P4

得出结果：

配送线路一：

运量=1.7+0.9+1.4=4t

运行距离=8+4+5+7=24km

用一辆4t车运送，节约距离为18km

配送线路二：

运量=2.4+1.5=3.9t<4t

运行距离=8+10+16=34km

用一辆4t车运送，节约距离为2km[1]

初始方案：配送线路5条，需要车5辆，配送距离=39*2=78km

精品文档

精品文档 设配送中心向5个客户配送货物，其配送路线网络、配送中心与客户的距离以及客户之间的距离如下图与下表所示，图中括号内的数字表示客户的需求量（单位：t），线路上的数字表示两结点之间的距离（单位：km），现配送中心有3台2t卡车和2台4t卡车两种车辆可供使用。

（1）试用节约里程法制订最优的配送方案。

（2）假定卡车行驶的平均速度为40 km／h，试比较优化后的方案比单独向各客户分送可节约多少时间？

里程表

需要量 P0

1.5 8 P1

1.7 8 12 P2

0.9 6 13 4 P3

1.4 7 15 9 5 P4

2.4 10 16 18 16 12 P5

节约里程表 精品文档

精品文档 需要量

P0

1.5 8 P1

1.7 8 12（4） P2

0.9 6 13（1） 4（10） P3

1.4 7 15（0） 9（6） 5（8） P4

2.4 0 16（2） 18（0） 16（0） 12（5） P5

节约里程排序

序号 路线 节约里程 序号 路线 节约里程

1 P2P3 10 6 P1P5 2

2 P3P4 8 7 P1P3 1

3 P2P4 6 8 P2P5 0

4 P4P5 5 9 P3P5 0

5 P1P2 4 10 P1P4 0

路线选择

节约的总里程：

节省的配送时间为

节约里程法

例1：

设配送中心向7个客户配送货物，其配送路线网络、配送中心与客户的距离以及客户之间的距离如下图与下表所示，图中括号内的数字表示客户的需求量（单位：t），线路上的数字表示两结点之间的距离（单位：km），现配送中心有2台4t卡车和2台6t卡车两种车辆可供使用。

（1）试用节约里程法制订最优的配送方案。

（2）设配送中心在向客户配送货物过程中单位时间平均支出成本为450元，假定卡车行驶的平均速度为25 km／h，试比较优化后的方案比单独向各客户分送可节约多少费用？

（1）作运输里程表，列出配送中心到用户及用户间的最短距离

P0

P1 8 P1

P2 4 5 P2

P3 8 9 4 P3

P4 12 16 11 7 P4

P5 5 13 9 13 10 P5

P6 14 23 18 22 19 9 P6

P7 19 27 23 27 30 20 11 P7

（2）按节约里程公式求得相应的节约里程数

P1

P1 P2

P2 7 P3

P3 7 8 P4

P4 4 5 13 P5

P5 0 0 0 7 P6

P6 0 0 0 7 10 P7

P7 0 0 0 1 4 22

（3）将节约里程按从大到小顺序排列

表-节约里程顺序排列

序号 连接点 节约里程

1 P6-P7 22

2 P3-P4 13

3 P5-P6 10

4 P2-P3 8

5 P1-P2 7

P1-P3 7

P4-P5 7

P4-P6 7

P2-P4 5

P1-P4 4

P5-P7 4

P4-P7 1

4）根据载重量约束与节约里程大小，选择配送路线。

优先择节约里程数最大的连接点：P6-P7、P3-P4

最优方案：P0-P7-P6-P5-P0、P0-P4-P3-P2-P0、P0-P1-P0

节约里程法及举例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千米以内。为了尽量缩短车辆运行距离，试用节约里程法设计出最正确配送路线。