Algorithm Engineering für dynamische Graphenoptimierungsprobleme in konkreten Anwendungen

点击翻译按钮获取中文摘要

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.