« Forschungslandschaft: Projekte

Das Projekt beschäftigt sich mit dynamischen Optimierungsproblemen in Graphen. Im Mittelpunkt des Projektes stehen

(1) Routenplanung im Straßenverkehr unter Berücksichtigung von Staus bzw. aktueller Straßenauslastung, tageszeitabhängiger Geschwindigkeiten und mehreren Zielkriterien.

(2) Online-Auskunft von Bahnverbindungen unter Berücksichtigung der aktuellen Verspätungslage infolge von Baustellen, technischen Defekten oder Unfällen. Dies erfordert eine möglichst genaue Prognose der Verspätungsentwicklung im Netzwerk. Darauf aufbauend streben wir eine Optimierung der Dispositionsentscheidungen an (delay management).

Für diese Aufgaben stehen bisher keine befriedigenden Lösungen oder bestenfalls heuristische Ansätze ohne Qualitätsgarantien zur Verfügung. Hauptziel des Projektes ist es, durch konsequentes Anwenden der Techniken des Algorithm Engineering bestehende Lücken zur Anwendbarkeit in der Praxis zu schließen. Dazu benötigt man zunächst realistische Anwendungsmodelle, die die Anforderungen aus der Praxis adäquat abbilden. Im Entwurf müssen geeignete speicherplatzeffiziente Datenstrukturen entwickelt werden, während in der Analyse realistische Sequenzen dynamischer Änderungen untersucht werden. Basierend auf sorgfältigen und flexiblen Implementationen der entwickelten Algorithmen soll in systematischen Experimenten untersucht werden, welche Eigenschaften der Netzwerke bzw. Updatesequenzen effiziente Lösungen ermöglichen.