---

Dynamische Graphen-optimierungsprobleme

Projekt: Algorithm Engineering für dynamische Graphenoptimierungsprobleme in konkreten Anwendungen
(gefördert im SPP 1307 der DFG)

In vielen Anwendungen von Graphenalgorithmen unterliegen die Graphen bzw. Instanzen von Optimierungsproblemen wiederholten kleinen Änderungen. Ein Graph, der eine Sequenz von Änderungsoperationen erfährt, wird als dynamischer Graph bezeichnet. Ziel dynamischer Graphenalgorithmen ist es, die Lösung nach Durchführung einer oder mehreren Änderungsoperationen effizienter aktualisieren zu können, als dies durch vollständige Neuberechnung möglich wäre.

Im Mittelpunkt des Projekts stehen konkrete Anwendungen dynamischer  Optimierungsprobleme, insbesondere
(1) Online-Auskunft von Bahnverbindungen unter Berücksichtigung der aktuellen Verspätungslage infolge von Baustellen, technischen Defekten oder Unfällen.
(2) Routenplanung im Straßenverkehr unter Berücksichtigung von Staus bzw. aktueller Straßenauslastung, tageszeitabhängiger Geschwindigkeiten und mehreren Zielkriterien.

Für diese Aufgaben stehen bisher keine befriedigenden Lösungen zur Verfügung. Durch konsequentes Anwenden der Techniken des Algorithm Engineering sollen die bestehenden Lücken zur Anwendbarkeit in der Praxis geschlossen werden.

Beteiligte Wissenschaftler

• Prof. Dr. Matthias Müller-Hannemann (Projektleiter)
• Prof. Dr. Karsten Weihe    (TU Darmstadt)
• M.Sc. Annabell Berger (gefördert von DFG)
• Dr. Mathias Schnee    (TU Darmstadt)

Bisherige Ergebnisse

• Echtzeit-Fahrplanauskunft mit dynamischen Aktualisierungen
  Wir haben einen realistischen Prototyp für eine Echtzeitauskunft im Bahnverkehr entwickelt, der fortlaufende Aktualisierungen aufgrund von Verspätungen berücksichtigt (Müller-Hannemann und Schnee 2009).
• Multi-kriterielle Fahrplanauskunft in zeitabhängigen Netzwerken
  Mehrere zunächst vielversprechende Beschleunigungstechniken für multikriterielle, zeitabhängige Kürzeste-Wege-Suchen in einem statischen Szenario wurden analysiert. Wir konnten erklären, warum man von ihnen nur geringe Beschleunigungsfaktoren für die Fahrplanauskunft von Zügen erwarten kann (im Vergleich zu Beobachtungen bei Straßennetzen) (ATMOS 2009).
• Beschleunigungstechniken für multi-kriterielle kürzeste Wege mit dynamischen Aktualisierungen
  Für dynamische Aktualisierungen haben wir zwei neue Beschleunigungstechniken entwickelt. Die eine basiert auf einer spezifischen Substruktureigenschaft zeitabhängiger Wege, die andere auf sogenannten "k-flags", einer Erweiterung von "arc flags" (SEA 2010).
• Robuste Fahrplanauskunft
  Verschiedene Robustheitsbegriffe zur Fahrplanauskunft im öffentlichen Personenverkehr wurden analysiert. Das Konzept starker Robustheit erwies sich als NP-schwer, aber konservative Approximationen können in Polynomialzeit berechnet werden. Basierend auf dem Hochgeschwindigkeitsnetz (ICE und IC-Verkehr) der Deutschen Bahn und dem Fahrplan von 2011 haben wir eine Kosten-Nutzen-Analyse für den Zielkonflikt zwischen erhöhter garantierter Robustheit und der dadurch verursachten Fahrzeitverlängerung durchgeführt (ATMOS 2011).
• Kundenfreundliche Anschlussdisposition
  Wir haben ein Modell einer kundenfreundlichen Zugdisposition entwickelt. Dies führt auf dynamische Passagierfluss- und Optimierungsprobleme, für die wir einen effizienten Prototpyen entwickelt haben (ESA 2011).
• Stochastische Progonose von Verspätungsfortpflanzungen
  Ein stochastisches Modell der Verspätungsfortpflanzung zur Vorhersage von Ankunfts- und Abfahrtsereignissen im öffentlichen Personenverkehr in einem Online-Szenario wurde implementiert und getestet (ATMOS 2011).
• Zeitabhängige Zentralität in komplexen Netzwerken
  Für die Netzwerkanalyse haben wir ein neues, zeitabhängiges Zentralitätsmaß eingeführt. Eine Fallstudie mit dem weltweiten Flugverkehrsnetz lieferte wertvolle Einsichten in die Rangfolge und Wettbewerbsposition von Flughäfen (WALCOM 2011).
• Zufällige gerichtete Graphen mit vorgegebene Gradsequenz
  Gleichverteilt zufälliges Erzeugen von gerichteten Graphen mit vorgegebener Gradsequenz ist ein wichtiges Hilfsmittel in der Analyse komplexer Netzwerke. Wir haben gezeig, dass ein populärer, Markovketten-basierter Kantenaustauschalgorithmus manchmal falsche Ergebnisse liefert, konnten jedoch charakterisieren unter welchen Bedingungen er korrekt arbeitet und zeigen, wie das Problem im Allgemeinen gelöst werden kann (WG 2010).

Publikationen

• Annabell Berger, Christian Blaar, Andreas Gebhardt, Matthias Müller-Hannemann and Mathias Schnee
  Passenger Flow-Oriented Train Disposition, Proceedings of ESA 2011, Saarbrücken, LNCS 6942, pp. 227-238, Springer, Heidelberg. Full version: Technical Report 2011/2, Institut für Informatik, MLU Halle-Wittenberg
• Annabell Berger, Andreas Gebhardt, Matthias Müller-Hannemann and Martin Ostrowski:
  Stochastic Delay Prediction in Large Train Networks, ATMOS 2011, OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 100-111, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
• Marc Goerigk, Martin Knoth, Matthias Müller-Hannemann, Anita Schöbel and Marie Schmidt:
  The Price of Robustness in Timetable Information,
  ATMOS 2011, OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 76-87, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
• Annabell Berger and Matthias Müller-Hannemann
  Dag Realizations of Directed Degree Sequences
  Proceedings of FCT 2011, Oslo, Norway, LNCS 6914, pp. 264-275, Springer, Heidelberg. Full version: Technical Report 2011/5, Institut für Informatik, MLU Halle-Wittenberg,
• Annabell Berger, Matthias Müller-Hannemann, Steffen Rechner, and Alexander Zock:
  Efficient Computation of Time-Dependent Centralities in Air Transportation Networks Proceedings of WALCOM 2011, LNCS 6552, pp. 77-88, Springer.
• Torsten Gunkel, Matthias Müller-Hannemann and Mathias Schnee:
  Improved Search for Night Train Connections, Networks 57(1), pp. 19-27 (2011).
• Annabell Berger, Martin Grimmer, and Matthias Müller-Hannemann:
  Fully dynamic speed-up techniques for multi-criteria shortest paths searches in time-dependent networks, Proceedings of SEA 2010, LNCS 6049, pages 35-46, Springer, 2010.
• Annabell Berger and Matthias Müller-Hannemann:
  Uniform Sampling of Undirected and Directed Graphs with a Fixed Degree Sequence, extended abstract in Proceedings of WG 2010, LNCS 6410, pp. 220-231, Springer, 2010.
• Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller-Hannemann:
  Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected,
  Proceedings of ATMOS 2009.
• Matthias Müller-Hannemann and Mathias Schnee:
  Efficient Timetable Information in the Presence of Delays, in Robust and Online Large Scale Optimization, LNCS 5868, pp. 249–272, Springer, 2009.
• Lennart Frede, Matthias Müller-Hannemann, and Mathias Schnee:
  Efficient On-Trip Timetable Information in the Presence of Delays, Proceedings of ATMOS 2008.
• Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee
  Multi-Criteria Shortest Paths in Time-Dependent Train Networks, in C.C. McGeoch (ed.): WEA 2008, LNCS 5038, pp. 347-361, 2008.

Zum Seitenanfang