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[1] ist in der Praxis eines der am häufigst eingesetzten.[2]

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.[3]

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äß ${\displaystyle 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:

${\displaystyle 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.[4]

Einzelnachweise

1. 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.
2. Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. 2., überarb. Auflage. Springer, 2009, ISBN 978-3-642-01579-3, S. 256.
3. Wolfgang Domschke: Grundlagen der Betriebswirtschaftslehre: Eine Einführung aus Entscheidungsorientierter Sicht. 4., verb. u. aktualisierte Auflage. Springer, 2008, ISBN 978-3-540-85077-9, S. 171f.
4. Michael Neubert: Vehicle Routing. (PDF; 395 kB). Proseminar Effiziente Algorithmen, TU Chemnitz S. 10.

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)