« Projekte
Algorithm Engineering für dynamische Graphenoptimierungsprobleme in konkreten Anwendungen (Förderphase III)
Finanzierung:
Deutsche Forschungsgemeinschaft (DFG) ;
Viele Optimierungsprobleme auf Graphen aus der realen Welt unterliegen häufigen, kleinen Änderungen. Mit dynamischen Graphenalgorithmen möchte man optimale Lösungen nach Änderungen schneller aktualisieren, als es durch Neuberechnen möglich wäre. Im Mittelpunkt dieses Projekts stehen als konkrete Anwendungen von dynamischen Graphenalgorithmen

    • stochastische Vorhersagen in dynamischen Transportnetzwerken für die Robustheitsanalyse und die Fahrplanauskunft;
    • eine passagierfreundliche Anschlussdisposition im Bahnverkehr;
    • die Netzwerkanalyse zeitabhängiger Netze mit Anwendungen in Flugnetzwerken.
    Unter Verwendung des breiten Spektrums der Techniken des Algorithm Engineering sollen die bestehenden Lücken zu praktisch anwendbaren Lösungen geschlossen werden.  Ausgehend von realistischen Anwendungsmodellen, die die Anforderungen aus der Praxis adäquat abbilden, müssen im Entwurf geeignete speicherplatzeffiziente Datenstrukturen entwickelt werden, während in der Analyse realistische Sequenzen dynamischer Änderungen untersucht werden. Basierend auf sorgfältigen und flexiblen Implementationen soll in systematischen Experimenten untersucht werden, welche Eigenschaften der Netzwerke bzw. Updatesequenzen effiziente Lösungen ermöglichen.

Schlagworte

Anschlussdisposition, Fahrplanauskunft, Graphen, Netzwerke, Optimierung
Kontakt
Prof. Dr. Matthias Müller-Hannemann

Prof. Dr. Matthias Müller-Hannemann

Martin-Luther-Universität Halle-Wittenberg

Naturwissenschaftliche Fakultät III

Institut für Informatik

Von-Seckendorff-Platz 1

06120

Halle (Saale)

Tel.+49 345 5524729

Fax:+49 345 5527039

matthias.mueller-hannemann(at)informatik.uni-halle.de

weitere Projekte

Die Daten werden geladen ...