【节约里程法例题及详解】节约里程法（Savings Algorithm）是一种用于优化物流配送路径的常用方法，主要目的是通过合并配送路线来减少总行驶距离，从而提高运输效率、降低成本。该方法由Clarke和Wright于1964年提出，广泛应用于车辆路径规划（VRP）问题中。
以下是一个典型的节约里程法例题及其详细解答过程。
一、例题背景
某物流公司需要从一个仓库向多个客户点配送货物，已知各客户点之间的距离如下表所示：
| 客户 | A | B | C | D | E |
| A | 0 | 12 | 20 | 30 | 25 |
| B | 12 | 0 | 18 | 28 | 15 |
| C | 20 | 18 | 0 | 22 | 10 |
| D | 30 | 28 | 22 | 0 | 17 |
| E | 25 | 15 | 10 | 17 | 0 |
假设仓库为O点，且O到各客户的距离如下：
| 客户 | O-A | O-B | O-C | O-D | O-E |
| 距离 | 10 | 15 | 18 | 22 | 20 |
每辆车的容量足够，可以运送所有客户的需求。请使用节约里程法确定最优的配送路线。
二、解题步骤
1. 计算各客户点之间的节约值（Savings）
节约值公式为：
$$ S_{ij} = d_{Oi} + d_{Oj} - d_{ij} $$
其中，$d_{Oi}$ 表示仓库O到客户i的距离，$d_{Oj}$ 表示仓库O到客户j的距离，$d_{ij}$ 表示客户i到客户j的距离。
计算结果如下表所示：
| i\j | A | B | C | D | E |
| A | - | 12+15-12=15 | 12+18-20=10 | 12+22-30=4 | 12+20-25=7 |
| B | 15 | - | 15+18-18=15 | 15+22-28=9 | 15+20-15=20 |
| C | 10 | 15 | - | 18+22-22=20 | 18+20-10=28 |
| D | 4 | 9 | 20 | - | 22+20-17=25 |
| E | 7 | 20 | 28 | 25 | - |
> 注：i和j不能相同，因此对角线为“-”
2. 按节约值从大到小排序
根据上表，将节约值按降序排列：
| 节约值 | 客户组合 |
| 28 | C-E |
| 25 | D-E |
| 20 | C-D |
| 20 | B-C |
| 15 | B-A |
| 15 | B-E |
| 10 | A-C |
| 9 | B-D |
| 7 | A-E |
| 4 | A-D |
3. 构建初始路径
初始时，每个客户单独一条路径，如：O→A→O；O→B→O；O→C→O；O→D→O；O→E→O。
4. 合并路径（按节约值顺序）
我们依次尝试合并路径，直到无法再合并为止。
- 合并C-E：O→C→E→O（节约28）
- 合并D-E：O→D→E→C→O（节约25，但C-E已经合并，需检查是否冲突）
- 合并C-D：C-E和D不能直接合并，因为C和D之间没有连接
- 合并B-C：O→B→C→E→O（节约15）
- 合并B-E：B-C-E与E无法合并，因E已在路径中
- 合并A-C：A和C未连接，可尝试合并
- 合并A-B：O→A→B→C→E→O（节约15）
- 合并A-E：A-B-C-E已包含E，无法再合并
- 合并A-D：A-B-C-E和D无连接，可尝试合并
最终路径为：
O→A→B→C→E→D→O
三、总结与表格展示
| 步骤 | 内容说明 | |
| 1 | 计算各客户点之间的节约值 | |
| 2 | 将节约值按降序排列 | |
| 3 | 初始路径为O→客户→O | |
| 4 | 按节约值顺序合并路径 | |
| 5 | 最终路径为：O→A→B→C→E→D→O | |
| 客户组合 | 节约值 | 是否合并 |
| C-E | 28 | ✅ |
| D-E | 25 | ❌ |
| C-D | 20 | ❌ |
| B-C | 15 | ✅ |
| B-A | 15 | ✅ |
| B-E | 20 | ❌ |
| A-C | 10 | ❌ |
| B-D | 9 | ❌ |
| A-E | 7 | ❌ |
| A-D | 4 | ❌ |
四、结论
通过节约里程法，我们可以有效减少配送路线的总行驶距离，提高物流效率。本例中，最优路径为：O→A→B→C→E→D→O，总节约里程为28+15+15=58单位距离。