Savings-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten | Quelltext bearbeiten]

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äß
  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[Bearbeiten | Quelltext bearbeiten]

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:

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[Bearbeiten | Quelltext bearbeiten]

  1. Clarke, G., Wright, J.W.: Scheduling vehicles from a central delivery depot to a number of delivery points. ORQ 12 (1964), S. 568-581.
  2. Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. Springer; Auflage: 2., überarb. Aufl. 2009 (10. Juni 2009). ISBN 978-3642015793. Seite 256.
  3. 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.
  4. Michael Neubert: „Vehicle Routing“ Proseminar Effiziente Algorithmen, TU Chemnitz S. 10 (PDF; 395 kB)

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]