« Projekte
Algorithm Engineering für dynamische Graphenoptimierungsprobleme in realen Anwendungen
Finanzierung:
Deutsche Forschungsgemeinschaft (DFG) ;
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.

Schlagworte

Algorithm Engineering, Bahnauskunft, Routenplanung, Verspätungsmanagement, dynamische Graphen
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 ...