Amazon veranstaltet Last Mile Routing Challenge
Anfang 2021 startete Amazon zusammen mit dem Massachusetts Institute of Technology (MIT) Center for Transportation & Logistics die „Amazon Last Mile Routing Research Challenge“. Ziel des Wettbewerbs war die Planung einer optimierten Paketzustellung auf der letzten Meile.
Trotz enormer Fortschritte bei der Tourenoptimierung in den vergangenen Jahren, besteht nach wie vor eine Lücke zwischen der theoretischen Optimierung und der tatsächlichen Umsetzung von Touren. Insbesondere bei der praktischen Umsetzung bestimmt vor allem noch das Fahrerwissen den Ablauf einer Tour. Im Rahmen des von Amazon veranstalteten Wettbewerbs sollte daher untersucht werden, wie Algorithmen das Wissen erfahrener Zusteller erlenen und für die optimierte Zustellung auf der letzten Meile nutzen können.
Bei der mathematischen Herangehensweise des Problems handelt es sich um eine neue Variante des bekannten Travelling Salesman Problems. Dabei wird die kürzeste Tour durch eine Vielzahl von Städten oder Paketadressen gesucht. Ob es effiziente Algorithmen für dieses Problem gibt oder nicht geben kann, hängt unmittelbar mit dem „Milleniums-Problem P vs. NP“ zusammen.
Stephan Held, Mitglied des Greenplan Forschungsteam, und sein Team präsentieren die effizientesten Ergebnisse
Unter den 2.285 Teilnehmern des diesjährigen Wettbewerbs war auch Professor Dr. Stephan Held vom Hausdorff Center for Mathematics und Mitglied des Greenplan Entwicklerteams der Universität Bonn. Zusammen mit seinen Teamkollegen Keld Helsgaun (Dänemark) und William Cook (Kanada) versuchte er die Problemstellung durch eine Weiterentwicklung bekannter kombinatorischer lokaler Such-Algorithmen zu lösen – mit Erfolg. Das Team um Stephan Held präsentierte um 42% bessere Ergebnisse als die Zweitplatzierten vom MIT. Diese außergewöhnliche Leistung wurde mit einem Preisgeld von 100.000 Dollar belohnt.
Das Team erkannte in den gefahrenen Touren eine zweistufige hierarchische Cluster-Struktur, die zu einer neuen Variante des Traveling Salesperson Problems führt. Darüber hinaus extrahierten sie sogenannte Reihenfolgebeschränkungen zwischen den Clustern aus einer bekannten Tour mit einer ähnlichen Cluster-Struktur. Solche Reihenfolgebeschränkungen sagen zum Beispiel aus, dass Cluster A vor B und C angefahren werden soll. Daraus ergaben sich neue sogenannte disjunktive Reihenfolgerestriktionen. Diese geben vor, dass die Cluster entweder in der Reihenfolge A, B, C oder in der Reihenfolge B, C, A besucht werden müssen.
Maschnielles Lernen nicht die präferierte Lösung
Interessanterweise zeigte sich, dass Maschinelles Lernen nicht den bevorzugten Lösungsansatz der Teilnehmer darstellte. Lediglich 35% aller teilnehmenden Teams nutzten Techniken des Maschinellen Lernens zur Lösung der Fragestellung. Laut Held spiele Maschinelles Lernen für kombinatorische Optimierungsprobleme wie das klassische TSP bislang noch keine große Rolle, obwohl vielfach daran geforscht werde.
Seinen eignen Ansatz kommentiert Held so: „Der Hype um das Machine-Learning führt dazu, dass man sich heutzutage fast schon rechtfertigen muss, auf diese Methoden in der diskreten Optimierung zu verzichten. Für mich war es eine zentrale Motivation umgekehrt auf einem Machine-Learning-Wettbewerb, welcher auf einem kombinatorischen Optimierungsproblem basiert, die Stärke von Optimierungsalgorithmen zu demonstrieren.“
Der Mathematiker vermutet, dass kombinatorische Algorithmen (wie Greenplan) weiterhin die Zukunft für die Tourenplanung und -optimierung sein werden – möglicherweise in Kombination mit maschinellen Lernalgorithmen.
An dem Wettbewerb nahmen insgesamt 220 Teams aus 22 Ländern teil. 45 Teams schafften es bis in die letzte Runde.
Lesen Sie hier die Pressemitteilung der Universität Bonn.