{"id":4018,"date":"2021-08-11T08:08:00","date_gmt":"2021-08-11T08:08:00","guid":{"rendered":"https:\/\/greenplan.limsup.de\/amazon-last-mile-routing-challenge\/"},"modified":"2022-11-18T11:15:39","modified_gmt":"2022-11-18T11:15:39","slug":"amazon-routing-challenge","status":"publish","type":"post","link":"https:\/\/greenplan.de\/de\/amazon-routing-challenge\/","title":{"rendered":"Amazon Last Mile Routing Challenge"},"content":{"rendered":"\n

Amazon veranstaltet Last Mile Routing Challenge<\/strong><\/h2>\n\n\n\n

Anfang 2021 startete Amazon zusammen mit dem Massachusetts Institute of Technology (MIT) Center for Transportation & Logistics die \u201eAmazon Last Mile Routing Research Challenge\u201c. Ziel des Wettbewerbs war die Planung einer optimierten Paketzustellung auf der letzten Meile.<\/p>\n\n\n\n

Trotz enormer Fortschritte bei der Tourenoptimierung in den vergangenen Jahren, besteht nach wie vor eine L\u00fccke zwischen der theoretischen Optimierung und der tats\u00e4chlichen 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\u00fcr die optimierte Zustellung auf der letzten Meile nutzen k\u00f6nnen.<\/p>\n\n\n\n

Bei der mathematischen Herangehensweise des Problems handelt es sich um eine neue Variante des bekannten Travelling Salesman Problems. Dabei wird die k\u00fcrzeste Tour durch eine Vielzahl von St\u00e4dten oder Paketadressen gesucht. Ob es effiziente Algorithmen f\u00fcr dieses Problem gibt oder nicht geben kann, h\u00e4ngt unmittelbar mit dem \u201eMilleniums-Problem P vs. NP\u201c zusammen.<\/p>\n\n\n\n

Stephan Held, Mitglied des Greenplan Forschungsteam, und sein Team pr\u00e4sentieren die effizientesten Ergebnisse<\/strong><\/h2>\n\n\n\n

Unter den 2.285 Teilnehmern des diesj\u00e4hrigen Wettbewerbs war auch Professor Dr. Stephan Held vom Hausdorff Center for Mathematics und Mitglied des Greenplan Entwicklerteams der Universit\u00e4t Bonn. Zusammen mit seinen Teamkollegen Keld Helsgaun (D\u00e4nemark) und William Cook (Kanada) versuchte er die Problemstellung durch eine Weiterentwicklung bekannter kombinatorischer lokaler Such-Algorithmen zu l\u00f6sen \u2013 mit Erfolg. Das Team um Stephan Held pr\u00e4sentierte um 42% bessere Ergebnisse als die Zweitplatzierten vom MIT. Diese au\u00dfergew\u00f6hnliche Leistung wurde mit einem Preisgeld von 100.000 Dollar belohnt.  <\/p>\n\n\n\n

Das Team erkannte in den gefahrenen Touren eine zweistufige hierarchische Cluster-Struktur, die zu einer neuen Variante des Traveling Salesperson Problems f\u00fchrt. Dar\u00fcber hinaus extrahierten sie sogenannte Reihenfolgebeschr\u00e4nkungen zwischen den Clustern aus einer bekannten Tour mit einer \u00e4hnlichen Cluster-Struktur. Solche Reihenfolgebeschr\u00e4nkungen 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\u00fcssen.<\/p>\n\n\n\n

Maschnielles Lernen nicht die pr\u00e4ferierte L\u00f6sung<\/strong><\/h2>\n\n\n\n

Interessanterweise zeigte sich, dass Maschinelles Lernen nicht den bevorzugten L\u00f6sungsansatz der Teilnehmer darstellte. Lediglich 35% aller teilnehmenden Teams nutzten Techniken des Maschinellen Lernens zur L\u00f6sung der Fragestellung. Laut Held spiele Maschinelles Lernen f\u00fcr kombinatorische Optimierungsprobleme wie das klassische TSP bislang noch keine gro\u00dfe Rolle, obwohl vielfach daran geforscht werde.<\/p>\n\n\n\n

Seinen eignen Ansatz kommentiert Held so: „Der Hype um das Machine-Learning f\u00fchrt dazu, dass man sich heutzutage fast schon rechtfertigen muss, auf diese Methoden in der diskreten Optimierung zu verzichten. F\u00fcr mich war es eine zentrale Motivation umgekehrt auf einem Machine-Learning-Wettbewerb, welcher auf einem kombinatorischen Optimierungsproblem basiert, die St\u00e4rke von Optimierungsalgorithmen zu demonstrieren.\u201c<\/p>\n\n\n\n

Der Mathematiker vermutet, dass kombinatorische Algorithmen (wie Greenplan) weiterhin die Zukunft f\u00fcr die Tourenplanung und -optimierung sein werden \u2013 m\u00f6glicherweise in Kombination mit maschinellen Lernalgorithmen.<\/p>\n\n\n\n

An dem Wettbewerb nahmen insgesamt 220 Teams aus 22 L\u00e4ndern teil. 45 Teams schafften es bis in die letzte Runde.<\/p>\n\n\n\n

Lesen Sie hier <\/a>die Pressemitteilung der Universit\u00e4t Bonn.<\/p>\n","protected":false},"excerpt":{"rendered":"

Amazon veranstaltet Last Mile Routing Challenge Anfang 2021 startete Amazon zusammen mit dem Massachusetts Institute of Technology (MIT) Center for Transportation & Logistics die \u201eAmazon Last Mile Routing Research Challenge\u201c. 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 … <\/p>\n

Read more „Amazon Last Mile Routing Challenge“<\/span><\/a><\/p>\n","protected":false},"author":9,"featured_media":3868,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[25],"tags":[],"class_list":["post-4018","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-greenplan-de"],"_links":{"self":[{"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/posts\/4018","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/comments?post=4018"}],"version-history":[{"count":2,"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/posts\/4018\/revisions"}],"predecessor-version":[{"id":4177,"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/posts\/4018\/revisions\/4177"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/media\/3868"}],"wp:attachment":[{"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/media?parent=4018"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/categories?post=4018"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/greenplan.de\/de\/wp-json\/wp\/v2\/tags?post=4018"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}