Martin-Luther-Universität Halle-Wittenberg

Kontakt

Prof. Dr. Matthias Müller-Hannemann

Telefon: +49-345-5524729
Telefax: ++49-345-5527039

Raum 4.19
Institut für Informatik
Martin-Luther-Universität
Halle-Wittenberg
Von-Seckendorffplatz 1
06120 Halle (Saale)

Email:
matthias.mueller-hannemann
AT informatik.uni-halle.de
oder
annabell.berger AT informatik.uni-halle.de

Weiteres

Login für Redakteure

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

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

Zum Seitenanfang