Lösungsansätze für das Vehicle Routing

Von den in der Einleitung dieser Unit angegebenen Lösungsansätzen sollen hier insbesondere die beiden ersten erläutert werden, exakte und heuristische Verfahren.

Exakte Lösungsverfahren

Exakte Verfahren versuchen die Weglängen aller möglichen Rundreisen zu berechnen und dabei die kleinste Weglänge auszuwählen. Bei dem Travelling-Salesman Problem bzw. Vehicle Routing Problem handelt es sich jedoch oft um ein deterministisch polynomial nicht mehr lösbares Problem (NP-schweres Problem), der Aufwand für die Berechnung sämtlicher möglicher Routen ist also zu hoch (Solomon 1987). Insbesondere bei der Lieferroutenplanung, sind es oft sehr viele Stationen (Kunden), die beliefert werden müssen.

Heuristische Lösungsverfahren

Heuristische Lösungesverfahren sind unumgänglich, wenn es sich um eine grosse Menge an zu verarbeitenden Daten (z.B. zu beliefernde Kunden) handelt. Sie lassen sich untergliedern in Eröffnungverfahren (oder auch Konstruktionsverfahren) und Verbesserungsverfahren, je nachdem, ob neue Routen konstruiert werden, oder bestehende Routen verbessert werden. Ihnen fehlt allerdings die Möglichkeit eine Güteabschätzung der mit ihnen ermittelten Routen vorzunehmen.

Eröffnungsverfahren nutzen z.B. die Nearest-Neighbour-Heuristik um an jedem Standpunkt sich für das nächstgelegene Ziel entsprechend der Länge der Verbindungslinien zu entscheiden (siehe Dijkstra). In der Nearest-Insertion-Heuristik hingegen wird zusätzlich überprüft, ob sich Stationen in der Nähe der Verbindungslinien zwischen zwei Stationen befinden. Ist eine solche Station gefunden, wird sie zwischengeschaltet.

Mit Hilfe von Verbesserungsverfahren wird versucht, eine Verkürzung existierender Routen mittels kleinerer Modifikationen zu erzielen.

Bott und Ballue nennen vier verschiedene Kategorien heuristischer Ansätze zur Lösung des Vehicle-Routing-Problems (Bott et al. 1986):

• Cluster first, Route second Ansätze
• Route first, Cluster second Ansätze
• Savings or insertion Ansätze
• Exchange or improvement Ansätze

Es ist zu beachten, dass in der Praxis häufig kombinierte Verfahren wie etwa die Cluster first, Route second Ansätze zum Einsatz kommen. Hier erfolgt zuerst eine Zuordnung von Kunden zu den Depots, erst danach erfolgt das eigentliche Routing. Andere Herangehensweisen gehen davon aus, dass eine nicht adäquate Zuordnung zu einem schlechten Routing führt, so dass eine erste Einteilung der Routen durch Modifikation sukzessive verbessert wird (exchange or improvement Ansätze) (Foulds 1997).