1. News
  2. Wissenschaft & Bildung
  3. Regional

Bonner Mathematiker gewinnt Algorithmus-Wettbewerb von Amazon

Bonner Mathematiker entwickelt Sieger-Algorithmus : Wettbewerbssieg: 100.000 Dollar für das Problem der letzten Meile

Für ihren Reiserouten-Algorithmus haben der Bonner Mathematikprofessor Stephan Held und zwei Kollegen im Wettbewerb der „Last Mile Challenge“ gesiegt. Ausgeschrieben hatten sie der Logistikriese Amazon und das Massachusetts Institute of Technology.

Maschinell optimierte Routen sind in der Logistik längst gang und gäbe. Im Straßenverkehr kommt es indessen regelmäßig zu Blockaden. Baustellen, Umleitungen oder parkende Fahrzeuge zwingen die Fahrer zu Abweichungen vom vorgegebenen Weg. Ihre Ortskenntnis entscheidet dann, wie reibungslos die Zustellung funktioniert. Theorie trifft auf Wirklichkeit.

Trotzdem lässt sich dieses Wissen für maschinelles Lernen nutzen, wie jetzt der Bonner Mathematik-Professor Stephan Held zeigen konnte. Zusammen mit zwei Kollegen aus Kanada und Dänemark gewann er den Wettbewerb „Last Mile Routing Research Challenge“, gemeinsam ausgerichtet von Amazon und dem MIT Center for Transportation and Logistics in Boston, Massachusetts. Mit seinen Mit-Preisträgern teilt Held sich jetzt ein Preisgeld von 100.000 US-Dollar. Der Bonner und seine Mitstreiter schlugen sich laut den Ergebnissen um 42 Prozent besser als das zweitplatzierte Team.

Algorithmen lernen aus gefahrenen Routen

Die Aufgabe der „letzten Meile“ ist eine Variante des „Problems des Handlungsreisenden“ – der Frage, wie sich eine vorgegebene Menge von Reisezielen möglichst schnell und/oder ressourcenschonend ansteuern lässt.

Zunächst sollten die Algorithmen hierzu 6000 bereits von Menschen gefahrene Routen analysieren und daraus lernen. Mit diesem Wissen mussten die Teilnehmenden neue Touren mit geheim gehaltenen Routen planen. Diese wurden nach ihrer Ähnlichkeit zu den tatsächlichen Routen bewertet.

Stephan Held (er wirkt an der Uni am Forschungsinstitut für Diskrete Mathematik und am Hausdorff Center for Mathematics) und seine Kollegen entwickelten dazu bekannte Such-Algorithmen weiter. So konnten sie in den gefahrenen Touren eine zweistufige hierarchische Cluster-Struktur erkennen.

Für den Mathematiker war die Aufgabe kein Neuland

Darüber hinaus extrahierten sie „Reihenfolgebeschränkungen“ zwischen den Clustern aus einer bekannten Tour mit einer ähnlichsten Cluster-Struktur. Solche Beschränkungen sagen zum Beispiel aus, dass Cluster A vor B und C angefahren werden soll.

Von dem Zwölf-Stunden-Limit, das zum Lernen aus den historischen Routen zur Verfügung stand, nutzten sie rund fünf Minuten für dieses Extrahieren. „Zur Berechnung der Touren für die neuen Instanzen haben wir das vorgegebene Zeitlimit von vier Stunden nahezu ausgenutzt, um das Ergebnis möglichst weit zu verbessern“, berichtet Held. „Im Nachhinein zeigte sich allerdings, dass auch hier sogar eine Rechenzeit von zehn Minuten ausgereicht hätte, um den ersten Platz zu erzielen.“

Seit Jahren mit Routenplanung befasst

Die Zukunft werde aber vermutlich noch bessere kombinatorische Algorithmen für das Wettbewerbsproblem bringen, eventuell in Kombination mit Machine-Learning-Algorithmen, erwartet Held, der auch Mitglied des Transdisziplinären Forschungsbereichs „Modelling“ der Uni ist.

Für den Mathematiker, der 2008 in Bonn promovierte und hier seit 2013 eine Professur besetzt, war die Aufgabenstellung kein Neuland. Seit Jahren ist er unter anderem an einem gemeinsamen Forschungsprojekt zur Routenplanung der Universität Bonn und einem Tochter­unternehmen der Deutschen Post DHL beteiligt. Die Greenplan GmbH soll der Konzernmutter wie auch anderen Kunden die Routenplanung optimieren, indem etwa Verkehrsvorhersagen, Zustellzeitfenster und Pausenzeiten für die Fahrer/innen einbezogen werden.