Das Vehicle Routing Problem (VRP) Erklärt

1. Was ist das Vehicle Routing Problem?

Das Vehicle Routing Problem (VRP) oder Tourenplanungsproblem ist ein Problem der kombinatorischen Optimierung und der ganzzahligen Programmierung, das die Frage stellt: "Was ist die optimale Menge von Routen für eine Fahrzeugflotte, um eine gegebene Menge von Kunden zu beliefern?"

Das 1959 von George Dantzig und John Ramser eingeführte VRP ist ein zentrales Problem in den Bereichen Transport, Distribution und Logistik. Das Ziel besteht typischerweise darin, die Gesamtkosten der Route zu minimieren (was die Minimierung von Entfernung, Zeit, Kraftstoff oder der Anzahl der eingesetzten Fahrzeuge bedeuten kann), während sichergestellt wird, dass jeder Kunde genau einmal besucht wird.

In einem Standard-VRP:

• Es gibt ein zentrales Depot, an dem alle Fahrzeuge ihre Fahrten beginnen und beenden.
• Es gibt eine Flotte von Fahrzeugen, von denen im Basisproblem angenommen wird, dass sie identisch sind.
• Es gibt eine Menge von Kunden, die sich jeweils an einem bestimmten Knoten eines Graphen befinden.

2. VRP vs. TSP: Den Unterschied verstehen

Wenn Sie mit Graphentheorie vertraut sind, klingt das VRP verdächtig nach dem Problem des Handlungsreisenden (TSP). Tatsächlich ist das VRP eine Verallgemeinerung des TSP.

Der Hauptunterschied ist die Anzahl der Akteure:

• TSP: Sie haben einen Handlungsreisenden, der jede Stadt besuchen und nach Hause zurückkehren muss.
• VRP: Sie haben mehrere Fahrzeuge. Sie müssen zunächst die Städte clustern (eine bestimmte Gruppe von Städten Fahrzeug A zuweisen, eine andere Gruppe Fahrzeug B) und dann für jedes Fahrzeug ein Mini-TSP lösen.

Da das TSP bereits NP-schwer ist (rechnerisch unlösbar für exakte Lösungen in großen Maßstäben), ist das VRP ebenfalls NP-schwer, jedoch aufgrund der zusätzlichen Clustering-Dimension wesentlich komplexer.

3. Häufige Variationen von VRP

Das Basis-VRP geht von einer unbegrenzten Fahrzeugkapazität und keinen zeitlichen Einschränkungen aus. In der realen Welt kann ein FedEx-LKW keine unbegrenzte Anzahl von Paketen befördern. Dies hat zur Schaffung mehrerer äußerst praktischer Variationen des VRP geführt.

Capacitated Vehicle Routing Problem (CVRP)

Beim CVRP (kapazitiertes VRP) hat jedes Fahrzeug eine maximale Ladekapazität (z. B. ein LKW kann 500 kg aufnehmen), und jeder Kunde hat eine bestimmte Nachfrage (z. B. Kunde A benötigt 50 kg Waren). Die Route eines Fahrzeugs muss enden und es muss zum Depot zurückkehren, bevor die Summe der Nachfragen auf seiner Route seine Kapazität überschreitet. Dies ist die am häufigsten untersuchte Variante in der Operations Research.

Vehicle Routing Problem with Time Windows (VRPTW)

Beim VRPTW (VRP mit Zeitfenstern) benötigen Kunden Lieferungen innerhalb bestimmter Zeitrahmen. Zum Beispiel benötigt ein Restaurant möglicherweise seine Zutaten zwischen 8:00 und 10:00 Uhr. Kommt ein LKW um 7:30 Uhr an, muss er warten. Kommt er um 10:15 Uhr an, schlägt die Lieferung fehl. Dies fügt der Routing-Logik strenge Zeitvorgaben hinzu.

Andere bemerkenswerte Variationen

• VRPPD (Pickup and Delivery): Fahrzeuge liefern nicht nur Waren ab; sie holen sie auch von Kunden ab und liefern sie an andere Kunden (wie Uber oder DoorDash).
• MDVRP (Multi-Depot VRP): Ein Unternehmen hat mehrere Lager (Depots). Der Algorithmus muss nicht nur über die Routen entscheiden, sondern auch darüber, welches Depot welchen Kunden bedient.
• SDVRP (Split Delivery VRP): Die Nachfrage eines Kunden ist so groß, dass sie aufgeteilt und von mehreren verschiedenen Fahrzeugen erfüllt werden kann.

4. Wie wird das VRP gelöst?

Da das VRP NP-schwer ist, ist die Berechnung der absolut perfekten Menge von Routen für Hunderte von Kunden praktisch unmöglich. Stattdessen verlassen sich Logistikunternehmen auf einen zweiphasigen Ansatz, um sehr schnell "nahezu optimale" Routen zu finden.

Phase 1: Zuerst Clustern, dann Routen

Der intuitivste menschliche Ansatz wird auch von Algorithmen verwendet. Zunächst werden die Kunden basierend auf der geografischen Nähe und der Fahrzeugkapazität in Cluster gruppiert. Sobald Sie einem bestimmten LKW ein Cluster von Kunden zugewiesen haben, behandeln Sie dieses Cluster als ein eigenständiges Problem des Handlungsreisenden und suchen nach dem kürzesten Pfad.

Phase 2: Metaheuristiken

Sobald eine anfängliche Menge von Routen festgelegt ist, versuchen Algorithmen, diese kontinuierlich zu verbessern. Diese sind als Metaheuristiken bekannt.

• Simulated Annealing (Simulierte Abkühlung): Der Algorithmus akzeptiert gelegentlich kurzfristig "schlechtere" Routen, um lokalen Optima zu entkommen, und kühlt sich langsam ab, um sich auf eine global effiziente Route einzupendeln.
• Genetische Algorithmen: Nimmt mehrere gute Routing-Lösungen, "kreuzt" sie miteinander, indem Routenabschnitte ausgetauscht werden, und behält die "fittesten" (kürzesten) Nachkommen.
• Tabu-Suche: Eine aggressive lokale Suche, die ein Gedächtnis (eine Tabu-Liste) von kürzlich evaluierten Routen behält, um zu verhindern, dass der Algorithmus in Endlosschleifen stecken bleibt.

5. Der Clarke-Wright-Savings-Algorithmus

Wenn Sie einen VRP-Solver schreiben möchten, ist der beste Ausgangspunkt der 1964 entwickelte Clarke-Wright-Savings-Algorithmus. Er ist nach wie vor eine der bekanntesten und am weitesten verbreiteten Heuristiken für das Kapazitierte VRP (CVRP).

Die Logik basiert auf dem Konzept der "Einsparungen" (Savings).

1. Beginnen Sie mit dem Worst-Case: Stellen Sie sich vor, Sie haben 10 Kunden. Sie senden 10 separate LKWs vom Depot aus. LKW 1 fährt zu Kunde 1 und kehrt zurück. LKW 2 fährt zu Kunde 2 und kehrt zurück usw.
2. Einsparungen berechnen: Wenn Sie die Routen kombinieren (Depot -> Kunde 1 -> Kunde 2 -> Depot), wie viel Entfernung sparen Sie im Vergleich zum Senden zweier separater LKWs? Sie berechnen diesen "Einsparungs"-Wert für jedes mögliche Kundenpaar.
3. Sortieren und Zusammenführen: Sie sortieren die Paare nach den höchsten Einsparungen. Anschließend führen Sie Routen aggressiv zusammen, beginnend mit den größten Einsparungen, vorausgesetzt, die kombinierte Route überschreitet nicht die maximale Kapazität des Fahrzeugs.

Dieser Algorithmus läuft in O(n^2 log n) Zeit ab und erzeugt fast sofort hocheffiziente Routen, die als Grundlage dienen, auf der Metaheuristiken aufbauen können.

6. Reale Anwendungen

Eine 5%ige Verbesserung bei der VRP-Optimierung bedeutet für Großkonzerne Einsparungen in Millionenhöhe.

• Paketzustellung (UPS/FedEx): UPS nutzt bekanntermaßen ein Optimierungssystem namens ORION (On-Road Integrated Optimization and Navigation). Durch die starke Pönalisierung von Linksabbiege-Vorgängen in ihren VRP-Berechnungen (die beim Warten an Ampeln Kraftstoff verschwenden), spart UPS über 10 Millionen Gallonen Kraftstoff pro Jahr.
• Ridesharing (Uber/Lyft): UberPool ist ein massives, dynamisches VRP mit Pickup and Delivery in Echtzeit. Der Algorithmus muss Fahrzeuge kontinuierlich neu clustern und umleiten, wenn dynamisch neue Fahrtanfragen auftauchen.
• Abfallwirtschaft: Müllwagen müssen durch jede Straße in einer Stadt fahren (eine Untergruppe von VRP, die als Capacitated Arc Routing Problem bekannt ist), um sicherzustellen, dass die Lastwagen zur Mülldeponie zurückkehren, bevor sie ihre Gewichtsgrenzen erreichen.