Vehicle Routing Problem (VRP)
Das Vehicle Routing Problem (VRP) ist das Optimierungsproblem, eine Reihe von Lieferungen einer Fahrzeugflotte zuzuordnen und die Stopps so zu reihen, dass die Kosten minimiert werden, während Bedingungen wie Kapazität und Zeitfenster eingehalten werden.
Was ist das Vehicle Routing Problem (VRP)?
VRP steht für Vehicle Routing Problem. Es verallgemeinert das Problem des Handlungsreisenden (Travelling Salesman Problem, TSP), das die kürzeste Rundreise für ein Fahrzeug sucht, auf eine ganze Flotte mit realen Nebenbedingungen: Fahrzeugkapazität, Lieferzeitfenster, Arbeitszeiten der Fahrer, Fahrzeugtypen und mehr. Dantzig und Ramser beschrieben es 1959 erstmals als „Truck Dispatching Problem“, und es gehört bis heute zu den am meisten untersuchten Problemen des Operations Research.
Die meisten praktischen Probleme sind eine Variante. Das kapazitierte VRP (CVRP) begrenzt, was jedes Fahrzeug laden kann; das VRP mit Zeitfenstern (VRPTW) fügt je Stopp ein Abhol- oder Lieferfenster hinzu; das Pickup-and-Delivery-Problem (PDP) koppelt jede Abholung an ihre Zustellung im selben Fahrzeug; und Varianten mit mehreren Depots oder gemischter Flotte lassen Fahrzeuge an verschiedenen Orten starten oder sich in Größe und Ausstattung unterscheiden.
Das VRP ist NP-schwer: Die Zahl möglicher Lösungen explodiert mit jedem Stopp. Schon ein einzelnes Fahrzeug mit zehn Stopps kann diese in 3.628.800 verschiedenen Reihenfolgen anfahren. Exakte Verfahren funktionieren nur für kleine Instanzen, daher nutzen produktive Solver Heuristiken. Ein Konstruktionsverfahren wie Nearest Neighbour oder der Savings-Algorithmus von Clarke und Wright erstellt einen ersten zulässigen Plan, und eine lokale Suche verbessert ihn mit Zügen wie 2-opt, Relocate und Swap, oft gesteuert durch eine Metaheuristik wie Simulated Annealing.
Beispiel: Ein Händler hat 3 Transporter mit 1.000 kg Nutzlast und 45 Lieferungen, jede mit einem Zeitfenster. Ein Disponent kann von Hand einen brauchbaren Plan erstellen; ein Solver hält jedes Zeitfenster und jede Nutzlast ein, minimiert die Gesamtstrecke und liefert seinen Plan in Sekunden. Lieferungen, die nicht passen, werden als ungeplant gemeldet, sodass der Disponent Kapazität ergänzen oder ein Zeitfenster lockern kann.
Die Tripoptimierung von Transportial macht den Solver zu einer Plattformeinstellung: PTV OptiFlow, PTV xTour, OSRM für die Reihenfolge eines einzelnen Fahrzeugs, CloverOpt oder der eigene Solver von Transportial, der Trips per Nearest-Neighbour-Konstruktion aufbaut, sie mit Relocate-, Swap-, Merge- und Split-Zügen verbessert und jede Route mit 2-opt verfeinert. Der Optimierer beachtet Zeitfenster, Gewicht, Fahrzeugtyp und Ausstattung, kann gesetzliche Lenkzeitpausen in Routen und ETAs einfügen und liefert eine Vorschau, die der Disponent vor dem Speichern anpasst.
Häufig gestellte Fragen
Was bedeutet VRP in der Logistik?
VRP steht für Vehicle Routing Problem: die Entscheidung, welches Fahrzeug welche Kunden in welcher Reihenfolge bedient, sodass Gesamtstrecke, -zeit oder -kosten möglichst gering sind, während jedes Fahrzeug seine Kapazität und jeder Stopp sein Zeitfenster einhält.
Was ist der Unterschied zwischen TSP und VRP?
Das Problem des Handlungsreisenden (TSP) sucht die beste Reihenfolge der Stopps für ein einzelnes Fahrzeug. Das VRP entscheidet zusätzlich, wie die Stopps unter Kapazitäts- und Zeitvorgaben auf mehrere Fahrzeuge verteilt werden; ist diese Aufteilung erfolgt, ist die Route jedes Fahrzeugs ein eigenes TSP.
Wie hilft ein VRP-Solver Disponenten?
Er erstellt automatisch effiziente Trips — ordnet Sendungen Fahrzeugen zu und bringt die Stopps in eine Reihenfolge —, sodass Disponenten weniger Zeit mit manueller Planung verbringen und die Flotte weniger leere oder unnötige Kilometer fährt, stets unter Beachtung von Kapazität, Zeitfenstern und Lenkzeitregeln.
Kann ein VRP-Solver den bestmöglichen Plan garantieren?
Nicht bei realistischen Flottengrößen: Das Optimum nachzuweisen würde viel zu lange dauern. Praktische Solver zielen auf einen sehr guten Plan innerhalb von Sekunden oder Minuten und melden, welche Stopps sie nicht einplanen konnten, und genau das brauchen Disponenten im Alltag.
Vehicle Routing Problem (VRP) in einem echten TMS erleben
Transportial setzt diese Konzepte in einer einzigen operativen Plattform um — Planung, Tracking, Dokumente und Finanzen.