Wegewahl in heterogenen Netzwerken

Maximilian Franzke

Bachelorarbeit
Institut für Informatik
Ludwigs-Maximilians-Universität München
6. August 2010

Abstract: Anhand des öffentlichen Personennahverkehrsnetzes in München werden heterogene Netze auf ihre Besonderheiten hin untersucht und es wird ein Verfahren vorgestellt, das sie in homogene Netze umwandelt. Auf Grundlage dieses theoretischen Modells wird eine praktische Implementierung in Form einer Fahrtauskunft für den Münchner Nahverkehr als Webservice entwickelt.

1 Einleitung

Schon lange beschäftigt sich die Forschung mit effizienten Routenberechnungen in Netzwerken: Dijkstra veröffentlichte bereits 1959 den nach ihm benannten Algorithmus, der ausnutzt, dass eine optimaler Weg in Teilstecken zerlegt werden kann, welche selbst wiederum optimale Wege sind (Dijkstra, 1959).

Heutzutage ist es möglich, Routen in Sekundenschnelle mit Consumer-Geräten zu berechnen, die unter hundert Euro kosten. Navigationsgeräte haben in Autos und Smartphones Einzug erhalten und auf Websites wie Google Maps lassen sich Wegbeschreibungen in Echtzeit berechnen.

Die meisten dieser Dienste können jedoch nur mit einem Netzwerk umgehen: Der Bordcomputer eines Autos kennt nur das Straßennetz und ermittelt anhand dessen den für ihn bestersichtlichen Weg zum Ziel. Manche tragbare Navigationsgeräte lassen den Benutzer einstellen, ob er zu Fuß, mit dem Fahrrad oder mit dem Auto reist und wählen anhand dieser Vorgabe das für das Fortbewegungsmittel passende Netzwerk aus.
Wie aber soll ein Nutzer verfahren, wenn er – wie in der Realität – eine Wahl zwischen verschiedenen Verkehrsmitteln hat und sich auch bei dieser Wahl von Kostenoptimierung leiten lassen möchte? Er könnte die Kostenabschätzung seines Navigationsgeräts mit der des Routenplaners des öffentlichen Nahverkehrs vergleichen und auf diesem Vergleich basierend seine Entscheidung treffen. Damit übersieht er jedoch Kombinationsmöglichkeiten: Beispielsweise könnte er auch erst mit dem PKW an den Stadtrand fahren, und dort in die U-Bahn umsteigen, um dem Innenstadtverkehr zu entfliehen und schneller ans Ziel zu gelangen, als wenn er für die gesamte Fahrtstrecke das Auto nehmen würde. Auch kann es kostenoptimaler sein, erst einen Fußweg in Kauf zu nehmen, um damit jedoch ein sehr schnelles Verkehrsmittel zu erreichen und so die Gesamtkosten der Reise zu senken.

Ein wichtiger Aspekt für eine realitätsnahe Routenberechnung ist also die Berücksichtigung mehrerer Netzwerke, welche zusammengenommen ein heterogenes Netzwerk ergeben – heterogen dahingehend, als dass sich die Verknüpfungen nicht nur anhand ihrer Kosten, sondern auch weiteren Kriterien unterscheiden (man benötigt zum Beispiel für den Weg über eine Autobahn ein Fahrzeug).

Diese Arbeit soll sich mit dem Problem des Routings durch heterogene Netzwerke beschäftigen und setzt dabei auf das Netz des öffentlichen Nahverkehrs von München auf. Die jeweils homogenen Netze der Linien werden zu einem heterogenen Netz zusammengefasst, auf welchem das Routing stattfinden wird. Diese Anwendung soll dann als Webservice implementiert werden und es Nutzern so ermöglichen, die für sie beste Verbindung mit öffentlichen Verkehrsmitteln herzustellen.

2 Begriffsklärungen

Da das System des öffentlichen Nahverkehrs als Software modelliert werden soll, ist es wichtig, zunächst einige Begriffe klar zu definieren:

Eine Station ist ein abstraktes Konstrukt, welches Bahnsteige und Haltestellen, aber auch Infrastruktureinrichtungen wie Fahrkartenautomaten, Treppen und Geschäfte semantisch zusammenfasst. Dadurch, dass diese Elemente innerhalb einer Station gruppiert werden, wird ein Bezug untereinander hergestellt. Bei Bahnsteigen etwa, die zur selben Station gehören, lässt sich aus dieser Relation dann eine Umsteigemöglichkeit ableiten. Stationen haben in der Regel einen eindeutigen Namen, der auch an Fahrgäste kommuniziert wird.

Eine Linie bedient eine Menge an Stationen in einer bestimmten Reihenfolge und in bestimmten Zeitintervallen. Diesem Linienverlauf folgen dann einzelne Fahrzeuge. Stoppen diese Fahrzeuge auf ihrem Weg an einer Station, um das Ein- und Aussteigen zu ermöglichen, spricht man von einem Halt. Wird von einem Fahrzeug an einer Station in eines einer anderen Linie gewechselt, wird umgestiegen.

Ein Verkehrsmittel gibt Aufschluss darüber, wie eine Linie in der Realität implementiert ist: Schienengebundene Verkehrsmittel sind bezüglich ihrer Wegewahl viel weniger flexibel als straßengebundene, wobei letztere jedoch weiteren Einflüssen wie der allgemeinen Verkehrslage unterliegen und somit höhere Schwankungen im Fahrplanbetrieb haben können.

3 Datengrundlage

Als Datengrundlage dient das öffentliche Nahverkehrsnetz Münchens, das vom Münchner Verkehrs- und Tarifverbund (MVV) betrieben wird. Unter dessen Dach bieten verschiedene Verkehrsunternehmen wie etwa die DB Regio AG oder die Münchner Verkehrsgesellschaft mbH (MVG) (MVV, 2010) ihre Dienste unter dem »1 Netz. 1 Fahrplan. 1 Ticket« in München und acht angrenzenden Landkreisen an (MVV, 2010). Im Rahmen dieses Projekts werden jedoch nur diejenigen Linien des Netzes betrachtet, die tatsächlich zumindest teilweise auf dem Stadtgebiet von München verlaufen. Insbesondere werden nur sogenannte Stadt- und Metrobusse behandelt und keine Überlandbusse zu ferneren Zielen, auch wenn diese innerhalb des Stadtgebiets beginnen. Metrobusse lassen sich an ihrer zweistelligen, Stadtbusse an ihrer dreistelligen, mit einer »1« beginnenden Liniennummer erkennen.

3.1 Datenerhebung

Um rechtlich einwandfreie und informationstechnisch gut weiterzuverarbeitende Daten zu generieren, wurden die Netzinformationen von Hand in eine Datenbank erfasst. Dabei wurde der Prozess softwaretechnisch stark optimiert, sodass eine zügige Dateneingabe möglich war.

Anhand von Fahrplänen und Netzplänen wurden zunächst die Stationen erfasst, wobei hier zunächst der Name der hinzuzufügenden Station in ein Formular eingetragen und dann die entsprechende Position der Haltestelle in einer Kartenansicht angeklickt wurde. Die Software vergab dann automatisch eindeutige Identifikationsnummern und berechnete die exakten Längen- und Breitengrade anhand der Mausklickposition.

Linien konnten nach dem Anlegen Stationen zugeordnet und diese dann sortiert werden, um den Verlauf der Linie exakt wiederzugeben. Wenn Stationen den Linien bereits in ihrer tatsächlichen Reihenfolge hinzugefügt wurden, war ein späteres Sortieren nicht mehr notwendig.

Ein Großteil dieser Daten stand schon vor dem Beginn dieser Arbeit zur Verfügung und konnte so sofort benutzt werden.

3.2 Datenrepräsentation

Die Daten für das Verkehrsnetz werden in einer MySQL-Datenbank im Wesentlichen in drei Tabellen gehalten:

Tabelle stations (id, name, geoinformation)
Diese Tabelle ist für die Verwaltung der Stationen zuständig. Hier werden IDs und Namen an die Stationen vergeben sowie zusätzliche Geo-Informationen wie Längen- und Breitengrad vorgehalten.
Tabelle lines (id, mean, name)
Linien werden hier gespeichert, wobei jede Linie über eine eindeutige ID und einen Namen verfügt. Zusätzlich bestehen Informationen über die Art der Linie (S-Bahn, U-Bahn, Tram oder Bus) – englisch: mean.
Tabelle routes (line, station, position)
Hier werden die Tabellen stations und lines über eine m:n-Verbindung kombiniert. Stationen können Linien beigewiesen und über eine Positionsangabe in ihrer Abfolge geordnet werden.

3.3 Datenmenge

Die hinterlegten Daten decken alle S-Bahn-, U-Bahn und Tramlinien sowie die Buslinien auf dem Münchner Stadtgebiet ab. Quantitativ stehen somit folgende Anzahlen an Daten zur Verfügung:

Linien: 93
- Davon S-Bahn: 10
- Davon U-Bahn: 6
- Davon Tram: 11
- Davon Bus: 66
Stationen: 1102
Halte an Stationen: 1960

3.3.1 Stationen nach Frequentierung

Für weitere Berechnungen ist es hilfreich, einen kurzen Überblick darüber zu bekommen, wie stark einzelne Stationen frequentiert werden – also wie viele Linien an einer Station verkehren. An zentralen Stationen wie dem Hauptbahnhof liegt deren Anzahl etwa höher als an kleinen Halten in den Außenästen; um jedoch genauere Aussagen über den Anteil der stark und der schwach frequentierten Stationen treffen zu können, ist eine genauere Analyse notwendig.

Abbildung 1: Anzahl Stationen gruppiert nach der Anzahl der an ihnen haltenden Linien

Wie sich leicht aus Abbildung 1 ablesen lässt, nimmt die Anzahl der Stationen exponentiell zu, wenn weniger Linien an ihnen halten. Die Station mit den meisten Halten ist der Hauptbahnhof (18 Linien), gefolgt von Karlsplatz (Stachus) und Ostbahnhof (je 16 Linien). Durchschnittlich halten an einer Station 1,78 Linien.

3.3.2 Linienlängen

Interessant ist auch zu wissen, wie viele Stationen von einer Linie bedient werden. Hierbei werden die unterschiedlichen Linien nach Verkehrsmittel farblich unterschieden:

Abbildung 2: Linien sortiert nach Anzahl der Halte

Kürzeste Linie ist Bus 186, die längste Bus 54. Durchschnittlich hält eine Linie an 21,08 Stationen.

3.4 Probleme

Leider bringt diese Form der Datenrepräsentation auch einige Probleme mit sich, die sich im Praxiseinsatz zeigten.

3.4.1 Asymmetrische Route

Bei der Verarbeitung der Daten wird davon ausgegangen, dass die Richtung, in der die Route einer Linie abgefahren wird, irrelevant ist. Dies bedeutet, dass davon ausgegangen wird, dass die Rückfahrt genau der umgekehrten Hinfahrt entspricht. In der Praxis gibt es jedoch (vor allem im Busverkehr) einzelne Stationen, die nur aus einer Richtung bedient werden, beispielsweise die Haltestelle Maxvorstadt der Buslinie 100.

Abbildung 3: Ausschnitt »Maxvorstadt« der Buslinie 100. Repräsentation im Datenbestand (Oben), daraus resultierende Implementierung als Graph (Mitte) und tatsächlicher Verlauf (Unten)

Somit wird bei der Implementierung fälschlicherweise in Westrichtung ein Halt eingefügt, obwohl dies in der Realität nicht der Fall ist. Dieses Problem kann nicht über einen Algorithmus gelöst werden, sondern es müssten im Datenbestand die Stationen der Routen dahingehend markiert werden, aus welcher Richtung sie angefahren werden (»hin«, »zurück« oder »beide«).

3.4.2 Verzweigte Linien

Es wird bei der Verwaltung der Linien davon ausgegangen, dass eine Linie genau einen Endhaltestelle mit einer anderen verbindet. Situationen mit mehr als zwei Endhaltestellen lassen sich nicht exakt Abbilden. In der Realität führt etwa die S1 vom Ostbahnhof sowohl zum Flughafen München als auch nach Freising, da in Neufahrn der Zug aufgetrennt wird und ein Zugteil nach Freising, der andere zum Flughafen weiterfährt. Die S1 wurde als Notlösung so implementiert, dass sie nun erst nach Freising, dann wieder zurück nach Neufahrn und schließlich zum Flughafen führt.

Abbildung 4: Verlauf der S1 nach Freising bzw. zum Flughafen. Provisorische Modellierung (Oben) und realer Verlauf mit verschiedenen Zugteilen (hell- und dunkelblau, Unten)

Noch viel extremer wird dieses Problem, wenn man das Beispiel der Londoner District Line betrachtet. Diese Linie verfügt über zahlreiche Außenäste, auf denen zusätzlich Züge mit verschiedenen Zielen verkehren. Von Upminster etwa fahren Züge sowohl nach Wimbledon als auch nach Richmond.

Abbildung 5: Schematischer Verlauf der Londoner District Line

Eine Lösung des Problems bestünde darin, eine Linie in der Realität durch mehrere Linien zu modellieren, wobei es hier zwei prinzipiell mögliche Ansätze gibt:

Von einer zentralen »Verteilerstation«, die in jeder Situation angefahren wird (etwa Neufahrn im Beispiel) wird für jeden Ast eine neue Linie angelegt. Es muss dann virtuell umgestiegen werden, um den Außenast zu erreichen.
Von jeder (tatsächlichen) Endstation aus wird eine Linie zu jedem von hier aus angefahrenen Ziel erstellt (im Beispiel der District Line wird also eine Linie DL1 von Upminster nach Richmond und eine Linie DL2 von Upminster nach Wimbledon erstellt). Dieser Ansatz fasst also identische Zugverbindungen als Linie zusammen.

Bei beiden Ansätzen muss das System dann allerdings bei der finalen Ausgabe gegenüber dem Benutzer die einzelnen Sub-Linien wieder zu einer einheitlichen Linie zusammenfassen, um den aus dem Alltag gewohnten Eindruck des Netzlinienplans aufrecht zu erhalten. Ähnliche Probleme entstehen bei der Modellierung einer ringförmigen Linie (wie etwa der Londoner Circle Line), bei der es überhaupt keine Endhaltestellen gibt.

3.4.3 Mehrfaches Anfahren von Stationen

Bildet eine Linie in ihrem Verlauf einen Kreis, indem eine Station mehrmals angefahren wird, kommt es ebenfalls zu Problemen. Ein Beispiel sei hier wieder die Buslinie 100, die beim Kreuzen der Ludwigstraße einen Halt an der Station Von-der-Tann-Straße einlegt, zum Odeonsplatz abbiegt, dort wendet und erneut an der Von-der-Tann-Straße hält. Das System fügt für jeden Streckenabschnitt eine Kante ins Netz ein, gibt jedoch nicht vor, in welcher Reihenfolge diese abgefahren werden müssen. So wird bei der Routenberechnung zwischen Amalien- und Königinstraße die direkte Verbindung ohne Umweg über den Odeonsplatz angenommen.

Abbildung 6: Ausschnitt »Von-der-Tann-Straße«. Oben: Tatsächliche Fahrstrecke, Unten: Realisierter Graph, über den der Abzweig zum Odeonsplatz nicht als notwendig passierbar markiert ist.

Lösen lässt sich dieser Umstand, indem die Station Von-der-Tann-Straße in zwei verschiedene Sub-Stationen aufgespalten wird, wobei dann die Route über Von-der-Tann-Straße₁ – Odeonsplatz – Von-der-Tann-Straße₂ führt (in der Realität sind die zwei Haltestellen auch unterschiedlich; lediglich ihre Bezeichnung ist identisch). Das System müsste dann wieder bei einer Kommunikation mit dem Benutzer die Sub-Stationen zusammenfassen.

4 Expansion des Netzes

Wie aus der Vorstellung der zugrundeliegenden Daten folgt, ist die Abbildung des Verkehrsnetzes eine Abstraktion der tatsächlichen Verhältnisse, die im Wesentlichen dem Schema eines Aushang-Netzplanes entspricht. Dabei wird jede Station als Knotenpunkt betrachtet, wobei mehrere Knotenpunkte mittels der verschiedenen Linien des Verkehrssystems verbunden werden.

Abbildung 7: Ausschnitt »Feldmoching« aus dem Netzlinienplan mit S1 (blau) und U2 (rot), links ohne und rechts mit gerichteten Kanten

Diese Repräsentation ermöglicht eine einfache und effiziente Form der Dateneingabe durch den Menschen, da sie sich sehr an der bildlichen Realität orientiert. Leider ist diese Repräsentation für die Berechnung nicht hinreichend, da außer Verbindungen und Umsteigemöglichkeiten keine Informationen zur Verfügung stehen: Verbindungen können als Kanten gesehen werden und mit entsprechenden Kosten wie Entfernung oder Reisezeit belegt werden – allerdings gestaltet sich dies bei den Stationen wesentlich unpraktischer. Denn mit welchen Kosten eine Station bei der Routenberechnung ins Gewicht fällt, hängt maßgeblich von den dort zu erfüllenden Aktionen ab: Einfach nur im Zug sitzen bleiben und kurz warten, während er anhält, ist kostentechnisch viel billiger als auszusteigen, den Bahnsteig zu wechseln, auf den Anschlusszug zu warten und die Station mit einer anderen Linie zu verlassen.

Die Kosten, mit denen eine Station bei der Routenberechnung ins Gewicht fällt hängen also davon ab, mit welcher Linie die Station erreicht und mit welcher Linie sie wieder verlassen wird. Prinzipiell ist es möglich, von jeder Linie, die in die Station hineinführt, auf jede herausführende zu wechseln.

Abbildung 8: Ausschnitt »Feldmoching« aus dem Netzlinienplan mit eingetragenen Kanten- und Knotenkosten

Um diesen Sachverhalt zu modellieren, wird das Netz expandiert: Jede Station wird ein neues Sub-Netz aufgespalten, bei dem es für jede hinein- und herausführende Linie einen Knoten gibt und diese untereinander mit Kanten versehen werden, welche die Umsteigevorgänge symbolisieren. Diese Kanten können dann entsprechend ihrer Kosten gewichtet werden: Sitzenbleiben kann als billiger modelliert werden, als auf einen anderen Zug zu warten.

Abbildung 9: Eingezeichnetes Sub-Netz »Feldmoching«

Dadurch ergibt sich noch ein weiterer Vorteil: Knoten haben nun keine Gewichte mehr, da die Kosten der ursprünglichen Stationen auf die Kanten innerhalb der Sub-Netze übertragen wurden. Dies vereinfacht die Routenberechnung, da nur noch Kanten betrachtet werden müssen.

Anmerkung: Wie in der Abbildung 9 ersichtlich, sind die Kosten für beispielsweise die Strecke Oberschleißheim – Feldmoching – Oberschleißheim fehlerhaft eingetragen: Die Kosten für das Warten auf die Gegenrichtung sind mit den selben Kosten angesetzt wie das Weiterfahren in die ursprüngliche Richtung. Dieser Umstand kann jedoch bei der Berechnung einer optimalen Wegstrecke vernachlässigt werden, da eine derartige Route nicht optimal sein kann (im Beispiel wäre die einfache Route Oberschleißheim optimaler).

Um das Problem in anderen Szenarien zu beheben, ist es ausreichend, die Ein- und Ausgänge jeweils soweit aufzuspalten, bis sie nur noch von einer einzigen Kante außerhalb des Sub-Netzes erreicht werden.

4.1 Variable Start- und Endpunkte

Da der Benutzer in der Praxis seine Start- und Zieleingabe über die Angabe der Stationsnamen treffen wird, ist es problematisch, den tatsächlichen Start- und Endknoten im Graphen zu bestimmen, da durch die Expansion der Stationen zu Sub-Netzen keine eigentlichen Stations-Knoten mehr existieren. Zwar wäre eine Abbildung etwa der Starteingabe auf die Ausgangsknoten der Start-Station möglich, doch kann es an der Start-Station mehrere ausgehende Linienverbindungen geben, sodass nicht eindeutig bestimmt werden kann, welcher Ausgang als Startknoten ausgewählt werden soll.

Um dieses Problem zu beseitigen, werden in den Sub-Netzen der Start- und Ziel-Station (und nur in diesen) je ein virtueller Knoten eingefügt. Im Start-Sub-Netz wird dieser Knoten nun mit allen Ausgangsknoten über Kanten ohne Kosten verbunden, im End-Sub-Netz entsprechend mit allen Eingangsknoten. Diese virtuellen Knoten werden dann für die Routenberechnung als eindeutige Start- und Zielknoten berücksichtigt. Durch die nichtvorhandenen Kosten kann so die Start-Station mit jeder beliebigen Linie verlassen und die Zielstation mit jeder beliebigen Linie erreicht werden.

Abbildung 10: Einfügen eines virtuellen Start-Knotens in das Sub-Netz der Start-Station (links) und eines virtuellen End- Knotens in das der End-Station (rechts). Die grün eingetragenen Verbindungen zeigen die Richtung der Kanten, mit denen die virtuellen Knoten verknüpft werden.

Da Start- und Zielknoten nur in der Start- beziehungsweise Zielstation eingefügt werden, muss das Netz für jede Routenanfrage seitens des Nutzers individuell neu expandiert werden. Alternativ kann einmalig auch zu jeder Station je ein Start- und ein Zielknoten eingefügt werden, wodurch man das daraus resultierende Netz zwischenspeichern und für jede Anfrage – unabhängig von Start- und Zieleingabe des Benutzers – verwenden kann. So spart man sich bei der Routenberechnung den Expansionsvorgang.

4.2 Algorithmus

Die Pseudocode-Implementierung expandiert das Netz, indem sie Informationen über Stationen, Linien und Fahrtstrecken nach der vorgestellten Methode verarbeitet. Daraus entsteht das Netz, das Wegewahlalgorithmen verarbeiten können. Dieses ist dann durch die Variablen knoten und verbindungen repräsentiert:


					stationen = new Array()

					knoten = new Array()

					verbindungen = new Array()

					

					Wiederhole für jede Station s

					    stationen[s.id].id = s.id

					    stationen[s.id].eingehend = new Array()

					    stationen[s.id].ausgehend = new Array()

					    Falls s = Starteingabe oder s = Zieleingabe

					        knoten.push(s.id)

					    Ende Falls

					Ende Wiederhole

					

					Wiederhole für jede Linie l

					    Wiederhole für jedes Segment s

					        stationen[s.Anfangsstation.id].ausgehend.push(l)

					        stationen[s.Zielstation.id].eingehend.push(l)

					        ausgang = s.Anfangsstation.id + '-Ausgang-' + l

					        eingang = s.Zielstation.id + '-Eingang-' + l

					        verbindung = new Verbindung()

					        verbindung.von = ausgang

					        verbindung.nach = eingang

					        verbindung.mittels = l

					        verbindungen.push(verbindung)

					        Falls eingang noch nicht in knoten enthalten

					            knoten.push(eingang)

					        Ende Falls

					        Falls ausgang noch nicht in knoten enthalten

					            knoten.push(ausgang)

					        Ende Falls

					    Ende Wiederhole

					Ende Wiederhole

					

					Wiederhole für jede Station s

					    Wiederhole für jedes s.eingehend e

					        Wiederhole für jedes s.ausgehend a

					            verbindung = new Verbindung()

					            verbindung.von = s.id + '-Eingang-' + e

					            verbindung.nach = s.id + '-Ausgang-' + a

					            verbindung.mittels = NULL

					            verbindungen.push(verbindung)

					        Ende Wiederhole

					        Falls s = Zieleingabe

					            verbindung = new Verbindung()

					            verbindung.von = s.id + '-Eingang-' + e
 
					            verbindung.nach = s.id

					            verbindung.mittels = NULL

					            verbindungen.push(verbindung)

					        Ende Falls

					    Ende Wiederhole

					    Falls s = Starteingabe

					        Wiederhole für jedes s.ausgehend a

					            verbindung = new Verbindung()

					            verbindung.von = s.id

					            verbindung.nach = s.id + '-Ausgang-' + a

					            verbindung.mittels = NULL

					            verbindungen.push(verbindung)

					        Ende Wiederhole

					    Ende Falls

					Ende Wiederhole

4.3 Probleme bei der Erweiterung

Bei genauerer Betrachtung erweist sich diese Erweiterung als noch nicht vollständig: Je Linie gibt es nur einen Eintritts- und einen Austrittspunkt. Da eine Linie jedoch immer als eine Hin- und eine Rückroute betrachtet wird (siehe auch Asymmetrische Route), müssten an jeder Station eigentlich je zwei dieser Punkte eingefügt werden – für jede Richtung einen. Wird dies nicht gemacht, steht etwa beim Umsteigen von einer Linie in eine andere nur eine Kante zur Verfügung – ungeachtet der Fahrtrichtung, mit der dann in der neuen Line weitergefahren wird. Dadurch, dass nur diese eine Kante zur Verfügung steht, kann auch nur ein Kostenkriterium angegeben werden, das dann für beide Fälle gelten soll. In der Realität ist es jedoch sehr häufig der Fall, dass Hin- und Rückrichtung eben nicht zum selben Zeitpunkt am Bahnsteig halten.

Um wirklich all diese Fälle behandeln zu können, müssen somit

für jede Linie an jeder Station vier Knoten eingefügt werden:
- Eintrittspunkt Hinrichtung
- Eintrittspunkt Rückrichtung
- Austrittspunkt Hinrichtung
- Austrittspunkt Rückrichtung
von jedem Eintrittspunkt zu jedem Austrittspunkt (aller Linien) eine Kante eingefügt werden, wobei die Kante zu den Austrittspunkten derselben Linie weggelassen werden können (Querverbindungen)

Dies Resultiert natürlich in einer höheren Kantenanzahl. Für große Station kann man diese Zahl noch leicht senken, indem erst die Eintritts- und Austrittspunkte angelegt werden und nun für jede Linie ein Intermediate-Knoten angelegt wird, von welchem dann zwei Verbindungen zu den Austrittsknoten dieser Linie angelegt werden. Diesen Kann man sich als Warteposition am Bahnsteig vorstellen, wenn noch nicht entschieden ist, in welche Richtung weitergefahren wird. Die Wartezeit, bis dann ein Fahrzeug der entsprechenden Richtung eintrifft, kann dann als Kostenattribut dieses Intermediate-Knotens zum jeweiligen Austrittsknoten modelliert werden. Um diesen Intermediate-Knoten überhaupt erreichen zu können, wird von jedem Eintrittsknoten eine Kante zu jedem Intermediate-Knoten geführt, solange es sich um den einer anderen Linie handelt. Dieser Intermediate-Knoten kann vom Algorithmus automatisch eingefügt werden, da davon ausgegangen werden kann, dass die Halte beider Richtungen an einer Station in enger Nachbarschaft liegen. Ist man bereit, zusätzliches Realitätswissen zu modellieren, können die Intermediate-Knoten zu vollständigen Bahnsteig-Metaphern abstrahiert werden, wobei dann jeder Intermediate-Knoten genau einen Bahnsteig repräsentiert, an welchem jedoch mehrere Linien verkehren können. Durch Verwendung von Intermediate-Knoten werden also die Gesamtkosten zwischen dem Verlassen eines Fahrzeugs und dem betreten des Anschlussfahrzeugs in zwei Kostenbereiche aufgeteilt: Transfer zum neuen Bahnsteig und dortige Wartezeit, bis das Fahrzeug auch eintrifft.

Bei beiden Ansätzen müssen noch je Linie und Fahrtrichtung der Eintritts- mit dem Austrittsknoten verbunden werden, um die Kostensituation »sitzenbleiben, Halt abwarten und weiterfahren« modellieren zu können (Direktverbindungen).

4.3.1 Performance-Verbesserung durch Intermediate-Knoten

Sowohl für das Routing mit als auch das ohne Intermediate-Knoten kann die Anzahl der Kanten des Sub-Netzes der Station kann allgemein in Abhängigkeit von der Anzahl l der dort verkehrenden Linien mathematisch ermittelt werden:

Nahezu analog dazu unter Verwendung von Intermediate-Knoten:

Beide Varianten bewegen sich in der Komplexität von O(n²). Um herauszufinden, ab welcher Größenordnung sich welcher Ansatz als sparsamer erweist, werden folgende Wertetabelle und die Graphen der Funktionen in Abhängigkeit von der Anzahl der Linien betrachtet:

Abbildung 11: Graph der Sub-Netz-Kanten-Funktionen für verschiedene Wertebereiche

Anzahl Linien l:	Resultierende Anzahl Kanten ohne Verwendung von Intermediate-Knoten:	Resultierende Anzahl Kanten mit Verwendung von Intermediate-Knoten:
1	2	4
2	12	12
3	30	24
4	56	40
5	90	60
6	132	84
7	182	112
8	240	144
9	306	180
10	380	220
11	462	264
12	552	312
13	650	364
14	756	420
15	870	480
16	992	544
17	1122	612
18	1260	684
19	1406	760
20	1560	840

Tabelle 1: Anzahl Kanten in Sub-Netz-Expansion

Wie sich aus Abbildung 11 und Tabelle 1 ablesen lässt, bringt es bereits ab zwei Linien pro Station im Hinblick auf die Anzahl der Kanten keinen Vorteil mehr, auf die Intermediate-Knoten zu verzichten. Allerdings sollte beachtet werden, dass bei der Variante mit Intermediate-Knoten zusätzliche Knoten ins Netz eingefügt werden müssen (nämlich für jede Linie einen), was die Anzahl der zu untersuchenden Knoten im Dijkstra- oder A*-Algorithmus nach oben treibt.

Die Ersparnis sollte zudem sehr kritisch betrachtet werden, weil bei »kleinen« Stationen – also solchen, an denen nur eine einzige Linie hält – der Verwaltungsaufwand höher liegt: Es werden zusätzliche Kanten und Knoten eingefügt, die die insgesamt betrachtete Ersparnis wieder senken. Öffentliche Nahverkehrsnetze sind oftmals genau mit dem Ziel organisiert, Stationen auf den Außenästen nur mit einer einzigen Linie zu bedienen oder in dünner frequentierten Gebieten etwa Buslinien ein- zurichten, die die alleinige Versorgung für viele Haltestellen übernehmen – hier entsteht durch die Intermediate-Knoten immenser Overhead, obwohl sie an dieser Stelle gar nicht benötigt werden würden.

Es ist auch möglich, eine Hybrid-Lösung zu implementieren, bei der erst dann begonnen wird, an einer Station Intermediate-Knoten einzufügen, wenn diese von mindestens drei Linien bedient wird. Dadurch wird allerdings wiederum der Verwaltungsaufwand erhöht, wenn Kostenfunktionen wie Fahrpläne oder Regelwerke auf die Sub-Netze angewendet werden sollen – hierbei müssen dann beide Fälle betrachtet werden.

4.3.2 Größenordnungen in der praktischen Implementierung

In der praktischen Implementierung zeigte sich die Berücksichtigung der Fahrtrichtung als äußerst kritisch: Wie bereits in Tabelle 1 und Abbildung 11 ersichtlich, werden immens viele neue Kanten in die Sub-Netze eingefügt. Als bei der Routenberechnung auch die Buslinien berücksichtig wurden, wurde das Netz so komplex, dass die Berechnung als implementierter Webservice nicht mehr möglich war. Betrachtet man die Größe der Netze bei den unterschiedlichen Varianten, lässt sich leicht die Komplexität verdeutlichen:

Betrachtete Verkehrsmittel: S = S-Bahn, U = U-Bahn, T = Tram, B = Bus	Größe des Netzes ohne Berücksichtigung der Fahrtrichtung:		Größe des Netzes mit Berücksichtigung der Fahrtrichtung (ohne Intermediates):
	Kanten:	Knoten:	Kanten:	Knoten:
S	1283	500	3222	998
U	448	258	840	514
T	949	480	1992	958
B	5937	2818	12970	5634
S, U	1897	756	4726	1510
S, T	2518	978	6358	1954
S, B	7760	3314	18344	6626
U, T	1575	736	3544	1470
U, B	6877	3070	15766	6138
T, B	7322	3292	16990	6582
S, U, T	3310	1234	8574	2466
S, U, B	8866	3566	21804	7130
S, T, B	9431	3788	23208	7574
U, T, B	8440	3544	20198	7086
S, U, T, B	10715	4040	27380	8078

Tabelle 2: Größe des Netzes nach Berücksichtigung der Fahrtrichtung

Einerseits fällt die signifikante Anzahl an Kanten und Knoten auf, aus denen die Linieninformationen für die Busse bestehen. Das Bus-Netz (B) ist größer und damit komplexer als das aus den übrigen Verkehrsmitteln gebildete Gesamtnetz (S, U, T). Andererseits wird hier deutlich, dass die Kombination mehrerer Verkehrsmittel zu einem kombinierten Netz die Komplexität um einen deutlich größeren Betrag erhöht, als wenn man lediglich die Knoten und Kanten der Komponenten addiert (Betrachtung der Daten mit Berücksichtigung der Fahrtrichtung):

Der Zuwachs an Kanten bei Kombination mehrerer Netze von Verkehrsmitteln lässt sich durch die Transitmöglichkeiten innerhalb der »Kreuzungsstationen« erklären, welche wie Umsteigewege implementiert werden. Dass die Anzahl der Knoten sogar geringfügig darunter liegt, ist darin begründet, dass bei jedem Gesamtnetz zwei virtuelle Start- und Endknoten eingefügt werden, deren Duplizität bei der Kombination entfernt werden kann. Da bei Verzicht auf Intermediates keine neuen Knoten in die Sub-Netze eingefügt werden, kann deren Zahl auch nicht steigen – die weitere Betrachtung beschränkt sich nun auf die Anzahl der Kanten. Tabelle 3 zeigt den Zuwachs prozentual:

Betrachtetes Netz bestehend aus Verkehrsmitteln:	Netz wird gebildet aus Kombination dieser Netze:	Theoretische Anzahl Kanten des Gesamtnetzes durch Addition der Kantenanzahlen der Komponenten:	Tatsächliche Anzahl Kanten des Gesamtnetzes:	Abweichung im Verhältnis zur theoretischen Anzahl:
(S, U)	(S), (U)	4062	4726	16,3%
(S, T)	(S), (T)	5214	6358	21,9%
(S, B)	(S), (B)	16192	18344	13,3%
(U, T)	(U), (T)	2832	3544	25,1%
(U, B)	(U), (B)	13810	15766	14,2%
(T, B)	(T), (B)	14962	16990	13,6%
(S, U, T)	(S), (U), (T)	6054	8574	41,6%
(S, U, T)	(S), (U, T)	6766	8574	26,7%
(S, U, T)	(S, T), (U)	7198	8574	19,1%
(S, U, T)	(S, U), (T)	6718	8574	27,6%
(S, U, B)	(S), (U), (B)	17032	21804	28,0%
(S, U, B)	(S), (U, B)	18988	21804	14,8%
(S, U, B)	(S, B), (U)	19184	21804	13,7%
(S, U, B)	(S, U), (B)	17696	21804	23,2%
(S, T, B)	(S), (T), (B)	18184	23208	27,6%
(S, T, B)	(S), (T, B)	20212	23208	14,8%
(S, T, B)	(S, B), (T)	20336	23208	14,1%
(S, T, B)	(S, T), (B)	19328	23208	20,1%
(U, T, B)	(U), (T), (B)	15802	20198	27,8%
(U, T, B)	(U), (T, B)	17830	20198	13,3%
(U, T, B)	(U, B), (T)	17758	20198	13,7%
(U, T, B)	(U, T), (B)	16514	20198	22,3%
(S, U, T, B)	(S), (U), (T), (B)	19024	27380	43,9%
(S, U, T, B)	(S, U), (T, B)	21716	27380	26,1%
(S, U, T, B)	(S, T), (U, B)	22124	27380	23,8%
(S, U, T, B)	(S, B), (U, T)	21888	27380	25,1%
(S, U, T, B)	(S, U), (T), (B)	19688	27380	39,1%
(S, U, T, B)	(S), (U), (T, B)	21052	27380	30,1%
(S, U, T, B)	(S, T), (U), (B)	20168	27380	35,8%
(S, U, T, B)	(S), (T), (U, B)	20980	27380	30,5%
(S, U, T, B)	(S, B), (U), (T)	21176	27380	29,3%
(S, U, T, B)	(S), (B), (U, T)	19736	27380	38,7%
(S, U, T, B)	(S, U, T), (B)	21544	27380	27,1%
(S, U, T, B)	(S, U, B), (T)	23796	27380	15,1%
(S, U, T, B)	(S, T, B), (U)	24048	27380	13,9%
(S, U, T, B)	(S), (U, T, B)	23420	27380	16,9%

Tabelle 3: Betrachtung der Kantenanzahl bei Kombination verschiedener Verkehrsmittel

Betrachtet man den vorhin erwähnten Praxisfall, bei dem zum vorhandenen Netz (S, U, T) nun das Bus-Netz hinzugefügt wurde – also das Netz (S, U, T, B) aus der Kombination der Komponenten (S, U, T) und (B) erzeugt wird – so zeigt Tabelle 3 sehr deutlich, wie zu den bestehenden 8574 Kanten von (S, U, T) erst 12970 Kanten von (B) und dann nochmals 5839 Kanten für die Transitverbindungen hinzugefügt werden. Das ursprüngliche Netz (S, U, T) ist also im Bezug auf seine Kantenanzahl um den Faktor 3,2 angewachsen, indem die Buslinien (B) hinzugefügt wurden. Diese Verdreifachung der Datenmenge führte dann im Praxisfall dazu, dass der Algorithmus seine Berechnungen unter Berücksichtigung der Richtungsinformationen nicht mehr mit den vorhandenen Ressourcen nicht mehr abschließen konnte.

4.3.3 Kompromisslösung

Wie in Kapitel 4.3.2 berichtet, stehen nicht genügend Ressourcen zur Verfügung, um die Routenberechnung noch als Webservice mit den an einen solchen gestellten Erwartungen (sekundenschneller Seitenaufbau, schnelle Reaktionszeit) unter Berücksichtigung aller Features zu implementieren. Daher ergeben sich für das weitere praktische Vorgehen grundsätzlich zwei Möglichkeiten:

Weglassen der Buslinien, um die Netzgröße klein zu halten
Dadurch, dass auf die große Anzahl der Buslinien verzichtet wird, müssen viel weniger Informationen bei der Routenberechnung berücksichtigt werden, sodass noch ausreichend Ressourcen für die Richtungsbehandlung zur Verfügung stehen.
Nichtbehandlung der Richtungsinformationen
Verzichtet man auf eine Behandlung der Fahrtrichtung bei den Transitvorgängen innerhalb von Stationen, werden die Sub-Netze weniger drastisch aufgebläht und das System kann alle vorhandenen Informationen verarbeiten, ohne dass die Datengrundlage künstlich beschnitten werden muss.

Im Praxisteil werden nun die Richtungsinformationen nicht behandelt, dafür aber die Buslinien hinzugezogen. Denn das Busnetz ist eine elementare Komponente, die den Wegewahl-Algorithmus erst interessant macht: Während S-Bahn- und Tram-Netz sternförmig angelegt sind, um das Zentrum mit den Außengebieten zu verbinden und das U-Bahn-Netz im Innenstadtbereich eine grobes Gitter darstellt, verbinden die Buslinien die anderen Linienäste in den Randbereichen auch direkt untereinander und übernehmen eine tangentiale Funktion. Dies macht ihre Betrachtung bei der Routenberechnung elementar.
Durch diese Entscheidung können nun jedoch keine genauen Abfahrtszeiten und somit die genauen Umsteigekosten ermittelt werden, wie in 4.1 erläutert. Da jedoch für den Praxiseinsatz keine realen Fahrplandaten vorhanden sind, könnte dieses Feature sowieso nur im Ansatz implementiert werden. Während dieses in der Theorie noch behandelt wird, findet es in der Praxis keine Anwendung, da die Verwendung der konkret vorhandenen Buslinieninformationen dem Benutzer gegenüber einen höheren Mehrwert bietet als eine Schnittstelle zu einer (nicht vorhandenen) Fahrplanschnittstelle.

5 Routenberechnung und Implementierung

Das Programm zur Routenberechnung ist als Web-Service implementiert und kann im Internet erreicht und benutzt werden. Die Daten (vergleiche Kapitel 3.2) werden in einer MySQL-Datenbank vorgehalten und für die Berechnung der Route wird serverseitig PHP verwendet. Dem Benutzer werden dabei normale XHTML-Seiten ausgeliefert, welche für eine bessere Interaktion mit JavaScript unter Verwendung des jQuery-Frameworks angereichert werden.

5.1 Komponenten

Das System für die Routenberechnung ist modular aufgebaut und besteht aus Komponenten, die weitgehend unabhängig vom Rest des Systems arbeiten und somit austauschbar sind, wenn weitere Funktionen hinzugefügt werden sollen:

Das Frontend kommuniziert mit dem Benutzer und fragt die Parameter (Start und Ziel, gegebenenfalls auch Uhrzeit und weitere Einstellungen) vom Benutzer ab und gibt später auch die berechnete Route aus.
Der Netz-Expander wandelt die interne und leicht zu verwaltende Datenrepräsentation nach der in Kapitel 4 vorgestellten Technik in ein Netz aus Kanten und Knoten um, auf denen die Routenberechnung dann durchgeführt wird. Dabei wird der Kostenvektor der Kanten und Knoten noch weggelassen, um dessen Behandlung flexibler zu gestalten.
Das Kosten-Modul verwaltet Informationen zu Fahrzeiten und Kosten und ist somit die Modellierung der Fahrpläne. Es kann in Abhängigkeit von Zeit und Ort ermitteln, wann die nächste Verbindung besteht und verwendet ein internes Regelwerk, um diese Daten zu verwalten.
Der Router arbeitet mit dem vom Expander gelieferten Netz und modelliert darauf eine echte Fahrtstrecke, indem es die Kostenparameter dynamisch vom Kosten-Modul erfragt.

Abbildung 12: Komponenten der Software

5.1.1 Regelwerk

Die Bestimmung der Kosten, insbesondere die zeitliche Dauer einzelner Kanten erweist sich als problematisch: Prinzipiell sollen die Kosten möglichst exakt bestimmt werden, wobei allerdings die exakten Fährpläne, aus denen sich diese Kosten ergeben, im Rahmen dieser Arbeit nicht digital vorliegen. Daher liegt eine Berechnung mit möglichst exakten Näherungswerten nahe. Für die Theorie sollten diese Daten jedoch generell soweit ergänzt werden können, bis auch der exakte Fahrplan abgebildet werden kann.

Daher wird als Kompromisslösung folgendes Prinzip gewählt: Generell werden die Zeit-Kosten für Kanten (Umsteigezeiten, Wartezeiten auf Anschlussverbindungen, Fahrzeiten, Wartezeiten an Stationen) mit statistisch ermittelten Näherungswerten ermittelt. Liegen jedoch exaktere Daten vor, sollen diese verwendet werden.
Das System muss also mehrere mögliche Kosten für einzelne Kanten verwalten und stets diejenigen Kosten anwenden, die exakter sind als alle anderen. Für diese Verwaltung kann das Prinzip der Kaskaden verwendet werden, so wie es etwa bei Cascading Style Sheets (CSS) verwendet wird: Hierbei können für ein Objekt mehrere (widersprüchliche) Regeln spezifiziert werden und CSS entscheidet anhand mehrerer Regeleigenschaften, welche angewendet werden soll – etwa Regel-Autor, Spezifizität der Regel (trifft sie eine allgemeine Aussage oder gilt sie nur für wenige exakt bestimmte Objekte) und die Reihenfolge, in der die Regeln spezifiziert wurden (Bos, Çelik, Hickson, & Lie, Assigning property values, Cascading, and Inheritance, 2009).

5.1.1.1 Ermittlung von geeigneten Näherungswerten

Für jedes Verkehrsmittel wurden einige ausgewählte Linien genauer untersucht, um realistische Näherungswerte für die Zeit-Kosten einer Fahrtstrecke zu ermitteln. Für jede der untersuchten Linien wurde zunächst aus einem Fahrplan die Gesamtzeit t ermittelt, welche benötigt wird, um von einer Endstation zur anderen zu fahren. In Abhängigkeit von der zur Linie gehörenden Stationsanzahl s und einer durchschnittlichen Haltedauer pro Station h (geschätzt) steht die Gesamthaltezeit g_h. Die daraus ermittelbare Gesamtfahrzeit g_f wird nun auf alle Fahrtstrecken verteilt und er ergibt sich die durchschnittliche Fahrzeit f von einer Station zur nächsten:

Aus diesen Daten ergeben sich für die verschiedenen Verkehrsmittel brauchbare Näherungswerte, siehe Tabelle 4. Aus der Wertemenge ausbrechende Linien wurden nicht zur Durchschnittsermittlung herangezogen, da diese später sowieso als Spezialfall behandelt werden.

Verkehrsmittel:	Angenommene Haltezeit an Station (Minuten):	Ermittelte durchschnittliche Fahrzeit zwischen zwei Stationen (Minuten):
S-Bahn	0,5	2,21
U-Bahn	0,25	1,20
Tram	0,2	1,09
Bus	0,2	1,25

Tabelle 4: Ermittelte Durchschnittszeiten für verschiedene Verkehrsmittel

5.1.1.2 Takte und Abfahrtszeiten

Viele Verkehrssysteme verwenden einen Taktfahrplan, bei dem die Intervalle zwischen zwei Fahrzeugen einer Linie konstant sind, sodass man dann umgangssprachlich von beispielsweise einem »20-Minuten-Takt« sprechen kann. Modelliert man tatsächlich den kompletten Fahrplan nach, kann man das Taktsystem unberücksichtigt lassen – in diesem Fall ist es jedoch sehr hilfreich, wenn keine genauen Fahrplandaten vorliegen. Durch das Taktsystem kann nämlich abgeschätzt werden, wie lange man an einer Station auf das nächste Fahrzeug einer Linie warten muss – der Mittelwert ist hier die halbe Taktzeit. Dadurch erhält man einen ungefähren Wert für die voraussichtliche Wartezeit auf eine Anschlussverbindung – wobei sich auch hier Probleme ergeben:

Gezielt abgestimmte Anschlussverbindungen bleiben unberücksichtigt. An manchen Stationen halten Fahrzeuge einzelner Linien gleichzeitig, um einen garantierten, schnellen Übergang zu ermöglichen, etwa an der U-Bahn-Station Innsbrucker Ring.
Obwohl eine Linie zwar sowohl in Hin- als auch in Rückrichtung im gleichen Takt fahren mag, müssen die Abfahrtszeiten an den einzelnen Stationen jedoch nicht identisch sein. Diese Problematik besteht jedoch in der Implementierung durch den in Kapitel 4.3.3 getroffenen Kompromiss sowieso nicht mehr.
Taktzeiten sind in der Realität variabel und hängen sowohl vom Ort als auch von der Tageszeit und dem Wochentag ab. Insbesondere bei S-Bahnen werden die entferntesten Stationen auf den Außenästen in einem größeren Takt bedient. Dies liegt daran, dass auf den städtischeren Streckenabschnitten Verstärkerzüge eingesetzt werden, die schon vor der Endstation wenden. Dadurch wird auf den inneren Streckenabschnitten ein höherer Takt erzeugt. Zudem verkehren Fahrzeuge im Berufsverkehr in einem kürzeren, am Wochenende zumeist in einem längeren Takt.

Da der Takt in der Implementierung sowieso nur als Hilfsmittel genutzt wird, wird pro Linie nur ein einziger Takt angenommen – meist derjenige, der tagsüber gilt. Der Takt wird ebenfalls über das Regelsystem eingegeben und verwaltet.

5.1.1.3 Regelsprache

Die Regelsprache, mit der Daten in das Regelwerk eingegeben werden, orientiert sich stark an CSS: Eine Regel besteht aus einem Selektor sowie mehreren Eigenschaften (SELFHTML e.V., 2007). Dabei wird definiert, dass beliebig viele Regeln hintereinander formuliert werden können. Als Syntax für eine Regel wird folgendes Format gewählt:


				[Selektor ]+{

				    [Eigenschaft: Wert;]*

				}

5.1.1.3.1 Selektoren

Als Selektor kann entweder eine Linie oder ein Verkehrsmittel dienen (genau genommen die numerische ID davon, die nicht zwangsläufig mit der Zahl, mit der die Linie in der Realität benannt wurde, übereinstimmen muss). Um zu unterscheiden, ob es sich bei einem Selektor um eine Linie oder ein Verkehrsmittel handelt, wird der ID von Verkehrsmitteln ein »m« vorangestellt. Soll der danach definierte Eigenschaftenblock gleichzeitig für mehrere Linien oder Verkehrsmittel gelten, können auch mehrere Selektoren durch Whitespace getrennt hintereinander geschrieben. Dies ist ein Unterschied zu CSS, wo Selektoren durch Kommas getrennt werden und Whitespace die Descendant-Achse an- spricht (Bos, Çelik, Hickson, & Lie, Selectors, 2009).

Die Selektivität der Selektoren kann aufgrund ihrer einfachen Struktur schnell ermittelt werden. Linienselektoren haben eine höhere Gewichtung als Verkehrsmittelselektoren; bei gleicher Gewichtung gilt die in der Dokumentordnung weiter hinten stehende Regel.

5.1.1.3.2 Eigenschaften

Im Eigenschaftenblock können den von den Selektoren ausgewählten Objekten verschiedene Eigenschaften zugewiesen werden. Für die gegenwärtige Implementierung sind folgende Eigenschaften vorgesehen:

Eigenschaft:	Bedeutung:	Wertemenge:	Eigenschaft anwendbar auf:
time-segment	Fahrzeit für die Strecke zwischen zwei Stationen	(float oder int) ≥ 0 Zeit in Minuten	Linien Verkehrsmittel
time-station	Haltezeit an einer Station	(float oder int) ≥ 0 Zeit in Minuten	Linien Verkehrsmittel
time-cycle	Taktzeit	(float oder int) ≥ 0 Zeit in Minuten	Linien Verkehrsmittel

5.1.1.3.3 Kommentare

Ebenso lassen sich Kommentare für interne Notizen einfügen. Diese werden mit einer besonderen Zeichensequenz eingeleitet und markieren alle nachfolgenden Zeichen bis zum Zeilenende als Kommentar:


				// Einstellungen für Metro-Bus 50

				33 {

				    time-cycle: 10;	// Linie hat eine Taktzeit von zehn Minuten

				    time-segment: 1.66;

				}

5.1.1.3.4 Erweiterungen

Prinzipiell lässt sich das Regelsystem noch erweitern, sodass ein exakter Fahrplan modelliert werden kann. Dazu ist es nötig, auch Eigenschaften für Stationen und Routensegmente definieren zu können. Man kann allerdings auf die Angabe von Abfahrts- und Ankunftszeiten verzichten, da sich diese Informationen in Wartezeiten kodieren lassen – etwa beim Umsteigen von einer Linie in eine andere. Dann können jedoch diejenigen Zeitfenster, bei denen sich die Taktzeit ändert, nicht modelliert werden.

5.1.1.4 Daten für Regelwerk

Mit den in 5.1.1.1 gewonnen Daten wurde ein Datensatz erstellt, welcher für die praktische Implementierung verwendet wurde.

5.1.1.5 Unterscheidung Regelwerk und Datenbank

Theoretisch wäre es denkbar, das Regelwerk zusammen mit den Netzinformationen in der Datenbank zu speichern. Allerdings ist es sinnvoller, das Regelwerk als selbstständiges, von der Datenbank unabhängiges Modul zu betrachten:

In der Datenbank werden im Anwendungsfall nur statische Informationen vorgehalten, die sich nur selten ändern, wie etwa die Lage von Stationen.
Alle von der Datenbank bezogenen Informationen können für mehrere Routenberechnungen zwischengespeichert werden, wie etwa das expandierte Netz, sodass die Gesamtzahl der Anfragen minimiert werden kann (vergleiche Kapitel 4.1).
Das Regelwerk hingegen ist (im theoretischen Fall) anfragespezifisch: Ein gehbehinderter Benutzer könnte etwa die Regeln dahingehend anpassen, dass Umsteigevorgänge für ihn erheblich länger dauern würden oder es kann je nach Tageszeit entweder der Tag- oder der Nachtfahrplan in das Regelwerk geladen werden.

Während die Informationen in der Datenbank also statische Zustände der Realität abbilden, enthält das Regelwerk dynamische Faktoren, welche vom Fahrplan (betrifft primär die Fahrtzeiten) und vom agierenden Benutzer (betrifft primär die Umsteigezeiten) abhängen.

5.1.2 Router

Als Routenkriterium wird der schnellste Weg gewählt. Als Alternativen würden sich allerdings ebenfalls der kürzeste oder der billigste (im Bezug auf die Fahrkartenpreise) Weg anbieten. Es existiert jedoch keine Funktion, die die Geo-Koordinaten einer Station auf eine Tarifzone abbilden kann, um die Fahrtkosten zu ermitteln. Diese Daten müssten erst noch ergänzt werden, um tatsächliche finanzielle Kosten ermitteln zu können. Der kürzeste Weg scheidet aufgrund seiner Praxisferne als Kriterium aus, da bei der Benutzung von öffentlichen Verkehrsmitteln die Kosten nur anhand der Parameter Start- und Ziel (sowie gegebenenfalls noch dem Fahrtzeitraum) bestimmt werden. Für den Fahrgast treten keine höheren Kosten auf, wenn er eine etwas längere Strecke wählt – etwa im Gegensatz zum Taxi, wo der Fahrpreis tatsächlich von der gefahrenen Strecke abhängt. Deswegen ist eine Orientierung an der schnellsten Verbindung am praxisrelevantesten.

Für eine effiziente Routenberechnung wird ein A*-Algorithmus verwendet. Da dieser eine Heuristik benötigt, um abschätzen zu können, welcher Knoten vermutlich am schnellsten zum Ziel führt (Patel, 2010), muss für jeden Knoten des expandierten Netzes abgeschätzt werden, wie viel Zeit von diesem bis zum Ziel im besten Fall benötigt wird. Da der Längen- und Breitengrad jeder Station bekannt ist (Kapitel 3.2), kann die Luftlinie zum Ziel berechnet werden. Es wird angenommen, dass kein Verkehrsmittel schneller als 150km/h fährt – wodurch eine geeignete untere Grenze für die Abschätzung der noch benötigten Zeit um Ziel gefunden werden kann.
Diese Abschätzung gilt derzeit nur für Stationen – dieser Wert wird nun für alle Knoten dieser Station (Eingangs-, Ausgangs-, Start- und Ziel-, eventuell Intermediateknoten, vgl. 4.2) übertragen. Man könnte die Abschätzung noch genauer differenzieren, indem man sie etwa für Eingangsknoten etwas höher schätzt als für Ausgangsknoten, was jedoch im Falle der Zielstation zu Problemen führt, da die exakte Distanz von allen Eingangsknoten zum Zielknoten mit 0 angegeben ist – und die Abschätzung in jedem Fall darunter liegen muss. Da Stationen aber sowieso immer nur in eine Richtung, nämlich von den Eingangs- zu den Ausgangsknoten, kann diese mögliche Verfeinerung vernachlässigt werden.

Da der A*-Algorithmus oft denjenigen Knoten benötigt, dessen geschätzte Entfernung zum Ziel am geringsten ist, ist es sinnvoll, die Knoten in einer speziellen Datenstruktur zu speichern, die diesen Aspekt berücksichtigt. Dazu bietet sich ein Min-Heap an, bei welchem die Suche nach dem Knoten mit der kleinsten Abschätzung in konstanter Zeit erfolgen kann (Atkinson, Sack, N., & Strothotte, 1986). Daher wurde ein solcher Heap nach Lester (Using Binary Heaps in A* Pathfinding, 2003) in PHP implementiert.

5.1.3 Frontend

Die Schnittstelle zur Kommunikation mit dem Benutzer ist als Web-Service angelegt und bietet in gewohnter Weise eine Eingabemöglichkeit für Start- und Ziel sowie eine Ausgabe der entsprechenden Ergebnisse.

Das Frontend unterstützt den Benutzer bei der Dateneingabe, indem es ihm Vorschläge für passende Stationen liefert, ohne dass dieser seine Eingabe zu Ende tippen muss. Durch die Auswahl eines der Vorschläge wird gleichzeitig im Hintergrund der Eingabe-Name auf die ID der Station abgebildet.

Abbildung 13: Eingabemaske für Start- und Ziel-Station mit Wortvervollständigung

Die Liste der möglichen Vorschläge wird dabei nach folgenden Kriterien geordnet:

Enthält der Name der Station nicht den eingegebenen Text, verwerfe sie
Die Liste wird in zwei Mengen geteilt: Stationen, die mit diesem Text beginnen (1) und solche, welche das Fragment an anderer Stelle in ihrem Namen beinhalten (2)
(1) und (2) werden jeweils nach der Länge der Zeichen im Namen der Station sortiert
(2) wird an das Ende von (1) angehängt, das Resultat ist die Liste der Vorschläge

Die Berechnete Route wird dann grafisch aufbereitet ausgeliefert, Linien werden mit Richtungsinformationen versehen und Umsteigevorgänge deutlich hervorgehoben. Zusätzlich besteht die Möglichkeit, den Streckenverlauf auf einer Karte anzeigen zu lassen.

Abbildung 14: Ausgabe der berechneten Route

5.2 Kritische Betrachtung der Routing-Ergebnisse

Die auf diese Weise ermittelten Strecken weisen einige Besonderheiten auf, welche im nachfolgenden Betrachtet werden sollen.

5.2.1 Optimalitätsprinzip

Da der Dijkstra-Algorithmus, beziehungsweise seine verallgemeinerte Form, der A*-Algorithmus (Krumke & Noltemeier, 2009, S. 181), in einem Graphen mit positiven Kantengewichten immer einen Kürzesten-Wege-Baum zu allen vom Start aus erreichbaren Knoten berechnet (Büsing, 2010, S. 154), kann man das für den Baum geltende Optimalitätskriterium auf die gefundene Route anwenden. Dies bedeutet, dass Teilstücke einer optimalen Route selbst wiederum optimale Routen sind.

Man mag nun verleitet sein, dieses Kriterium auf die berechneten Routen des Verkehrsnetzes anzuwenden: Betrachtet werden soll exemplarisch die Route vom Hauptbahnhof nach Daglfing. Das System errechnet nun, dass die beste Verbindung über die S8 hergestellt wird, deren Route über den Ostbahnhof führt. Unter Berufung auf das Optimalitätskriterium könnte man nun behaupten, dass die S8 ebenfalls die beste Verbindung zwischen Hauptbahnhof und Ostbahnhof, einer Teilstrecke der Verbindung Hauptbahnhof – Ostbahnhof, herstellt. Dies ist jedoch nicht der Fall, das System errechnet für diese Start- und Zielstation die U5 als beste Verbindung (siehe Abbildung 15).

Abbildung 15: Vereinfachter Ausschnitt aus dem Linienplan. Die S8 (schwarz) bietet die beste Verbindung vom Hauptbahnhof nach Daglfing, die U5 (oliv) jedoch vom Hauptbahnhof zum Ostbahnhof

Um diese augenscheinliche Verletzung des Optimalitätskriteriums aufzuklären, muss die Aussage »Verbindung Hauptbahnhof – Ostbahnhof ist Teilstrecke von Hauptbahnhof – Daglfing« genauer untersucht werden. Da in Kapitel 4 die Stationen zu Sub-Netzen expandiert wurden, existieren streng genommen keine Kanten Hauptbahnhof, Ostbahnhof und Daglfing mehr im Graphen. Stattdessen wurden die Ein- und Ausgangsknoten eingefügt.
Deshalb führt die Route der S8 im Beispiel genau betrachtet über die Knoten Hauptbahnhof-Start, Hauptbahnhof-Ausgang-S8, ..., Ostbahnhof-Eingang-S8, Ostbahnhof-Ausgang-S8, ..., Daglfing-Eingang-S8 und Daglfing-Ende. Die Verbindung Hauptbahnhof – Ostbahnhof muss dagegen am Knoten Hauptbahnhof-Start beginnen und am Knoten Ostbahnhof-Ende enden. Der Knoten Ostbahnhof-Ende ist allerdings überhaupt nicht in der Route der S8 nach Daglfing enthalten (vergleiche Kapitel 4.1), somit kann die Verbindung Hauptbahnhof – Ostbahnhof auch keine Teilstrecke von Hauptbahnhof – Daglfing sein (wie in Kapitel 4.1 erläutert, wird bei der Route nach Daglfing auch überhaupt kein Knoten Ostbahnhof-Ende angelegt). Daher kann hier eine andere Linie (hier: U5) eine bessere Verbindung herstellen.

5.2.2 Fahrtrichtung

Vertauscht man Start- und Zielstation, um eine Route für die Rückfahrt zu bekommen, kann diese von der Hinfahrt abweichen: Sie kann länger oder kürzer dauern als die Hinfahrt oder sogar eine gänzlich andere Streckenführung haben.
So berechnet das System die Kosten für die Strecke Ramersdorf – Holzwiesenstraße mit 20 Minuten, für die Rückfahrt (also von der Holzwiesenstraße nach Ramersdorf) werden die Kosten jedoch mit 15 Minuten angegeben.
Für die Verbindung vom Rosenheimer Platz zum Kustermannpark werden je nach Fahrtrichtung sogar unterschiedliche Fahrtstrecken angegeben: In Richtung Rosenheimer Platz in 16 Minuten mit Bus 55 zum Ostbahnhof, weiter mit Tram 19 zur Wörthstraße und ab dort mit der Tram 25 ans Ziel. In Gegenrichtung soll hingegen die S2 zum Ostbahnhof und dann der Bus 55 genommen werden, berechnete Zeit sind hier 12 Minuten. Abbildung 16 visualisiert die unterschiedlichen Fahrtstrecken:

Abbildung 16: Unterschiedliche Streckenwahl je nach Fahrtrichtung zwischen Rosenheimer Platz und Kustermannpark

Da die Fahrtzeiten für Streckenabschnitte unabhängig von der Fahrtrichtung sind, ist die Ursache für dieses Verhalten in den Sub-Netzen der Stationen zu finden: Beim Umsteigevorgang muss auf das nächste Anschlussfahrzeug gewartet werden, diese Wartezeit wird intern als halbe Taktzeit abgeschätzt (vergleiche Kapitel 5.1.1.2). Zusätzlich wird die Wartezeit, die unter Umständen am Beginn der Reise entstehen kann, nicht zu den Kosten hinzugezählt, da viele Menschen diese Zeit noch nutzen und erst pünktlich zur Station gehen. Somit besteht das Problem immer dann, wenn von einer Linie in eine andere mit unterschiedlicher Taktzeit umgestiegen wird. Fällt diese Zeitdifferenz zwischen beiden Richtungen zu gravierend aus, wählt das System dann eine alternative Streckenführung, die in einer der Richtungen dann schneller zum Ziel führt.

5.2.3 Vergleich mit Real-Daten

Da die Implementierung mangels Datengrundlage viel mit geschätzten Werten anstelle von echten Fahrplandaten arbeitet, bietet sich ein Vergleich mit den tatsächlichen Fahrtzeiten an, um die Qualität dieser Implementierung einordnen zu können.

Die tatsächlichen Fahrtzeiten wurden über die Website des MVV Münchens ermittelt, es wurden Fahrzeiten tagsüber gewählt. Da die Fahrtauskunft des MVV auch längere Fußwege berücksichtigt, etwa um zu Fuß zwischen zwei unterschiedlichen Stationen zu wechseln, wurden nur solche Ergebnisse herangezogen, deren Linienverlauf ohne diese Wege auskommt und der daher auch mit dem von diesem Algorithmus übereinstimmt. Ebenso wurden Routen verworfen, welche auf Linien zurückgreifen, die in der Datengrundlage dieser Implementierung nicht vorhanden sind (etwa Buslinien außerhalb des Stadtgebiets von München oder Regionalexpress).

Start	Ziel	Umstei- gevor- gänge	Berech- nete Fahrt- zeit	Tatsäch- liche Fahrtzeit	Abwei- chung	Absolute Abwei- chung in Relation zur tatsäch- lichen Fahrtzeit
Bayerischer Rundfunk	Hofbräuallee	4	68 Min.	64 Min.	+4 Min.	6,3%
Südpark	Pinakotheken	2	35 Min.	32 Min.	+3 Min.	9,4%
Abtstraße	Gauting	2	66 Min.	54 Min.	+12 Min.	22,2%
Tivolistraße	Pinakotheken	1	16 Min.	15 Min.	+1 Min.	6,7%
Schöngeising	Herrsching	1	59 Min.	71 Min.	-12 Min.	16,9%
Dürrnhaar	Messestadt West	1	40 Min.	41 Min.	-1 Min.	2,4%
Altomünster	Neuperlach Zentrum	2	97 Min.	92 Min.	+5 Min.	5,4%
Bachern	Petershausen	1	30 Min.	32 Min.	-2 Min.	6,3%
Kreuzstraße	Flughafen München	1	73 Min.	71 Min.	+2 Min.	2,8%
Olympiazentrum	Hasenbergl Süd	1	18 Min.	22 Min.	-4 Min.	18,2%
Bonner Platz	Brudermühlstraße	0	15 Min.	15 Min.	±0 Min.	0,0%
Heimeranplatz	Am Hart	1	22 Min.	18 Min.	+4 Min.	22,2%
Feldafing	Kranzberger Allee (Dirnismaning)	2	90 Min.	91 Min.	-1 Min.	1,1%
Erding	Olympiaeinkaufs- zentrum Ost	2	82 Min.	82 Min.	±0 Min.	0,0%
Karlsfeld	Universität	1	38 Min.	32 Min.	+6 Min.	18,8%
Königinstraße	Thalkirchen (Tierpark)	1	21 Min.	29 Min.	-8 Min.	27,6%
Authariplatz	Krautheimstraße	2	56 Min.	48 Min.	+8 Min.	16,7%

Obwohl diese Auswahl an potentiellen Verbindungsmöglichkeiten nicht vollständig oder besonders repräsentativ ist, lässt sich eine grobe Tendenz erkennen, bei der die auf Näherungswerten basierenden Kosten nur im Bereich von ±30% von den tatsächlichen Kosten abweichen. Vergleicht man den Münchner Fahrplan mit dem anderer Verkehrssysteme wie etwa dem der Schweiz, wo auf das Prinzip der Taktminute zurückgegriffen wird, so könnten noch bessere Ergebnisse erzielt werden. Bei der Verwendung von Taktminuten verlassen im Idealfall alle Züge eine Station gleichzeitig, die Wartezeiten auf Anschlussverbindungen sind somit einheitlich und lassen sich berechnen. Die Taktminuten sind dabei explizit verfügbar (SMA und Partner AG, 2008).

6 Zusammenfassung

Diese Arbeit hat gezeigt, wie beim Routing durch heterogene Netze vorgegangen werden muss: Der Großteil des Anstrengungen muss für die Transitknoten aufgewendet werden, welche Verbindungen zwischen den einzelnen homogenen Netzen herstellen. Die Subnetz-Expansion ist dabei ein allgemeiner Ansatz, welcher diesen Wechsel in alle Richtungen ermöglicht, wobei auch durch Verwendung von Intermediate-Knoten ein spezieller Weg für die üblicherweise im öffentlichen Nahverkehr gegeben Verhältnisse gezeigt wurde.

Um ein Routing nach Kostenkriterien in einem heterogenen Netzwerk durchführen zu können, sind mehr Informationen nötig, als dies bei einem homogenen der Fall ist. Transitvorgänge beanspruchen einen erheblichen Anteil an den Gesamtkosten und sollten möglichst exakt bestimmt werden, wobei gezeigt wurde, dass hier bereits eine gute Abschätzung Ergebnisse liefert, die nahe den in der Realität vorliegenden Bedingungen liegt.

Der Routing-Mechanismus kann zukünftig noch verbessert werden, indem neben der Zeit als Kostenkriterium auch weitere andere wie die Anzahl der Umsteigevorgänge berücksichtigt werden. Dazu bieten sich Skyline-Anfragen an, welche anstelle einer einzigen Route eine Menge an Ergebnissen zurückliefern, wobei jedes für eine Kostenparameterkonstellation ideal ist. Die Komplexität des hier betrachteten Netzes liegt mit 10715 Kanten und 4040 Knoten (vgl. Tabelle 2) auch in der Größenordnung des für Skyline-Berechnungen herangezogenen Benchmarks Oldenburg, welcher aus 7036 Kanten und 6105 Knoten besteht (Kriegel, Renz, & Schubert, 2010).

Ferner kann das Netz noch um andere Verkehrsmittel wie Fußwege oder Radwege ergänzt werden. Hier können dann auch Beschränkungen auftreten, die während der Routenberechnung berücksichtigt werden müssen: Ist die Fahrradmitnahme im Bus beispielsweise untersagt, so stehen am Ende der Busreise keine Fahrradwege mehr im Netz zur Verfügung.

Literaturverzeichnis

Atkinson, M. D., Sack, J.-R., N., S., & Strothotte, T. (Oktober 1986). Min-Max Heaps and Generalized Priority Queues. Communications of the ACM , S. 996-1000.

Bos, B., Çelik, T., Hickson, I., & Lie, H. W. (8. September 2009). Assigning property values, Cascading, and Inheritance. Abgerufen am 27. Mai 2010 von World Wide Web Consortium: http://www.w3.org/TR/CSS21/cascade.html

Bos, B., Çelik, T., Hickson, I., & Lie, H. W. (8. September 2009). Selectors. Abgerufen am 27. Mai 2010 von World Wide Web Consortium: http://www.w3.org/TR/CSS21/selector.html

Büsing, C. (2010). Graphen- und Netzwerkoptimierung. Heidelberg: Spektrum Akademischer Verlag.

Dijkstra, E. W. (1959). Two Problems in Connexion with Graphs. In Numerische Mathematik (S. 269-271).

Kriegel, H.-P., Renz, M., & Schubert, M. (2010). Route Skyline Queries: A Multi-Preference Path Planning Approach. 26th Int. Conf. on Data Engineering.

Krumke, S. O., & Noltemeier, H. (2009). Graphentheoretische Konzepte und Algorithmen. Wiesbaden: Vieweg + Teubner.

Lester, P. (11. April 2003). Using Binary Heaps in A* Pathfinding. Abgerufen am 2. Juli 2010 von Almanac of Policy Issues: http://www.policyalmanac.org/games/binaryHeaps.htm

MVV. (17. Mai 2010). Über uns. Abgerufen am 17. Mai 2010 von Münchner Verkehrs- und Tarifverbund: http://mvv-muenchen.de/de/home/dermvv/unternehmen/ueber_uns/index.html

MVV. (17. Mai 2010). Verkehrsunternehmen. Abgerufen am 17. Mai 2010 von Münchner Verkehrs- und Tarifverbund: http://mvv- muenchen.de/de/home/dermvv/unternehmen/verkehrsunternehmen/index.html

Patel, A. (16. Februar 2010). Game Programming. Abgerufen am 14. Juni 2010 von Stanford: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

SELFHTML e.V. (1. März 2007). Stylesheets und HTML. Abgerufen am 27. Mai 2010 von SELFHTML: http://de.selfhtml.org/css/intro.htm

SMA und Partner AG. (5. November 2008). Netzgrafik - Fahrplan Schweiz 2009. Abgerufen am 24. Juni 2010 von SMA: http://www.sma-partner.ch/index.php?option=com_rokdownloads&task=download&id=66%3Ang_ch_2009&Itemid= 154&lang=de

mixabit.com