Quelltext der Seite Savings-Algorithmus

Als '''Savings-Algorithmus''' (auch Sparalgorithmus, Savings-Heuristik oder Einsparheuristik) bezeichnet man im [[Operations Research]] ein [[Heuristik|heuristisches]] Lösungsverfahren in der [[Vehicle Routing Problem|Tourenplanung]]. Das 1964 von Clarke und Wright erstmals publizierte Verfahren<ref>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.</ref> ist in der Praxis eines der am häufigst eingesetzten.<ref>Leena Suhl, Taieb Mellouli: ''Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen.'' 2., überarb. Auflage. Springer, 2009, ISBN 978-3-642-01579-3, S. 256.</ref>

Die [[Heuristik]] versucht dem [[Kürzester Pfad|kürzesten Pfad]] zwischen einem Ausgangs- und Endknoten und verschiedenen [[Knoten (Graphentheorie)|Zwischenknoten]] möglichst nahezukommen (''[[Problem des Handlungsreisenden]]''). Die Lösung kann weiteren [[Problem des Handlungsreisenden#Verbesserungsverfahren|Verbesserungsverfahren]], wie etwa den [[k-Opt-Heuristik]]en, 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.<ref>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.</ref>

== 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äß <math>S_\text{i,j}=d_\text{i,rück}+d_\text{j,hin}-d_\text{i,j}</math>
# 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 ==
[[Datei:Savings-Algorithm-Beispiel.PNG|mini|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:
:<math>S_{ij} = C_{i0} + C_{0j} - C_{ij}</math>
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.<ref>Michael Neubert: [http://www.tu-chemnitz.de/informatik/ThIS/downloads/courses/ss02/effalg/neubert.pdf ''Vehicle Routing.''] (PDF; 395&nbsp;kB). Proseminar Effiziente Algorithmen, TU Chemnitz S. 10.</ref>

== Einzelnachweise ==
<references />

== 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 ==
* [http://pure.au.dk/portal-asb-student/files/36025757/Bilag_E_SAVINGSNOTE.pdf Clarke & Wright's Savings Algorithm] – Erklärung mit Beispiel (PDF; 20&nbsp;kB)
[[Kategorie:Reise- und Routenplanung]]
[[Kategorie:Operations Research]]