100.000 Dollar für Lösung eines Routen-Problems

Stephan Held gewinnt mit zwei Kollegen „Amazon Last Mile Routing Research Challenge“

 

Stephan Held vom Forschungsinstitut für Diskrete Mathematik

Bonn, 05.08.2021. Wie kann die Paketzustellung bei einer Masse von Routen und Paketen optimiert werden? Genauer gesagt: Wie können Algorithmen das Wissen und Verhalten von erfahrenen Zustellern lernen und nutzen? Für die Lösung dieses Problems ist der Stephan Held gemeinsam mit zwei Teampartnern aus Kanada und Dänemark als Gewinner eines weltweiten Wettbewerbs hervorgegangen – der „Amazon Last Mile Routing Research Challenge“. Veranstalter des Wettbewerbs sind das Unternehmen Amazon und das MIT Center for Transportation & Logistics in Boston. Das Preisgeld von 100.000 Dollar für das Gewinnerteam hatte in diesem Jahr 2.285 Teilnehmende aus der ganzen Welt angelockt.

Die Aufgabenstellung des Wettbewerbs war es, das Wissen und Verhalten von erfahrenen Zusteller*innen mit Verfahren des Maschinellen Lernens zu erfassen und zu nutzen. Hintergrund: Zusteller*innen reichern häufig die automatisch generierten Routen mit ihrem Wissen über Staus, Baustellen oder Kundenerreichbarkeiten an.

Bei der mathematischen Herangehensweise des Problems handelt es sich um eine neue Variante des bekannten Traveling Salesperson 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.

Im ersten Teil des Wettbewerbs sollten die Algorithmen von rund 6.000 bereits von Menschen gefahrenen Routen lernen. Danach mussten die Teilnehmenden neue Touren mit geheim gehaltenen Routen planen. Diese wurden nach ihrer Ähnlichkeit zu den tatsächlich gefahrenen Routen bewertet.

Das Team von Stephan Held vom Bonner Forschungsinstitut für Diskrete Mathematik, William Cook (University of Waterloo, Kanada) und Keld Helsgaun (Universität Roskilde, Dänemark) ging das Problem durch eine Weiterentwicklung bekannter kombinatorischer lokaler Such-Algorithmen an. So konnten die Wissenschaftler in den gefahrenen Touren eine zweistufige hierarchische Cluster-Struktur erkennen, die zu einer neuen Variante des Traveling Salesperson Problems führte. Darüber hinaus extrahierten sie sogenannte Reihenfolgebeschränkungen zwischen den Clustern aus einer bekannten Tour mit einer ähnlichsten 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.

Großer Abstand zu Platz zwei

Die Forscher gewannen den Wettbewerb mit einem um 42 Prozent besseren Ergebnis als das zweitplatzierte Team vom Massachusetts Institute of Technology (MIT). Von dem zwölfstündigen Zeitlimit, das zum Lernen aus den historischen Routen zur Verfügung stand, nutzten sie rund fünf Minuten zum Extrahieren der Reihenfolgebeschränkungen. „Zur Berechnung der Touren für die neuen Instanzen haben wir das hierfür vorgegebene Zeitlimit von vier Stunden nahezu ausgenutzt, um das Ergebnis möglichst weit zu verbessern“, erzählt Stephan Held. „Im Nachhinein zeigte sich allerdings, dass auch hier sogar eine Rechenzeit von zehn Minuten ausreichend gewesen wäre, um den ersten Platz zu erzielen.“

Es stellte sich heraus, dass nur eine Minderheit von 35 Prozent der Teams Techniken des Maschinellen Lernens nutzten. „In der Tat spielen diese für kombinatorische Optimierungsprobleme wie das klassische TSP bislang keine große Rolle, obwohl vielfach daran geforscht wird. Die Zukunft wird vermutlich noch bessere kombinatorische Algorithmen für das Wettbewerbsproblem bringen, eventuell in Kombination mit Machine-Learning-Algorithmen“, sagt Stephan Held, der auch Mitglied des Transdisziplinären Forschungsbereichs „Modelling“ der Universität Bonn ist.

Um die neue Art von Forschung anzutreiben, ist der Gewinnercode mittlerweile im Internet frei verfügbar: https://github.com/heldstephan/jpt-amz. Ein erster technischer Report wird in Kürze in einer Serie des MIT erscheinen.

Stephan Held ist auch an einem gemeinsamen Forschungsprojekt zur Routenplanung zwischen der Universität Bonn und Greenplan, einem Tochterunternehmen der Deutschen Post DHL, beteiligt. In diesem Projekt geht es um eine bessere Routenplanung unter Berücksichtigung von Verkehrsvorhersagen, Zustellzeitfenstern und Pausenzeiten für die Fahrer*innen. Kürzlich erhielt dieser Kooperationsvertrag eine Verlängerung auf unbegrenzte Zeit.

Zum Wettbewerb: https://routingchallenge.mit.edu/

Pressemitteilung von Amazon