Savings-Algorithmus

• Der Savings-Algorithmus (auch Clarke-Wright Savings Algorithmus) ist ein heuristisches Verfahren zur Lösung von Routing-Problemen

• dabei wird nicht unbedingt die beste Lösung gefunden, aber es ist praktisch und führt zu einer ausreichend guten Lösung

• Es wird angenommen, dass vom Ausgangsknoten alle weiteren Knoten direkt angefahren werden. Dadurch fällt bei jedem Knoten ein Hin- und ein Rückweg an. Also das dopplete der einfachen Strecke

• Statt gleich eine optimale Route zu suchen, beginnt der Algorithmus mit einer einfachen, naiven Lösung – jeder Kunde bekommt eine eigene Tour vom Depot aus. Dann schaut man:

  Wie viel "Strecke" oder "Kosten" kann man einsparen, wenn man zwei dieser Touren zusammenlegt?

  Diese Einsparung nennt man "Savings", also „Ersparnis“.

Alle Werte für jeden einmaligen Weg notieren

Routen Berechnen mit hin und Rückweg

Route kombinieren zu einer Rundtour und Savings berechnen

Das für alle Kombinationen fortführen…

Sortieren der berechneten Savings in einer Tabelle

Prüfung der Route mit der höchsten Einsparung auf Kapazitätseinhaltung

Streckenlänge berechnen

Weitere Kunden in Rundtour mit einbeziehen und dafür zunächst Kapazitätsprüfung der weiteren Möglichkeiten, um unpassende Route von vornherein auszuschließen

Savings für infragekommende Kunden berechnen

Neuen Einsparungen in Savingstabelle übertragen

Streckenlänge berechnen

Weitere Kunden mit einbeziehen, dafür Kapazitätsprüfung

Da keine Kapazität für weitere Kunden übrig ist muss eine neue Tour geplant werden, dafür wird eine Kapazitätsprüfung und anschließend eine Savings-Berechnung der übrigen Touren durchgeführt