Diploma Thesis DIP-1531

BibliographyLener, Claus: Wegsuche zur Verkehrsumlegung in ÖV-Netzen.
University of Stuttgart, Faculty of Computer Science, Diploma Thesis No. 1531 (1997).
92 pages, german.
CR-SchemaG.2.2 (Graph Theory)
Keywordsoeffentlicher Verkehr; Verkehrsumlegung; kuerzeste Wege; Minieka; Tiefensuche; Linienverfolgung
Abstract

Zur Prognose der Verkehrsnachfrage in Netzen des öffentlichen Verkehrs (ÖV) wird mit Hilfe von Verkehrsmodellen die Nachfrage F_{i,j} zwischen zwei Verkehrszellen i und j berechnet und auf alle Routen umgelegt, welche von i nach j führen und aus Sicht von Fahrgästen in Betracht kommen. Zur Bewertung von Routen ist eine Widerstandsfunktion definiert, in welche alle für die Routenwahl relevanten Einflußgrößen wie Reisezeit, Fahrtkosten und Reisekomfort eingehen. Gesucht sind alle Wege, deren Widerstand eine vom kürzesten Weg abhängige obere Schranke nicht überschreitet. Die Problemstellung entspricht nicht dem "k-kürzeste-Wege-Problem", weil die Anzahl der gesuchten Wege je Verkehrsbeziehung nicht einheitlich ist und gegenüber der Netzgröße exponentiell wachsen kann. In der Praxis kann ein festes k als obere Schranke für die Anzahl der gesuchten Wege je Verkehrsbeziehung angenommen werden.

Zur Berechnung der gesuchten Wege wurde der Algorithmus nach Minieka sowie das Tiefensuche-Verfahren modifiziert. Außerdem wurde ein spezielles Verfahren (Linienverfolgung) entworfen. Bezüglich Laufzeit benötigt das Minieka-Verfahren O(N^{4}*log(N)*k^{2}), Tiefensuche und Linienverfolgung dagegen nur O(N^{3}*k). Speicherplatzbedarf ist O(N^{3}*k) für Minieka und O(N^{2}*k) für Tiefensuche bzw. Linienverfolgung. Parallelisierung beschleunigt den Ablauf deutlich: O(N^{3}) Zeit für Minieka und O(N^{2}*k) für Tiefensuche bzw. Linienverfolgung. Der Speicherplatzbedarf ist dann bei allen Verfahren O(N^{3}*k).

In der Praxis (Stuttgarter ÖV-Netz mit 785 Verkehrszellen, 784 Haltestellen und 1.064 Linien) sind bis zu 7 Mio. Verkehrswege zu berechnen. Während Minieka am Speicherplatzbedarf scheitert, benötigen Tiefensuche und Linienverfolgung auf schnellen PC's wenige Minuten.

Full text and
other links
PostScript (2386453 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Computer Science, Formal Concepts
Entry dateOctober 16, 1997
   Publ. Computer Science