节约里程法(Clarke-Wright Savings Algorithm)是求解车辆路径问题的一种启发式算法，又称节约法、节约算法。[1][2] 它以配送中心与各客户之间的距离数据为基础，计算把两条单独的往返路线合并为一条巡回路线所能减少的行驶里程，再按节约值从大到小的顺序逐步合并路线，在车辆载重、路线长度等约束下构造配送方案。[3] 该方法由克拉克(G. Clarke)与怀特(J. W. Wright)于1964年提出，因思路直观、既可手工计算也可编程实现，成为物流配送路径优化中应用最广的经典方法之一。[4][5]
定义
节约里程法的核心是一个衡量合并是否有利的指标。设配送中心编号为 0，两位客户为 i 与 j，配送中心到两位客户的距离分别为 $d_{0i}$ 和 $d_{0j}$，两位客户之间的距离为 $d_{ij}$。[1] 若两位客户分别由不同车辆往返送货，总行驶距离为 $2d_{0i}+2d_{0j}$；若改由同一辆车沿 0→i→j→0 巡回送货，总行驶距离为 $d_{0i}+d_{ij}+d_{0j}$。[1]
两种方案的距离之差记为 $S_{ij}=d_{0i}+d_{0j}-d_{ij}$，称为客户 i 与 j 之间的节约里程或节约值。[3] 由三角形两边之和大于第三边的几何性质，$S_{ij}$ 一般不小于 0，其数值越大，说明把这两位客户安排进同一条巡回路线越有利。[1][5]
背景
配送路径优化问题由 Dantzig 和 Ramser 在1959年以卡车调度问题的形式提出，此后成为运筹学与物流管理的重要研究课题。[6] 车辆路径问题及其多种变体属于 NP 困难问题，客户规模增大时精确方法的计算量上升很快，往往难以在可接受的时间内求解，实践中因而多采用能在有限时间内给出满意解的启发式方法。[5]
在节约里程法出现之前，一种直观做法是为每位客户单独派车，车辆从配送中心出发送货后原路返回；这种方案行驶距离最长，车辆利用也最不经济。[7] 当送货点数量较多时，可供选择的路线组合数量极其庞大，需要一种能快速筛选路线的迭代方法。[4]
克拉克与怀特在1964年发表于《Operations Research》的论文中给出了这一迭代程序，用于从大量可能路线中快速选出最优或接近最优的方案，文中说明该程序既可在数字计算机上运行，也适合手工计算。[4] 该文的算例取自曼彻斯特牛顿希思地区一个配送中心的送货任务。[3]
内容
算法从最简单的方案出发：每位客户各自构成一条由配送中心往返的路线，此时所需车辆数等于客户数。[8] 随后依次进行以下计算：确定配送中心与各客户之间以及各客户之间的距离矩阵；算出所有客户两两之间的节约值；将节约值按从大到小排列；从最大值开始逐对考察，把可行的路线合并起来。[5][9]
一对客户能否合并需要逐项检验：两位客户必须分属不同的路线，并且各自位于所在路线的端点；合并后车辆的装载总量不能超过车辆载重；合并后路线的长度也不能超过规定上限。[10][8] 检验通过就把两条路线在相应端点处对接成一条新路线，被连接的客户不再是端点，因而不会重复合并；这一过程反复进行，直到所有客户都被纳入路线，或剩余的合并机会都不再可行。[8][5]
节约里程法有两种常见实现方式。顺序法一次只扩展一条路线，沿着节约值列表把当前路线延伸到无法继续为止，然后才开始构建下一条；并行法则在每一步都从全局节约值列表中挑选合并机会，同时维护和合并多条路线。[2][11] 由于算法总是优先采纳当时节约值最大的连接，而已经建立的连接不再拆除，它采取的是贪婪算法式的局部选择思路。[3]
除载重与路线长度外，实际应用还常把配送时间窗、客户到货时间、每日总行驶时间上限等作为合并的检验条件。[1][10] 该算法在增加约束条件时较容易修改，能在较短时间内得到实用方案，这是它在配送调度中被广泛采用的原因之一。[9][11]
影响与争议
节约里程法被视为车辆路径问题中知名度最高的启发式方法之一，许多车辆调度软件都是依照该方法或其改进形式开发的。[12][11] 按 Toth 与 Vigo 的统计，该方法求得的解通常落在最优解 7% 的范围之内；其不足在于算法早期建立的路线质量较好，越接近尾声建立的路线质量越差，而且作为启发式方法，它并不保证得到最优解。[8] 在原始论文的算例中，为曼彻斯特牛顿希思地区一个配送中心的 30 位客户安排送货，原有做法需要 10 条路线、总里程 1766 英里，改用节约法后缩减为 8 条路线、1427 英里；原文结尾提到将另文发表一份案例研究，但没有证据显示该文后来刊出。[3]
关于两种实现方式的优劣，比较研究给出的结论较为一致。Laporte 和 Semet 在标准基准问题上的测试显示，并行版配合 3-opt 后处理能够取得明显优于顺序版的结果；Toth 与 Vigo 公布的基准数据中，并行版的总距离也普遍短于顺序版。[11][13]
后续研究对节约值的定义提出了多种修正。一种做法是引入标量参数 θ，使节约函数在距离之外还考虑各点相对配送中心的位置关系；另一种常见的修改形式是把公式改为 $s_{ij}=c_{i0}+c_{0j}-\gamma c_{ij}$，以抑制原始算法容易生成的外围弧形路线。[8][11] 还有研究把路线合并过程与匹配算法、匈牙利算法等方法结合，以同时兼顾总行驶距离和车辆使用数等目标。[11][5]
该方法也存在被明确指出的局限。有研究比较带时间窗的路径构造方法后发现，插入类方法总体明显优于以节约值为基础的构造方法；在异质车队等更复杂的车辆路径问题中，节约里程法需要额外适配，或与禁忌搜索等元启发式方法结合使用，且客户规模较大时效果下降。[14][15][7] 一项针对多种节约法变体的计算测试表明，各变体之间难以判定孰优孰劣，解的质量与计算时间之间存在明显权衡，质量上的微小提升往往需要付出很大的计算代价。[12]
参见
参考资料
- bookdetail . sinobook.com.cn [引用日期2026-09-27]
- Summary . tudelft.nl [引用日期2026-09-27]
- Volume 25 (2), pp . ac.za [引用日期2026-09-27]
- detailv2 . ebsco.com [引用日期2026-09-27]
- IJAM_55_10_08(PDF) . iaeng.org [引用日期2026-09-27]
- * [17] Dantzig, G . journal-aprie.com [引用日期2026-09-27]
- _4.5. Heurísticas-base_ . usp.br [引用日期2026-09-27]
- GRI-2019-24449(PDF) . auth.gr [引用日期2026-09-27]
- Skripsi_Maulidah_Hanik_Malihatin_(115060701111053)(PDF) . ac.id [引用日期2026-09-27]
- _pdf . jst.go.jp [引用日期2026-09-27]
- Das GENIUS-Verfahren wurde in Gendreau et al . uni-regensburg.de [引用日期2026-09-27]
- INPE-5361-RPQ/656 . inpe.br [引用日期2026-09-27]
- | 3 | - | 27 | 30 | 30 | 0 | . ac.id [引用日期2026-09-27]
- 10966-Kisjes . eur.nl [引用日期2026-09-27]
- pub_geral . up.pt [引用日期2026-09-27]
浏览次数：0 次
阅读量：0 次 · 阅读完成量：0 次
最近更新：2026-09-27T14:39:19Z
完成率 = 阅读完成量 ÷ 阅读量，分母是阅读量不是浏览次数 —— 关了 JS 的、秒退的都在浏览次数里、不在阅读量里。 详细口径在后台的「数据统计」页。