Untersuchungsgegenstand in dieser Arbeit zur Analyse von Fahrplandaten sind die von öffentlichen Verkehrsmitteln, wobei eine Beschränkung auf Züge erfolgt. Jeder Fahrplan enthält Angaben zu den angefahrenen Bahnhöfe mit den jeweiligen Ankunfts- und Abfahrzeiten. Die Abstraktion der Fahrplandaten besteht in einem durch die Fahrpläne induzierten gerichteten Fahrplangraphen. Dabei wird jeder Bahnhof, der in mindestens einem Fahrplan auftritt, als Knoten im Graph dargestellt. Gibt es für zwei Knoten mindestens einen Fahrplan, in dem diese Knoten direkt aufeinanderfolgende Halte sind, dann gibt es im Fahrplangraph eine gerichtete Kante. Ein solcher Fahrplangraph für den europäischen Zugverkehr umfasste im Sommer 1997 gut 28000 Knoten und 82000 Kanten. In der vorliegenden Arbeit wird eine Lösung für ein mit diesem Fahrplangraphen zusammenhängendes Klassifizierungsproblem entwickelt und vorgestellt. Die Aufgabenstellung lautet: Entscheide für jede Kante eines Fahrplangraphen, ob sie einem Teilstück des physikalischen Schienennetzes entspricht, oder ob die diese Kante induzierenden Züge auf ihrem Weg entlang der Kante einen oder mehrere andere Bahnhöfe ohne Halt durchfahren. Im Fahrplangraph muss also jede Kante als minimal oder transitiv klassifiziert werden. Ausserdem wird für jede transitive Kante die Folge der von sie induzierenden Zügen durchfahrenen Bahnhöfe benötigt. Diese Klassifizierung soll automatisiert und allein auf der Grundlage der Fahrplandaten geschehen. Die Arbeit befasst sich mit einem strukturellen Lösungsansatz für das Klassifizierungsproblem. Dabei wird das Problem auf ein Bündelerkennungsproblem als graphentheoretisches Optimierungsproblem zurückgeführt. Um Lösungen für das zugrundeliegende Anwendungsproblem zu finden, entwickelt die Arbeit zunächst eine Heuristik für das Bündelerkennungsproblem. Schliesslich vergleicht eine umfangreiche Studie die Ergebnisse der Heuristik für den oben erwähnten europäischen Fahrplangraphen aus dem Sommer 1997 für verschiedene Wahlen einer initialen Knotenmenge.
Analyzing train time table graphs
Analyse von Fahrplangraphen
2001
113 Seiten, 54 Bilder, 12 Tabellen, 26 Quellen
Hochschulschrift
Englisch