节约里程法应用案例

节约里程法的应用1.基本资料介绍①宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优化方法。

公司客户分布在全国各地,这里主要以广东省内7家客户及省外一家特殊客户的一次配送为例。

城市和货运量②广州配送中心为这次配送提供了三种车型,载重量分别为2吨、5吨和8吨,不同车型的运输单价不一样,具体见运输单价表。

配送中心的配送是由外协商提供车辆,因此汽车的数量没有限制。

运输单价表2.步骤第一步:各城市之间的距离见上表。

第二步:计算连接城市到同一线路上的距离节约值,具体见下表。

第三步:确定初始方案的运输线路及运输费用,现安排4辆2吨、4辆5吨的车给每个客户送货。

运输线路及运输费用见下表所示。

运输线路及运输费用运输路线车型距离单价运费广州-东莞5T 50 2.7 135广州-江门2T 53 2.4 127.2广州-惠州2T 116 2.4 278.4广州-阳江5T 173 2.7 467.1广州-汕尾5T 221 2.7 596.7广州-揭阳5T 333 2.7 899.1广州-汕头2T 344 2.4 825.6广州-漳州2T 478 2.4 1147.2合计1768 4476.3第四步:进行线路第一次优化。

第一次修改后的车辆调度结果运输路线车型距离单价运费广州-东莞5T 50 2.7 135 广州-江门2T 53 2.4 127.2 广州-惠州2T 116 2.4 278.4 广州-阳江5T 173 2.7 467.1 广州-汕尾5T 221 2.7 596.7 广州-揭阳5T 333 2.7 899.1 广州-汕头-漳州5T 502 2.7 1355.4 合计1148 3858.9第五步:继续进行线路优化。

第二次修改后的车辆调度结果运输路线车型距离单价运费广州-东莞5T 50 2.7 135广州-江门2T 53 2.4 127.2广州-惠州2T 116 2.4 278.4广州-阳江5T 173 2.7 467.1广州-汕尾5T 221 2.7 596.7 广州-揭阳-汕头-漳州8T 526 3.65 1919.19 合计1139 3523.59从表中可以看出,广州-惠州-揭阳-汕头-漳州路线上的总货运量达到7.9吨,再连接任何一个城市都将使货运量超过最高限制(8吨),则不能继续配载,所以可以首先确定的是这一条线路。

图3-17 配送中心网络图分送式运输是指由一个供应点对多个客户的共同送货。

其基本条件是所有客户的需求量总和不大于一辆车的额定载重量。

送货时，由这一辆车装着所有客户的货物，沿着一条精心选择的最佳线路一次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，又节约了车辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。

例：图3-17所示为某配送中心的配送网络，图中P0点为配送中心，P1、P2、P3、P4、P5、P6、P7、P8、P9、P10为配送客户，共10位客户，括号内为配送货物吨数，线路上的数值为道路距离，单位为km。

现配送中心有额定载重量分别为2吨和4吨两种厢式货车可供送货使用，试用节约法设计最佳送货路线。

第一步计算最短距离首先计算网络结点之间的最短距离（可采用最短路求解法）。

计算结果如表3-16所示。

表3-16 最短距离表第二步计算节约里程根据最短距离结果，计算出各客户之间的节约行程，结果见表3-17所示。

表3-17 节约里程表第三步将节约里程进行分类对节约行程按从大到小的顺序排列，如表3-18所示。

表3-18 节约里程排序第四步确定配送线路按节约里程大小顺序，组成线路图。

1、初始方案：如图3-18所示，从配送中心P0分别向各个客户进行配送，对每一客户分别单独派车送货，共有10条配送线路，总行程为148公里，需2吨货车10辆。

2、修正方案1：图3-18 图3-19按照节约行程的由大到小的顺序，连接P1和P2，P1和P10，P2和P3，P3和P4，形成巡回路线P0-P10-P1-P2-P3-P4-P0的配送线路，如图所示，装载货物4吨，这时配送路线总运行距离为109公里，配送线路6条，需4吨货车1辆，需2吨货车5辆，如图3-19所示。

3、修正方案2：按节约里程由大到小的顺序，连接P5和P6，P6和P7，形成巡回路线P0-P5-P6-P7-P0的配送线路，如图所示，装载货物3.5吨，这时配送路线总运行距离为85公里，配送线路4条，需4吨货车2辆， 图3-20 需2吨货车2辆，如图3-20所示。

节约里程法路径优化节约里程法是一种用于路径优化的方法，通过选择最短路径来减少行程中的里程数。

在现实生活中，我们经常需要规划行程，比如出差、旅行或者日常的通勤。

而选择最优路径可以节省时间和精力，提高效率。

下面我将以一个出差的例子来说明如何使用节约里程法进行路径优化。

假设我需要从A市出差到B市，那么我可以通过多种交通方式进行选择，比如飞机、火车、汽车等。

为了节约里程，我需要考虑以下几个因素：距离、时间、费用和舒适度。

我可以考虑乘坐飞机。

飞机通常是最快的交通工具，可以快速到达目的地。

然而，飞机票价格较高，且需要提前预订。

如果我需要频繁出差，花费较多的机票费用可能会对我的财务造成一定的压力。

我可以选择乘坐火车。

火车通常比汽车更舒适，且价格相对较低。

但是，火车的速度可能较慢，行程可能需要更长的时间。

如果我需要在短时间内到达目的地，乘坐火车可能不是最佳选择。

我可以选择乘坐汽车。

汽车的灵活性较高，我可以根据需要随时停下来休息或处理其他事务。

然而，长途驾驶可能会让我感到疲劳，而且汽车的油费和路桥费用也需要考虑。

综合考虑以上因素，我可以做出最优选择。

如果时间充裕且预算充足，我可以选择乘坐飞机，以最快的速度到达目的地。

如果时间有限，但预算有限，我可以选择乘坐火车，虽然时间稍长，但价格相对较低。

如果我喜欢自驾旅行或者需要灵活性，我可以选择乘坐汽车。

节约里程法可以帮助我在出差或旅行时选择最优路径。

通过综合考虑距离、时间、费用和舒适度等因素，我可以做出最合适的决策。

这样不仅可以节约里程，还可以提高出差或旅行的效率和体验。

希望这种方法能对大家在路径优化方面提供一些参考和帮助。

物流方案设计（最优运输路线决策-节约里程法）典型实例:已知配送中心P O向5个用户P j配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示：图中括号内的数字表示客户的需求量（单位：吨），线路上的数字表示两结点之间的距离，配送中心有3台2t卡车和2台4t两种车辆可供使用，1、试利用节约里程法制定最优的配送方案？2、设卡车行驶的速度平均为40公里/小时，试比较优化后的方案比单独向各用户分送可节约多少时间？第（1）步：作运输里程表，列出配送中心到用户及用户间的最短距离。

得初始方案配送距离=39X 2=78KM第（5）步：根据载重量约束与节约里程大小，将各客户结点连接起来，形成二个配送路线。

即A B 两配送方案。

序号 路线 节约里程 序号 路线 节约里程1 P 2P 3 10 6 P i F 52 2 P 3P 4 8 7 P i P3 1 3 P 2P4 6 8 F 2F5 0 4 P 4P 5 5 9 F 3F 5 0 5P l P 2410P i F 4第（2）步：由运输里程表、按节约里程公式，求得相应的节约里程数，如上表（ 第（3）步：将节约里程 sij 进行分类，按从大到小顺序排列第（4）步：确定单独送货的配送线路）内。

(1.5)①配送线路A：P0-P2-P3-P4- P 0 运量q A= q 2+q3+q4 = 1.7+0.9+1.4 = 4t 用一辆4t 车运送节约距离S A =10 +8 = 18km②配送线路B: P 0-P5 -P 1-P0 运量q B =q 5+q1=2.4+1.5=3.9t<4t 车用一辆4t 车运送节约距离S B=2km第（6）步：与初始单独送货方案相比，计算总节约里程与节约时间总节约里程：△ S= S A+S B= 20 km与初始单独送货方案相比，可节约时间：△T = △ S/V=20/40=0.5小时。

物流方案设计（最优运输路线决策－节约里程法）典型实例：已知配送中心P O向 5 个用户 P j配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示：图中括号内的数字表示客户的需求量（单位：吨），线路上的数字表示两结点之间的距离，配送中心有 3 台 2t 卡车和 2 台 4t 两种车辆可供使用，1、试利用节约里程法制定最优的配送方案？2、设卡车行驶的速度平均为40 公里 / 小时，试比较优化后的方案比单独向各用户分送可节约多少时间？（ 0.9）P3 4（ 1.7）5P2 6128（ 1.4）12 P4 7 P0 1312 10 8P5 16P1 （ 1.5）需要量P0（ 2.4）1.5 8 P11.7 8 12 P20.9 6 13 4 P31.4 7 15 9 5 P42.4 10 16 18 16 12 P5第（ 1）步：作运输里程表，列出配送中心到用户及用户间的最短距离。

需要量0 P1.5 8 P11.7 8 （ 4）P12 20.9 6 （1）（ 10）P3 13 41.4 7 （0）（6）（8）4 15 9 5 P2.4 10（2）（0）（0）（5）16 18 16 P512第（ 2）步：由运输里程表、按节约里程公式，求得相应的节约里程数，如上表（）内。

第（ 3）步：将节约里程sij 进行分类，按从大到小顺序排列序号路线节约里程序号路线节约里程1 P2P3 10 6 P1 P5 22 P P 8 7 P P 13 4 1 33 P P 6 8 P P 02 4 2 54 P4P5 5 9 P3 P5 05 P1P2 4 10 P1 P4 0第（ 4）步：确定单独送货的配送线路（0.9）P3 （ 1.7 ）P268（ 1.4）P4 7P0108P5P1（1.5）（2.4 ）得初始方案配送距离 =39× 2=78KM第（ 5）步：根据载重量约束与节约里程大小，将各客户结点连接起来，形成二个配送路线。

节约里程法：
由配送中心P 向A ～I 等9个用户配送货物。

图中连线上的数字表示公路里程（km ）。

靠近各用户括号内的数字，表示各用户对货物的需求量（t ）。

配送中心备有2t 和4t 载重量的汽车，且汽车一次巡回走行里程不能超过35km ，设送到时间均符合用户要求，求该配送中心的最优送货方案。

计算配送中心至各用户以及各用户之间的最短距离，列表得最短距离表：
由最短距离表，利用节约法计算出各用户之间的节约里程，编制节约里程表：
A
B C
D
E
F
G
H
I P
(0.9)
(1.2)(1.6)(0.9)
(0.9)
(0.6)
(1.7)(0.5)4
44
5
555
5
66
6
3
77
7
8
9
1010
1112
14
根据节约里程表中节约里程多少的顺序，由大到小排列，编制节约里程顺序表，以便尽量使节约里程最多的点组合装车配送。

根据节约里程排序表和配车（车辆的载重和容积因素）、车辆行驶里程等约束条件，渐进绘出配送路径：
(0.9)。

算例：节约里程法以上一个二维码扫描算法算例为例，用节约里程法计算配送线路的安排。

解：① 首先根据上一个二维码扫描算法算例中的距离矩阵表计算出各点间的节约值矩阵表，如表1所示。

表1 节约值矩阵表② 从表1中选出节约值最大值为23，其对应的两个顶点为5、6。

5、6两处的需求量之和为8，未超过一辆车的运输能力14，因此，连接5、6成回路，即0—5—6—0。

再将顶点5与6的节约值赋为0，结果如表2所示。

表2 节约矩阵表计算过程1③ 从表2中再选出节约值最大值为20，其对应的两个顶点为7、8。

7、8两处的需求量之和为7，未超过一辆车的运输能力14，因此，连接7、8成回路，即0—7—8—0。

再将顶点7与8的节约值赋为0，结果如表3所示。

表3 节约矩阵表计算过程2④ 从表3中再选出节约值最大值为16，其对应的两个顶点为5、8或6、8。

如果连接5与8，则上述两条回路合并，其总需求量为15，超过一辆车的运输能力14，因此，5与8不能连接，同样6和8也不能连接，则将顶点5、8和6、8的节约值赋为0，结果如表4所示。

表4 节约矩阵表计算过程3⑤ 从表4中再选出节约值最大值为15，其对应的两个顶点为4、6。

如连接4与6，则形成：0—5—6—4—0回路，其总需求量为11，未超过一辆车的运输能力14，因此，连接4、6成新回路，即0—5—6—4—0。

再将顶点4与6的节约值赋为0，同时，由于顶点6成为回路的中间点，则与顶点6相关的节约值都赋为0。

表示顶点6不可能再与其他点相连，其结果如表5所示。

表5-33 节约矩阵表计算过程4⑥ 按算法步骤迭代运算，直到节约值矩阵表中的值均为0时，迭代结束。

最终的结果为：0—2—3—0，0—5—6—4—0，0—7—8—1—0这三条线路，其运输量分别为9、11、13，总里程数为93。

一般来说，节约里程法可以得到比较好的结果，但此算法也是一种贪婪启发式算法，对于一些特殊的算例，得不到最优解。

上一个二维码中算例的全局最优解是：选择0—1—3—0，0—2—7—8—0，0—5—6—4—0这三条线路，其运输量分别为11、11、11，总里程数为90。

节约里程法应用案例在当今竞争激烈的商业环境中，物流成本的有效控制对于企业的生存和发展至关重要。

节约里程法作为一种优化配送路线的有效方法，能够显著降低运输成本，提高物流效率。

接下来，让我们通过一个具体的案例来深入了解节约里程法的实际应用。

假设我们有一家位于城市中心的配送中心，需要向位于城市不同区域的五个客户（A、B、C、D、E）配送货物。

每个客户的需求量以及他们之间的距离如下表所示：｜客户|需求量（吨）｜与配送中心距离（公里）｜｜｜｜｜｜A|5|10|｜B|8|12|｜C|3|8|｜D|6|15|｜E|4|11|｜客户|A|B|C|D|E|｜｜｜｜｜｜｜｜A| ｜ 18 ｜ 22 ｜ 25 ｜ 16 ｜｜B| 18 ｜｜ 10 ｜ 18 ｜ 12 ｜｜C| 22 ｜ 10 ｜｜ 14 ｜ 9 ｜｜D| 25 ｜ 18 ｜ 14 ｜｜ 20 ｜｜E| 16 ｜ 12 ｜ 9 ｜ 20 ｜｜首先，我们按照传统的方法，即每个客户单独配送，计算出总运输里程。

配送中心到客户 A 的往返里程为 2×10 ＝ 20 公里。

配送中心到客户 B 的往返里程为 2×12 ＝ 24 公里。

配送中心到客户 C 的往返里程为 2×8 ＝ 16 公里。

配送中心到客户 D 的往返里程为 2×15 ＝ 30 公里。

配送中心到客户 E 的往返里程为 2×11 ＝ 22 公里。

总运输里程为 20 ＋ 24 ＋ 16 ＋ 30 ＋ 22 ＝ 112 公里。

接下来，我们应用节约里程法来优化配送路线。

第一步，计算两两客户之间的节约里程数。

例如，客户 A 和客户 B 之间的节约里程数为：（配送中心到 A 的距离＋配送中心到 B 的距离 A 到 B 的距离）× 2 ＝（10 ＋ 12 18）× 2 ＝ 8 公里。

按照同样的方法，计算出所有两两客户之间的节约里程数，如下表所示：｜客户|A|B|C|D|E|｜｜｜｜｜｜｜｜A| ｜ 8 ｜ 6 ｜ 5 ｜ 2 ｜｜B| 8 ｜｜ 4 ｜ 3 ｜ 4 ｜｜C| 6 ｜ 4 ｜｜ 2 ｜ 3 ｜｜D| 5 ｜ 3 ｜ 2 ｜｜ 5 ｜｜E| 2 ｜ 4 ｜ 3 ｜ 5 ｜｜第二步，根据节约里程数的大小对路线进行合并和优化。

节约里程法1.原理设P 为配送中心，A 和B 为收货点，相互之间的道路距离为a , b , c 。

若分别使用两辆货车分别向A 、B 两地往返送货，其行驶里程为:2a+2b 。

但若使一辆货车（货车可以满载两地送货）由P → A →B →P ，单线巡回送货，其行驶总里程为a+c+b 。

两者相比，后一种方案比前一种送货方案可节省的运输距离是： （2a+2b ）-（a+c+b ）= a + b - c > 0这一节约距离称为节约里程，所以我们称这种方法为“节约里程法”。

2 .实例由于案例所给内容有限，所以我们自行上网查找了一些资料。

下图是我们找到的位于郑明现代物流有限公司上海总部周边的一些大型商超，下面我们就假设这些超市为郑明现代物流有限公司的配送点，利用节约里程法来设计末端配送网络的合理运输。

上海郑明现代物流有限公司周边的商超配送点PABacb图X-X备注：1 . 红色五角星所在位置即为郑明现代物流有限公司的所在地(P)2 . 紫色圆圈即为超市配送点的位置及其名称（从左至右依次为：城市超市(A)、沃尔玛超市(B)、世纪华联超市(C)、联华超市(F)、家乐福超市(D)、大润发超市(E)）为直观清晰的了解郑明现代物流有限公司与给超市配送点之间的关系，我们将上图简化为下图（图X-X）的简易图形。

线段旁的数字为两者之间的距离，单位：km.图X-X节约里程法的求解过程如下：1.计算配送中心P 到各个配送点及各配送点之间的最短路距离，如下表最短距离表P ABCDEFP A 4.7B 2.8 6.8C 0.6 4.2 2.9D 8 12.7 6.1 8.6E 7.4 12.1 9.2 8 3.1F1.83.24.62.49.89.14.26.12.96.80.62.883.17.49.11.83.2BDFA C EP2.计算各个配送点之间的节约里程，如下表节约里程表A B C D E FAB 0.7C 1.1 0.5D 0 4.7 0E 0 1 0 12.3F 3.3 0 0 0 0.13.进行排序：节约里程排序表序号连接节约序号连接节约1 DE 12.3 8 AD 02 BD 4.7 9 AE 03 AF 3.3 10 BF 04 AC 1.1 11 CD 05 AB 0.7 12 CE 06 BC 0.5 13 CF 07 EF 0.1 14 DF 04.得出线路安排线路一：P →E →D →B →P 节约里程为：12.3+4.7= 17 km 线路二：P →F →A →C →P 节约里程为：3.3+1.1= 4.4 km如果没有使用节约里程法来进行商超的配送，那么结果是怎样的呢？假定初始配送方案是由中心点P 按最短路径向其余各个点分别进行送货，则总配送里程为：2x(0.6+4.2+1.8+7.4+8+2.8)=49.6 km 。

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

节约里程法正是用来解决这类问题的较成熟的方法。

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

节约里程法的根本思路如下图，P 为配送中心所在地，A 和B 为客户所在地，相互之间道路距离分别为a 、b 、c 。

最简单的配送方法是利用两辆车分别为A 、B 客户配送，此时，如图〔b 〕所示，车辆运行距离为2a 2b 。

然而，如果按图〔c 〕所示改用一辆车巡回配送，运行距离为abc 。

如果道路没有什么特殊情况，可以节省的车辆运行距离为2a 2b –abc =ab –c >0，这个节约量“ab –c 〞被称为“节约里程〞。

AAABPPPB（a ）物流网络（c ）用一辆车配送ac ba cb ab c图 配送中心配送路线的选择1郑克俊仓储与配送管理〔第四版〕科学出版社 修订。

步骤：实际上如果给数十家、数百家客户配送，〔1〕应首先计算包括配送中心在内的相互之间的最短距离，〔2〕然后计算各客户之间的可节约的运行距离，〔3〕按照节约运行距离的大小顺序连结各配送地并设计出配送路线。

下面举例说明节约里程法的求解过程。

例节约里程法举例图为某配送网络，P为配送中心所在地，A～J为客户所在地，共10个客户，括号内的数字为配送量〔单位：吨〕，路线上的数字为道路距离〔单位：千米〕。

现有可以利用的车辆是最大装载量为2吨和4吨的两种厢式货车，并限制车辆一次运行距离在30千米以内。

为了尽量缩短车辆运行距离，试用节约里程法设计出最正确配送路线。