Einsparheuristik

Als Einsparheuristik bzw. Savings-Heuristik bezeichnet man im Operations Research ein heuristisches Lösungsverfahren in der Tourenplanung.

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 gefunden. 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.