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

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

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

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