Greenplan hat mit Prof. Dr. Jens Vygen vom Forschungsinstitut für Diskrete Mathematik in Bonn über die Zusammenarbeit mit einem jungen Tech-Unternehmen gesprochen. Das Interview bietet spannende Einblicke in die effiziente Planung von Touren mithilfe diskreter Mathematik.
Herr Professor Vygen, Sie sind Professor für Mathematik an der Universität Bonn, tätig am Forschungsinstitut für Diskrete Mathematik sowie am Hausdorff-Zentrum in Bonn. Ihr Arbeitsgebiet ist die kombinatorische Optimierung. Zusammen mit Professor Korte leiten Sie die seit über 30 Jahren bestehende Kooperation „Kombinatorische Optimierung im Chip Design“ mit IBM. Seit 2016 besteht nun auch die wissenschaftliche Kooperation mit Deutsche Post DHL zur „Kombinatorischen Optimierung in Logistikdienstleistungen“.
Was hat Sie an dieser besonderen Aufgabenstellung im Logistik-Bereich gereizt?
Die hier auftretenden Kernprobleme, angefangen beim berühmten Traveling Salesman Problem (TSP, Rundreiseproblem), sind klassische kombinatorische Optimierungsprobleme mit denen ich mich schon vorher aus theoretischer Sicht beschäftigt habe und bei denen es immer noch viel zu entdecken gibt. Noch spannender wird es aber, wenn zusätzliche Anforderungen aus der Praxis hinzukommen für die mathematische Modelle und Algorithmen erst noch entwickelt werden müssen. Mich freut immer, wenn wir durch innovative Mathematik effizientere und ressourcensparende Lösungen in der Praxis ermöglichen. In Kooperation mit Greenplan ist der Weg von der mathematischen Idee bis zum Einsatz in der Praxis sehr kurz.
Was ist Diskrete Mathematik, und wie profitiert der Tourenplanungsalgorithmus von der Expertise Ihres Instituts in diesem Bereich?
Die Diskrete Mathematik analysiert Systeme in denen es nur endlich viele Wahlmöglichkeiten gibt, die aber so zahlreich sind, dass man sie nicht einfach durchprobieren kann. Ein gutes Beispiel ist das TSP. Wenn Sie von einem Depot aus drei Orte A, B und C anfahren müssen, können Sie alle möglichen Reihenfolgen ausprobieren: ABC, ACB, BAC, BCA, CAB, CBA. Bei 30 statt 3 Orten gibt es aber schon so viele Möglichkeiten, dass das selbst mit allen Computern der Welt zusammen Jahre an Rechenzeit bräuchte. Mit Diskreter Mathematik kann man die optimale Reihenfolge der 30 Orte aber schnell finden. Wir nennen das Kombinatorische Optimierung und in diesem Bereich hat unser Institut eine Spitzenstellung. Gleichzeitig haben wir jahrzehntelange Erfahrung mit industriellen Anwendungen und schreiben Software, die höchsten Anforderungen genügt.
Was sind Besonderheiten des von Ihnen im Kooperation mit DHL/Greenplan entwickelten Algorithmus?
Wir haben unseren Algorithmus so konzipiert, dass er flexibel ist und garantiert in kurzer Rechenzeit eine Lösung findet, die alle Nebenbedingungen einhält. Bei komplexen oder sehr großen Problemen reichen einige Minuten Rechenzeit nicht aus, um das Optimum zu berechnen; wir kommen ihm aber sehr nahe. Dabei arbeiten wir mit einem sorgfältig konzipierten allgemeinen Modell auf das man sehr unterschiedliche Anwendungsszenarien abbilden kann. Eine Besonderheit ist auch, dass wir durchweg mit realistischen Fahrtzeiten arbeiten, die nicht nur von Fahrzeugtyp und Weg sondern auch von der Tageszeit abhängen. Das macht einige Algorithmen komplizierter, aber nicht unbedingt viel langsamer und es zahlt sich in viel realistischeren und robusteren Lösungen aus, vor allem wenn Zeitfenster eingehalten werden müssen.
Wie sehen Sie die zukünftige Entwicklung in diesem Bereich?
Wir haben ständig neue Ideen und entwickeln den Algorithmus laufend weiter. Dabei geht es einerseits darum ihn noch besser oder schneller zu machen, andererseits auf neue Anforderungen aus der Praxis zu reagieren. Beispielsweise konnten wir gerade eine bessere Approximationsgüte beweisen und wollen nun sehen, was das in der Praxis bringt. Ein anderes Thema sind die Planung mit unvollständigen Daten und die Anpassung einer Tourenplanung an sich ergebende Änderungen. Es gibt noch viele weitere Ideen; es wird also sicher nicht langweilig.
Was sichert den Erfolg der Kooperation?
Wir kooperieren wirklich ausgezeichnet und sehr eng miteinander, kommunizieren nahezu täglich. Da wir alle in Bonn sind, können wir uns auch sehr häufig persönlich treffen. Wir haben sehr kurze Wege von der mathematischen Idee bis zum Einsatz in der Praxis oder von der neuen Praxisanforderung bis zur Implementierung. Ein wichtiger Faktor ist auch, dass wir als Teil des Exzellenzclusters „Hausdorff Center for Mathematics“ regelmäßig herausragende Studierende frühzeitig für unser Team gewinnen. Schon jetzt arbeitet einer unserer ehemaligen Doktoranden für Greenplan; weitere werden sicherlich folgen.
Vielen Dank für Ihre Zeit!