克拉克和赖特的节约法：让配送路线能用手算

1964年，G. 克拉克和J. W. 赖特与曼彻斯特的合作批发协会合作，在《运筹学》杂志上发表了《从中心仓库向多个配送点调度车辆》。他们针对的是丹齐格和拉姆泽在1959年形式化的路径问题——而该问题的精确解计算太慢。

他们的节约算法简单得几乎让人难为情：先为每个客户单独规划一条往返路线，然后计算每一对客户合并成一条线路比分开两条线路能省多少距离；按节省量从大到小合并线路对，只要车辆容量允许。南丹麦大学的一门课程至今仍将这种算法作为容量受限车辆路径问题的经典构造式启发式方法。

精确方法行不通的地方，它却管用：路线可以手工计算或用早期计算机计算，这种方法成了标准积木——一个强大的初始解，后来由2-opt、禁忌搜索和遗传算法等元启发式算法进行优化。

先合并节省距离最多的路线对

节约量这个指标让贪心选择成为正确选择

运行不需要昂贵的计算能力

合并过程中自然处理容量限制

它的输出为后续几十年的更优算法奠定了基础

当精确答案代价太高时，在正确的指标（“节约量”）上使用贪心规则，能获得大部分价值——而且你今天就能算出来。

克拉克-赖特节约算法成为车辆路径问题中被引用最多的思想之一，至今仍是教科书和软件中的基线方法，常作为配送车队路线优化的起点。