Savings-Algorithmus

Als Savings-Algorithmus (auch Sparalgorithmus, Savings-Heuristik oder Einsparheuristik) bezeichnet man im Operations Research ein heuristisches Lösungsverfahren in der Tourenplanung. Das 1964 von Clarke und Wright erstmals publizierte Verfahren ist in der Praxis eines der am häufigst eingesetzten.

Die Heuristik versucht dem kürzesten Pfad zwischen einem Ausgangs- und Endknoten und verschiedenen Zwischenknoten möglichst nahezukommen (Problem des Handlungsreisenden). Die Lösung kann weiteren Verbesserungsverfahren, wie etwa den k-Opt-Heuristiken, als Ausgangslösung dienen.

Beim Savings-Algorithmus erfolgen Tourenbildung und Reihenfolgebestimmung innerhalb der Touren simultan. Man kann zwei Versionen des Verfahrens unterscheiden: eine parallele und eine sequentielle Vorgehensweise.

Algorithmus

Eine symmetrische Entfernungsmatrix ist eine der Voraussetzungen für den Algorithmus.

1. Verbinde jeden Knoten (Kunden) mit dem Ausgangsknoten (Depot) über eine Hin- und Rückkante (Weg); es entstehen Pendeltouren.
2. Löse bei allen möglichen Kombinationen jeweils eine Hin- und eine Rückkante und verbinde die beiden Knoten mit einer Kante.
3. Bewerte alle im Schritt 2 entstandenen Savings gemäß $S_{\text{i,j}}=d_{\text{i,rück}}+d_{\text{j,hin}}-d_{\text{i,j}}$
4. Sortiere alle Savings in absteigender Reihenfolge.
5. Verbinde die beiden Knoten die das beste verbliebene Saving haben und noch mindestens eine Kante zum Ausgangspunkt.
6. Wiederhole Schritt 5 solange noch mehr als zwei Kanten zum Ausgangspunkt existieren.
7. Existieren nur noch zwei Kanten zum Ausgangspunkt ist eine Lösung erreicht.

Beispiel

Einsparung durch den Savings-Algorithmus

Dieses Beispiel verdeutlicht die Berechnung der Einsparungen durch den Saving-Algorithmus. In nebenstehender Grafik stellen i und j die Kunden und 0 das Depot dar. Der Weg nach i kostet hin und zurück je 5 Einheiten, der Weg nach j 7 Einheiten. Der Weg zwischen i und j kostet 3 Einheiten.

Nun berechnet man für alle Kundenpaare (in diesem Fall nur eines) die mögliche Einsparung:

$S_{ij}=C_{i0}+C_{0j}-C_{ij}$

In diesem Fall ergeben sich beim Zusammenlegen der beiden Touren aus dem linken Graph Einsparungen in Höhe von 9 Einheiten. Existieren mehrere Kundenpaare ordnet man im nächsten Schritt die Paare absteigend nach der möglichen Einsparung und beginnt dann oben die Touren zusammenzufügen.

Literatur

• G. Clarke, J. W. Wright: Scheduling vehicles from a central delivery depot to a number of delivery points. In: Operations Research Quarterly. Band 12, 1964, S. 568–581.

Weblinks

• Clarke & Wright's Savings Algorithm – Erklärung mit Beispiel (PDF; 20 kB)