【节约里程法例题及详解】节约里程法（Savings Algorithm）是一种用于优化物流配送路径的常用方法，主要用于解决车辆路径问题（Vehicle Routing Problem, VRP）。该方法通过计算不同客户之间的“节省距离”，从而确定最优的配送路线，以减少总行驶距离，提高运输效率。
以下是一个典型的节约里程法例题及其详细解答过程，采用加表格的形式进行展示。
一、例题背景
某物流公司需要从一个仓库出发，向5个客户点（A、B、C、D、E）配送货物。已知各客户点之间的单程距离如下表所示：
| 距离 | A | B | C | D | E |
| A | 0 | 12 | 18 | 24 | 30 |
| B | 12 | 0 | 10 | 16 | 22 |
| C | 18 | 10 | 0 | 14 | 20 |
| D | 24 | 16 | 14 | 0 | 18 |
| E | 30 | 22 | 20 | 18 | 0 |
假设所有配送任务必须由一辆车完成，且每辆车只能在一天内完成一次配送任务。请使用节约里程法求出最优配送路线。
二、解题步骤
1. 计算每个客户点之间的节约里程
节约里程是指将两个客户点合并为一条路线后，相对于分别单独配送所节省的距离。公式如下：
$$
\text{Savings}(i,j) = d_{0i} + d_{0j} - d_{ij}
$$
其中：
- $d_{0i}$：仓库到客户i的距离；
- $d_{0j}$：仓库到客户j的距离；
- $d_{ij}$：客户i到客户j的距离；
根据题目中的距离表，我们先计算每个客户点对之间的节约里程，并按从大到小排序。
2. 建立节约里程表并排序
以下是各客户点对之间的节约里程计算结果（假设仓库为O，距离为0）：
| 客户对 | d₀i | d₀j | dij | Savings(i,j) |
| A-B | 12 | 12 | 12 | 12+12-12=12 |
| A-C | 12 | 18 | 18 | 12+18-18=12 |
| A-D | 12 | 24 | 24 | 12+24-24=12 |
| A-E | 12 | 30 | 30 | 12+30-30=12 |
| B-C | 12 | 18 | 10 | 12+18-10=20 |
| B-D | 12 | 24 | 16 | 12+24-16=20 |
| B-E | 12 | 30 | 22 | 12+30-22=20 |
| C-D | 18 | 24 | 14 | 18+24-14=28 |
| C-E | 18 | 30 | 20 | 18+30-20=28 |
| D-E | 24 | 30 | 18 | 24+30-18=36 |
按节约里程从高到低排序：
| 客户对 | Savings |
| D-E | 36 |
| C-D | 28 |
| C-E | 28 |
| B-C | 20 |
| B-D | 20 |
| B-E | 20 |
| A-B | 12 |
| A-C | 12 |
| A-D | 12 |
| A-E | 12 |
三、构建配送路线
初始时，每个客户点都是独立的路线，即：O → A → O；O → B → O；O → C → O；O → D → O；O → E → O。
然后按照节约里程由高到低依次尝试合并路线：
1. D-E（36）：合并D和E，形成O → D → E → O。
2. C-D（28）：D已在当前路线中，C未加入，可合并C与D，形成O → C → D → E → O。
3. C-E（28）：C和E都在当前路线中，无需再合并。
4. B-C（20）：B未加入，C在当前路线中，可合并B与C，形成O → B → C → D → E → O。
5. B-D（20）：B和D均在当前路线中，无需再合并。
6. B-E（20）：B和E均在当前路线中，无需再合并。
7. A-B（12）：A未加入，B在当前路线中，可合并A与B，形成O → A → B → C → D → E → O。
最终路线为：
O → A → B → C → D → E → O
四、总结
| 步骤 | 操作 | 结果 |
| 1 | 计算节约里程 | 得到客户对的节约值 |
| 2 | 排序节约里程 | 按从高到低排列 |
| 3 | 合并路线 | 逐步合并客户点，形成最短路径 |
| 4 | 最终路线 | O → A → B → C → D → E → O |
通过节约里程法，可以有效减少配送路径的总行驶距离，提升物流效率。本例中，通过合理合并客户点，最终形成了一个高效的配送路线。
