クラークとライトの節約法が配送ルートを手計算可能にした

1964年、マンチェスターの協同卸売組合で働いていたG・クラークとJ・W・ライトは、『Operations Research』誌に「中央倉庫から複数の配送地点への車両のスケジューリング」を発表した。彼らの狙いは、ダンツィヒとラムザーが1959年に定式化したルーティング問題であった。その問題は、厳密解の計算が遅すぎて実用的でなかった。

彼らの節約アルゴリズムは、ほとんど気恥ずかしいほど単純である。まず各顧客ごとに別々の往復ルートから始め、次に顧客の各組について、2つのルートでサービスする代わりに1つのルートでサービスすることでどれだけ距離を節約できるかを計算する。そして、車両の容量が許す限り、節約量が最大の組から順に統合していく。南デンマーク大学の講義では今でも、容量制約付き車両ルーティングの古典的な構成的ヒューリスティックとしてこれを教えている。

厳密手法が通用しなかったところでそれは機能した。ルートは手計算でも、初期のコンピュータでも計算でき、この手法は標準的な構成要素となった。すなわち、2-opt、タブー探索、遺伝的アルゴリズムといった後のメタヒューリスティックが改良を加える、強力な初期解である。

最も距離を節約できる組を最初に統合する

節約量の尺度により、貪欲な選択が正しい選択になった

高価な計算能力なしで実行できた

容量制約は統合の過程で自然に扱われた

その出力は数十年にわたるより優れたアルゴリズムの種となった

厳密な答えのコストが高すぎる場合、適切な尺度（「節約量」）に基づく貪欲な規則で価値の大部分を得られる。しかもそれは今日でも計算できる。

クラーク=ライトの節約アルゴリズムは車両ルーティングにおいて最も引用されるアイデアの一つとなり、今日でも教科書やソフトウェアで基準として、しばしば配送車両群のルート最適化の出発点として用いられている。