Glossar · approach
Clarke-Wright Savings
Klassische Heuristik von 1964 für das Capacitated Vehicle Routing Problem: jeder Kunde startet auf einer eigenen Tour; Paare von Touren werden iterativ nach größter 'Ersparnis' verschmolzen, bis die Kapazität weitere Verschmelzungen verhindert.
Clarke-Wright-AlgorithmusSavings-AlgorithmusEinspar-AlgorithmusClarke und Wright 1964
Der Clarke-Wright-Savings-Algorithmus, von Clarke und Wright 1964 in *Operations Research* eingeführt, ist die klassische und einfachste konstruktive Heuristik für CVRP. Anfangs liegt jeder Kunde auf einer eigenen Hin-Rück-Tour (Depot → Kunde → Depot). Für jedes Kundenpaar (i, j) wird die 'Ersparnis' s(i, j) = d(Depot, i) + d(Depot, j) − d(i, j) berechnet — die Streckenreduktion, wenn die zwei Einzelkunden-Touren zu einer Tour Depot → i → j → Depot verschmolzen werden. Die Paare werden nach absteigender Ersparnis sortiert; der Algorithmus läuft die Liste durch und verschmilzt zwei Touren, wann immer die Kapazität es zulässt. Er läuft in Sekunden auf 100-200 Kunden und landet typischerweise innerhalb von 5-10 % des Optimums. Trotz seines Alters von über sechzig Jahren und der Tatsache, dass er der digitalen Optimierung vorausging, bleibt Clarke-Wright ein praktischer Benchmark für mittlere CVRP-Instanzen und ein Standard-Warmstart für anspruchsvollere Metaheuristiken wie 2-opt, Or-opt und ALNS.
Örnek
Zwei Einzelkunden-Touren (Depot → A → Depot und Depot → B → Depot) ergeben beim Zusammenführen zu Depot → A → B → Depot eine Ersparnis von 8 km. Erlaubt die Kapazität die Verschmelzung, wird sie durchgeführt; die Ersparnisliste wird von oben nach unten abgearbeitet, bis keine kapazitätsverträgliche Verschmelzung mehr verbleibt.