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ürzestem 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äß
- 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
Dieses Beispiel verdeutlicht die Berechnung der Einsparungen durch den Savings 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:
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
- ↑ Clarke, G., Wright, J.W.: Scheduling vehicles from a central delivery depot to a number of delivery points. ORQ 12 (1964), S. 568-581.
- ↑ Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. Springer; Auflage: 2., überarb. Aufl. 2009 (10. Juni 2009). ISBN 978-3642015793. Seite 256.
- ↑ Wolfgang Domschke: Grundlagen der Betriebswirtschaftslehre: Eine Einführung aus Entscheidungsorientierter Sicht. Springer; Auflage: 4., verb. u. aktualisierte Aufl. 2008 (1. September 2008). ISBN 978-3540850779. Seite 171f.
- ↑ Michael Neubert: „Vehicle Routing“ Proseminar Effiziente Algorithmen, TU Chemnitz S. 10 (PDF; 395 kB)
Literatur
- Clarke, G., Wright, J.W.: Scheduling vehicles from a central delivery depot to a number of delivery points. ORQ 12 (1964), S. 568-581.
Weblinks
- Clarke & Wright's Savings Algorithm – Erklärung mit Beispiel (pdf; 20 kB)