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.

Verbinde jeden Knoten (Kunden) mit dem Ausgangsknoten (Depot) über eine Hin- und Rückkante (Weg); es entstehen Pendeltouren.
Löse bei allen möglichen Kombinationen jeweils eine Hin- und eine Rückkante und verbinde die beiden Knoten mit einer Kante.
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}}$
Sortiere alle Savings in absteigender Reihenfolge.
Verbinde die beiden Knoten die das beste verbliebene Saving haben und noch mindestens eine Kante zum Ausgangspunkt.
Wiederhole Schritt 5 solange noch mehr als zwei Kanten zum Ausgangspunkt existieren.
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.^[4]

Einzelnachweise

↑ 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.
↑ Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. 2., überarb. Auflage. Springer, 2009, ISBN 978-3-642-01579-3, S. 256.
↑ 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.
↑ 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)

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

[1]

[2]

[3]

[4]