Das Vehicle Routing Problem für die Praxis erklärt:
Montag, kurz nach sechs. Die Aufträge für den Tag sind da, und die Disposition verteilt sie wie seit Jahren: nach Postleitzahl. Alles mit 44 kommt auf die eine Tour, alles mit 45 auf die andere. Das geht schnell, und jeder kennt sein Gebiet. Nur halten sich die Aufträge nicht an Postleitzahlen. Heute hat ein Gebiet zwölf Aufträge und das Nachbargebiet drei, morgen ist es umgekehrt. Am Ende fährt ein Lkw halb leer, während nebenan ein zusätzliches Fahrzeug gebraucht wird. Wer seine Lkw pro Tag mietet, zahlt dafür jedes Mal drauf.
Dahinter steckt eine einfache Frage: Welche Aufträge kommen zusammen auf welchen Lkw, und in welcher Reihenfolge werden die Kunden angefahren? In der Forschung hat diese Frage einen Namen. Sie heißt Vehicle Routing Problem, kurz VRP, auf Deutsch Tourenplanungsproblem.
Was hinter dem VRP steckt
In seiner Grundform ist das VRP schnell erklärt. Es gibt ein Lager, eine Reihe von Kunden mit bekannter Bestellmenge und eine Flotte gleich großer Fahrzeuge. Jeder Kunde wird genau einmal angefahren, jede Tour beginnt und endet im Lager, und kein Lkw darf mehr laden, als er tragen kann. Gesucht sind die Touren mit der kürzesten Gesamtstrecke oder den wenigsten Fahrzeugen. George Dantzig und John Ramser haben das Problem 1959 zum ersten Mal beschrieben, damals ging es um die Belieferung von Tankstellen mit Benzin. Seitdem gehört es zu den meistuntersuchten Fragestellungen im Operations Research.
Dass sich Forschende seit über 60 Jahren daran abarbeiten, liegt an einer unangenehmen Eigenschaft: Mit jedem Kunden wächst die Zahl der möglichen Lösungen explosionsartig. Schon zehn Kunden kann ein einzelner Lkw in über 3,6 Millionen verschiedenen Reihenfolgen anfahren. Bei 50 Kunden hat diese Zahl 65 Stellen. Alles durchzurechnen ist damit schon bei einem normalen Tagesgeschäft ausgeschlossen, auch mit dem schnellsten Rechner. In der Praxis setzt man deshalb Heuristiken ein, also Verfahren, die geschickt suchen, statt alles auszuprobieren. Sie finden in Sekunden oder Minuten sehr gute Lösungen, können aber nicht beweisen, dass es keine bessere gibt. Für die Disposition reicht das in aller Regel völlig aus.
Vom Lehrbuch in die Praxis
Das Grundmodell ist für den Alltag zu einfach. Über die Jahrzehnte ist deshalb eine ganze Familie von Erweiterungen entstanden, die jeweils eine reale Bedingung ergänzen. Ihre Kürzel tauchen in Fachartikeln genauso auf, wie in den Produktbeschreibungen von Planungssoftware.
Schon die Ladegrenze aus dem Grundmodell hat ihr eigenes Kürzel: CVRP, das Capacitated VRP. Nehmen Kunden nur zu bestimmten Zeiten Ware an, wird daraus das VRP mit Zeitfenstern (VRPTW). Wer schon einmal vor einem geschlossenen Wareneingang gestanden hat, weiß, warum das eine der wichtigsten Erweiterungen ist. Sind die Fahrzeuge unterschiedlich groß, etwa Sattelzüge und Solo-Lkw, spricht man von einer heterogenen Flotte. Dazu gehört auch die Frage, welches Fahrzeug überhaupt auf welches Werksgelände passt. Liefern mehrere Standorte aus, entsteht ein Multi-Depot-Problem (MDVRP), und es muss zusätzlich entschieden werden, welcher Standort welchen Kunden beliefert. Und wird unterwegs nicht nur abgeliefert, sondern auch abgeholt ist von Pickup and Delivery die Rede.
Und das ist nur ein kleiner Ausschnitt. Praxisnahe Modelle bringen schnell viele weitere Bedingungen mit, etwa Lenk- und Ruhezeiten, Kunden, die nur bestimmte Fahrzeuge anfahren dürfen, oder Waren, die nicht zusammen geladen werden können. Die Forschung fasst diese ganze Klasse von Problemen unter dem Begriff Rich VRP zusammen. Als Faustregel gilt: Je mehr Bedingungen dazukommen, desto aufwendiger wird die Berechnung, denn jede zusätzliche Regel muss für jede Lösung, die das Verfahren ausprobiert, mitgeprüft werden.
Warum Standardsoftware oft nicht reicht
Im echten Betrieb kommen diese Erweiterungen nicht einzeln vor, sondern alle auf einmal. Ein Metallhändler hat Zeitfenster, eine gemischte Flotte, sperrige Ware, kurzfristige Aufträge und Stammdaten, in denen Maße auch mal fehlen. Die meisten wissenschaftlichen Arbeiten betrachten dagegen ein oder zwei Erweiterungen gleichzeitig. Und Software für Paketdienste ist auf Kartons ausgelegt, nicht auf Langgut.
Genau mit dieser Lücke beschäftige ich mich in meiner Promotion: mit einer Tourenplanung, die zu den Bedingungen des Metallhandels passt.
Malte Meistrell
Malte ist Stipendiat in der Graduate School of Logistics und promoviert in Kooperation mit tk accelis Materials GmbH (ehemals thyssenkrupp Schulte GmbH). In Dissertation und Transfer setzt er sich mit der Tourenplanung im Metallhandel auseinander.