- Savings-Algorithmus
-
Als Savings-Algorithmus, auch als Savings-Heuristik oder Einsparheuristik, bezeichnet man im Operations Research ein heuristisches Lösungsverfahren in der Tourenplanung. Das Verfahren wurde 1964 von Clarke und Wright erstmals publiziert.
Ziel ist dabei die insgesamt zurückgelegte Strecke zwischen einem Lager und den zu beliefernden Kunden zu minimieren. Wie für eine Heuristik charakteristisch, wird nicht garantiert, eine optimale Lösung zu finden. Die gefundene Lösung kann jedoch anschließend durch Verbesserungsverfahren, etwa mit k-Opt-Heuristiken, der optimalen Lösung angenähert werden.
Betrachtet werden dazu jeweils Kundenpaare. Das Einsparpotential ist die eingesparte Distanz, wenn beide Kunden in einer Tour nacheinander beliefert werden, gegenüber dem zurückzulegenden Weg bei einer einzelnen Belieferung der beiden Kunden direkt ab Lager.
Dabei wird klar, dass das Einsparpotential umso größer ist, je weiter die Kunden vom Lager entfernt liegen und umso näher sie sich im Verhältnis dazu zueinander befinden. Die Einsparpotentiale werden für alle Kundenpaarungen ermittelt. Die Tourplanung geht dann von der Kundenpaarung aus, die das größte Einsparpotential verspricht. Daran anschließend werden die weiteren Stationen der Tour mit den restlichen Paarungen entsprechend der Rangfolge ihrer Einsparpotentiale integriert.
Beispiel
Einsparung durch den Savings Algorithmus
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:
- Sij = Ci0 + C0j − Cij
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.
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.
Wikimedia Foundation.
