Algorithm Engineering für dynamische Graphenoptimierungsprobleme in konkreten Anwendungen

• Antragsteller: Professor Dr. Matthias Müller-Hannemann
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 47775921

Konkrete Anwendungen dynamischer Optimierungsprobleme sollen im Mittelpunkt desProjekts stehen: (1) Online-Auskunft von Bahnverbindungen unter Berücksichtigung deraktuellen Verspätungslage infolge von Baustellen, technischen Defekten oder Unfällen; (2)Optimierte Anschlussdisposition im Bahnverkehr (delay management); (3) Routenplanung fürintermodalen Verkehr (Bahnverkehr, Flugverkehr, Straßenverkehr) unter Berücksichtigungunvorhersehbarer Störungen (Staus, Straßensperrungen, Streiks, technische Defekte).Für diese Aufgaben stehen bisher keine befriedigenden Lösungen zur Verfügung. Hauptziel desProjektes ist es, durch konsequentes Ausnutzen der Techniken des Algorithm Engineeringbestehende Lücken zur Anwendbarkeit in der Praxis zu schließen. Dazu benötigt man zunächstrealistische Anwendungsmodelle, die die Anforderungen aus der Praxis adäquat abbilden. ImEntwurf müssen geeignete speicherplatzeffiziente Datenstrukturen entwickelt werden, währendin der Analyse realistische Sequenzen dynamischer Änderungen untersucht werden. Basierendauf sorgfältigen und flexiblen Implementationen der entwickelten Algorithmen soll insystematischen Experimenten untersucht werden, welche Eigenschaften der Netzwerke bzw.Updatesequenzen effiziente Lösungen ermöglichen.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering