28. 02. 2023
Verfasst von: Lars Schmidt-Thieme, Julia Rieck

Dynamische Routenoptimierung mit maschinellem Lernen

Lastwagen parken nebeneinander. — Staus, Baustellen, Auftragsänderungen – die Routenplanung großer Fahrzeugflotten ist schwierig. Von der Spedition Hahne aus Goslar erhält die Hildesheimer Forschungsgruppe reale Daten und praxisnahe Erfahrungen, um Planungsverfahren zu verbessern.

Wie können Logistik-Unternehmen ihre großen Fahrzeugflotten optimal einsetzen? Wie reagieren sie auf veränderte Bedingungen auf der Strecke – wenn etwa neue Kunden eingeplant oder Baustellen umschifft werden müssen? An diesen Forschungsfragen arbeitet die Stiftung Universität Hildesheim im Forschungsprojekt „L2O: Learning to Optimize“. Techniken des maschinellen Lernens sollen bisherige Optimierungsverfahren verbessern.

Fahrzeugflotten effizienter planen und einsetzen

Routenoptimierung ist so wichtig wie nie zuvor: Personen- und Güterströme unterliegen ständigem Wachstum und es werden immer größere Fahrzeugflotten verwendet, um den Bedarf zu bedienen. Gleichzeitig steigen sowohl die Kundenerwartungen als auch der Konkurrenzdruck. Die Routenplanung kann insbesondere in hochgradig stochastischen und dynamischen Umgebungen herausfordernd sein, da alle Entscheidungen schnell und präzise getroffen werden müssen. Optimierungsverfahren müssen auf Staus, Baustellen oder kurzfristige Streckensperrungen reagieren, müssen deren Auswirkungen auf den Plan für die gesamte Flotte korrekt einschätzen und anschließend möglichst optimale Anpassungen vornehmen. Zahlreiche Dienstleister, wie Spediteure, Taxianbieter oder mobile Pflegedienste, sehen sich tagtäglich mit diesen Herausforderungen konfrontiert.

Große Routing-Probleme schnell lösen

Bisher wurden für diese Probleme überwiegend Ansätze aus dem Operations Research (OR) verwendet. Hierbei lösen exakte oder heuristische Methoden das zugrundeliegende mathematische Optimierungsproblem. Je größer die Probleme und die (stochastische) Unsicherheit jedoch werden, desto schwieriger wird es, sehr gute Lösungen mit diesen klassischen Methoden zu finden. Aus diesem Grund untersucht ein Forschungsteam der Universität Hildesheim im Forschungsprojekt „Learning to Optimize – Dynamische, komplexe Routenoptimierung für Fahrzeugflotten“ verschiedene Möglichkeiten, bekannte OR-Verfahren durch Techniken des maschinellen Lernens zu erweitern, um große, realistische Routing-Probleme zu lösen.

Grafisches Netzwerk mit Symbolen für Lastwagen, Depot, Zielorte, Strecken, Staus und Baustellen — Wenn Lastwagen ihre Tour beginnen (links), können dynamische Ereignisse wie Staus oder Baustellen die Route behindern. Die dynamische, komplexe Routenoptimierung (rechts) verknüpft OR-Verfahren mit Techniken des maschinellen Lernens. Das beschleunigt und verbessert die Routenplanung.

Automatisch lernen, schneller reagieren

Maschinelles Lernen bietet den besonderen Vorteil, dass ein Verfahren sowohl aus realen Daten als auch aus simulierten sowie vergangenen Erfahrungen automatisch lernen und damit viel schneller auf unerwartete Veränderungen reagieren kann. Das vom Bundesforschungsministerium geförderte Projekt wird von den Hildesheimer Arbeitsgruppen für Operations Research und für Maschinelles Lernen durchgeführt. Um Zugang zu realen Daten und praxisnahen Einschränkungen zu erhalten, arbeiten sie mit der Spedition Hahne aus Goslar sowie dem Logistiksoftwaredienstleister Spedifix aus Langelsheim als Praxispartner zusammen. Das versetzt die Forschenden auch in die Lage, die implementierten Methoden in realen Umgebungen zu testen.

Kooperationspartner: