Algorithm Engineering für dynamische Graphenoptimierungsprobleme in konkreten Anwendungen

• Applicant: Professor Dr. Matthias Müller-Hannemann
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering