20. April 2021

Grüne Tourenplanung mit Diskreter Mathematik Grüne Tourenplanung mit Diskreter Mathematik

Universität Bonn und Deutsche Post DHL Group verstetigen ihre Kooperation.

Wie lassen sich Pakete und Fracht ressourcensparender und umweltfreundlicher ausliefern? Seit 2017 kooperieren die Universität Bonn und die Deutsche Post DHL Group auf dem Gebiet der Tourenplanung. Das Forschungsinstitut für Diskrete Mathematik hat einen Algorithmus für eine optimierte Planung entwickelt, der sich bereits in der Praxis bewährt hat. Die Deutsche Post DHL hat daraufhin die Tochterfirma Greenplan gegründet, die den Algorithmus breit zum Einsatz bringen will und für die Tourenplanung nutzt. Die Kooperation wird nun unbefristet fortgesetzt.

Das Tourenplanungs-Team am Forschungsinstitut für Diskrete Mathematik
Das Tourenplanungs-Team am Forschungsinstitut für Diskrete Mathematik - Im Uhrzeigersinn, beginnend bei 12 Uhr: Professor Jens Vygen, Antonia Ellerbrock, Felix Rosebrock, Dr. Dirk Müller, Professor Stephan Held, Jannis Blauth (Doktorand), Silas Rathke, Vanessa Ryborz und in der Mitte Luise Puhlmann. © Jens Vygen/HCM/Uni Bonn
Alle Bilder in Originalgröße herunterladen Der Abdruck im Zusammenhang mit der Nachricht ist kostenlos, dabei ist der angegebene Bildautor zu nennen.

“Die Zusammenarbeit mit den Logistik-Experten bei Greenplan war von Anfang an äußerst fruchtbar”, sagt Prof. Dr. Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn. „So entstand ein Algorithmus, der sehr flexibel einsetzbar ist und dennoch nach kurzer Rechenzeit exzellente Ergebnisse liefert.“ Ein Novum ist, dass der Algorithmus mit Fahrtzeiten plant, die nicht nur von der Strecke abhängen, sondern auch vom Verkehrsaufkommen zur jeweiligen Tageszeit. Damit können die Touren zum Beispiel Staus ausweichen und ermöglichen erhebliche Einsparungen an Kosten und Emissionen. Greenplan erhielt dafür im vergangenen Jahr den PostEurop Innovation Award.

Dr. Dirk Müller, der die Softwareentwicklung im Forschungsinstitut für Diskrete Mathematik leitet, erläutert die Herausforderungen: “Schon die Berechnung der besten Route von A nach B ist nicht mehr ganz einfach, wenn die Fahrtzeiten und Kosten von der Verkehrssituation abhängen.” Die Frage, wie stark sich die Kosten einer Tour erhöhen, wenn ein neuer Auftrag an der optimalen Stelle eingebaut wird, sei erheblich schwieriger und müsse vom Programm millionenfach beantwortet werden. “Und das bei einer Gesamtrechenzeit von nur einigen Minuten.”

Dr. Clemens Beckmann, CEO von Greenplan, hat selbst Mathematik studiert und ist begeistert von der engen Zusammenarbeit mit der Universität: “Die hohe Professionalität in der Partnerschaft sowie die räumliche Nähe waren die Basis für eine extrem temporeiche Entwicklung, bei der sich logistische und wissenschaftliche Expertise optimal ergänzen.” So könne heute den Kunden aus Logistik, Außendienst-Planung etwa für Monteure und Techniker sowie Online-Handel ein Tourenplanungs-Tool an die Hand geben werden, das sowohl effizient als auch nachhaltig ist und sich schnell und flexibel für eine Vielzahl von Anwendungen einsetzen lässt. “Mit dem neuen Vertrag haben wir unsere Kooperation weiter gefestigt und freuen uns auf die weitere Zusammenarbeit”, sagt Dr. Beckmann.

Mit der Zahl der Städte steigt die Zahl der Routen extrem an

Die Wissenschaftler aus der Diskreten Mathematik der Universität Bonn um Prof. Jens Vygen sind Experten für Kombinatorische Optimierung. Sie haben in den letzten Jahren insbesondere für das berühmte Rundreiseproblem (englisch Traveling Salesman Problem) immer bessere Algorithmen entwickelt. Dabei geht es darum, eine kürzeste Rundreise durch verschiedene Städte zu finden. Bei 15 Städten gibt es bereits mehr als 87 Milliarden verschiedene Rundreisen, aus denen die kürzeste auszuwählen ist, und schon bei 20 Städten kann auch ein Computer nicht mehr alle Möglichkeiten durchprobieren.

Auszeichnung für Forschungsteam

Nun gelang den Forschenden sogar eine Verbesserung der Approximationsgarantie für das allgemeinere Tourenplanungsproblem (englisch Capacitated Vehicle Routing), die erste überhaupt seit mehr als 30 Jahren. Dafür erhalten die Autoren Jannis Blauth, Vera Traub und Jens Vygen im Mai den Best Paper Award auf der IPCO 2021, der weltweit führenden Konferenz für Ganzzahlige und Kombinatorische Optimierung.

Prof. Dr. Jens Vygen ist Fachgruppenvorsitzender der Mathematik, Vorstandsmitglied im Exzellenzcluster Hausdorff Center for Mathematics (HCM) und im Transdisziplinären Forschungsbereich Mathematik, Modellierung und Simulation komplexer Systeme an der Universität Bonn. Das Hausdorff Center for Mathematics wird von sechs Einheiten getragen, sein Forschungsspektrum reicht von reiner und angewandter Mathematik über mathematisch orientierte Fragestellungen der Ökonomie bis hin zu interdisziplinärer Forschung.

Im Transdisziplinären Forschungsbereich (TRA) „Mathematik, Modellierung und Simulation komplexer Systeme“ der Universität Bonn schaffen Forschende verschiedener Fachbereiche Modelle, die komplexe Systeme nicht nur beschreiben, sondern auch analysieren können. Dazu nutzen sie eine Kombination aus klassischen Beobachtungsmethoden, rechnergestützten Simulationen und kreativem Geist.

Wird geladen