Verteilte Verbindungssuche im öffentlichen Personenverkehr: Graphentheoretische Modelle und Algorithmen

Appeared in Patrick Horster (ed.) Angewandte Mathematik - insbesondere Informatik, Beispiele erfolgreicher Wege zwischen Mathematik und Informatik, Vieweg Verlag, 1999, pages 192-220

traffic information systems, shortest paths with side constraints, decomposition

Inzwischen verfügen viele Verkehrsunternehmen über lokale, computerbasierte Auskunftsysteme, bei denen Informationen über Verbindungen im jeweiligen System abrufbar sind. Derzeit entstehen Kopplungen solcher Systeme zu übergreifenden Auskunftsystemen, die die unterschiedlichen Teilsysteme und Datenbestände in einer verteilten Verbindungssuche geeignet kombinieren.

Diese Arbeit behandelt die verteilte Verbindungssuche aus graphentheoretischer Sicht. Im ersten Teil wird untersucht, wie weit sich unterschiedliche Abfragen auf die Berechnung kürzester Wege in einem geeignet definierten Graphen zurückführen lassen. Die Rückführung auf ein Graphenmodell eröffnet zum einen den Zugang zu Standardalgorithmen für eine Fülle ähnlich gelagerter, auch mehrkriterieller Kürzeste-Wege Berechnungen, und bietet aus struktureller Sicht den geeigneten Rahmen für die verteilte Verbindungsabfrage, die dann eng mit Dekompositionsmöglichkeiten des Graphen zusammenhängt.

Im zweiten Teil wird dann untersucht, welche Anfragen sich in einem verteilten System berechnen lassen und wie groß der dafür benötigte Aufwand ist. Insbesondere wird der Frage nachgegangen, welche Daten von den Teilsystemen bereit gestellt werden müssen, ob sich Pre-Processing dieser Daten lohnt und über welche Techniken ein Master-Algorithmus verfügen muß, der mit den Teilsystemen kommuniziert. Dabei wird insbesondere auf (approximative) Methoden für mehrkriterielle Zielfunktionen eingegangen.

Es zeigt sich, daß sich nahezu alle Standardabfragekriterien wie Reisezeit, Anzahl der Umstiege, Wahl des Verkehrsmittels sowie Kombinationen hiervon bei einer verteilten Abfrage berücksichtigen lassen, wobei der Rechenaufwand vom Grad der Vernetzung der Teilsysteme abhängt. Auch mehrkriterielle Abfragen sind möglich.

Download as [PDF] [ps.gz]