“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.