Nicht in jedem Stadtbahnnetz ist Robustheit als Optimierungskriterium für Fahrpläne gleichsam geeignet. Im Rahmen dieses Beitrags werden deshalb Faktoren für die Netzstruktur bestimmt, die die Wirksamkeit von Robustheit als verspätungsmindernden Faktor beeinflussen. Anhand von Optimierungs- und  Simulationsexperimenten auf Basis von Modellen der Stadtbahnnetze von Köln und Montpellier werden die definierten Einflussfaktoren getestet.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einführung

Bei der angebotsorientierten Optimierung von Fahrplänen für Stadtbahnnetze existieren viele valide Zielgrößen, wie z. B. der Erhalt von Umsteigeverbindungen oder die Minimierung von Wartezeiten der Passagiere. Dazu gehört als häufig verwendetes Ziel auch die Robustheit als Maß für die Widerstandsfähigkeit eines Fahrplans gegenüber kleinen, im täglichen Betrieb unvermeidlich auftretenden Störungen.

In diesem Artikel wollen wir untersuchen, welche Voraussetzungen gelten müssen, damit ein robuster Fahrplan zur Reduktion von Verspätungen in einem Stadtbahnnetz beitragen kann. Wir stellen dazu eine Methode zur Erzeugung robuster Fahrpläne vor, die auch verkehrsplanerische Vorgaben berücksichtigt, wie sie aus ökonomischen, politischen und rechtlichen Überlegungen erwachsen. Anschließend formulieren wir einige Bedingungen an die Netzstruktur, die erfüllt sein müssen, damit Robustheit als Optimierungsziel verspätungsreduzierend wirkt. Schließlich prüfen wir unsere Annahmen anhand zweier Modelle real existierender Stadtbahnnetze, indem wir robuste Fahrpläne für diese Netze erzeugen und mittels einer Simulationsanwendung deren Einfluss auf die entstehenden Verspätungen untersuchen.

Dazu schildern wir zuerst einige Hintergründe zu robusten Stadtbahnfahrplänen und zeigen eine Möglichkeit zu deren Generierung (Abschnitt 2). Danach stellen wir einige Überlegungen zur Wirksamkeit von Robustheit als Mittel zur Reduktion von Verspätungen im Stadtbahnverkehr vor (Abschnitt 3). Um diese Überlegungen zu prüfen wird eine Reihe von Experimenten durchgeführt, in denen robuste und nicht-robuste Fahrpläne für die Stadtbahnnetze der Städte Köln und Montpellier generiert werden. Die Fahrpläne werden anschließend simuliert, und die resultierenden Verspätungswerte verglichen (Abschnitt 4). Der Artikel endet mit einer kurzen Zusammenfassung des Erreichten und einem Ausblick auf die weitere Forschung (Abschnitt 5).

2 Hintergrund

2.1 Robuste Stadtbahnfahrpläne

Für die Generierung und Bewertung von periodischen Fahrplänen existieren eine Reihe von Ansätzen. Dazu gehören u.a. die von Bampas, et al. in [1], Cacchiana, Caprara und Fischetti in [3], Caimi, et al. in [4], Genç in [7], Ginkel und Schöbel in [8], Schöbel in [16], Speckenmeyer, et al. in [17], Suhl und Mellouli in [18] und Ullrich, et al. in [28] beschriebenen Verfahren. Die erwähnten Ansätze optimieren dabei hinsichtlich verschiedener allgemeiner Zielgrößen, wie zum Beispiel der Fahrzeugverspätung (siehe [16] und [18]), der verpassten Umsteigeverbindungen kombiniert mit der Fahrzeugverspätung (siehe [8]), sozialer Opportunitätskosten und operativer Kosten (siehe [17]), Robustheit und Gewinnausrichtung (siehe [3]) oder hinsichtlich der Maximierung der Robustheit (siehe [1], [4], [7] und [28]). Die für die praktische Einsetzbarkeit der Fahrpläne wichtigen planerischen Vorgaben, wie die Erhaltung von Umsteigeverbindungen, Verstärkerfahrten in Innenstadtbereichen und die Koordinierung mit dem Fernverkehrsnetz, werden in der besprochenen Literatur jedoch nicht berücksichtigt.

Im Rahmen einer Verbesserung der Angebotsqualität kann die Zielgröße Robustheit herangezogen werden. Als Robustheit wird in diesem Kontext das Maß bezeichnet, zu dem die Abfahrten im Taktintervall gleichmäßig verteilt sind. Bei einem angenommenen ZehnMinuten-Takt lassen sich zwei Linien auf einem gemeinsamen Streckenabschnitt z.B. mit jeweils fünf Minuten planmäßigem Abstand zum nachfolgenden Fahrzeug versehen. Hier kann eines der beteiligten Fahrzeuge um mehr als vier Minuten verspätet sein, ohne dass die nachfolgenden Fahrten verzögert werden. Bei einer extrem ungleichmäßigen Aufteilung in Abstände von neun Minuten und einer Minute kann das eine Fahrzeug zwar mehr als acht Minuten Verspätung haben, ohne dass es zu weiteren Konsequenzen kommt, das andere Fahrzeug jedoch überträgt schon eine kleine Verspätung ab einer Minute auf die folgenden Bahnen. Da im Folgenden von typischerweise kleinen Störungen ausgegangen wird, wird die gleichmäßige Aufteilung der zur Verfügung stehenden Zeitpuffer in möglichst hohe Abstände als sehr robust, das Auftreten von sehr kleinen Abständen als nicht robust angesehen.

Die Berücksichtigung der Robustheit als Zielgröße erzeugt einen Fahrplan, der optimal an die vorhandenen Netzstrukturen angepasst ist, während viele andere bekannte Kriterien den Fahrplan auf Vorgaben von außen, also von Anbietern oder Passagieren anpassen. Dabei muss, um für ein gegebenes Netz eine möglichst hohe Robustheit zu erreichen, ein komplexes kombinatorisches Optimierungsproblem gelöst werden.

2.2 Generierung robuster Stadtbahnfahrpläne

Im Folgenden wird deshalb ein Ansatz beschrieben, der heuristische und exakte Methoden kombiniert um optimale Taktfahrpläne zu generieren, die sowohl auf maximale Robustheit zielen als auch einer gegebenen Menge von verkehrsplanerischen Vorgaben entsprechen. Dabei werden Taktfahrpläne erstellt, die für alle Linien ein gemeinsames Taktintervall aufweisen. Durch die Möglichkeit zur freien Wahl des gemeinsamen Linientakts können, obwohl bei der Anwendung typischerweise die Hauptverkehrsperioden mit den kürzesten vorkommenden Takten betrachtet werden, auch Nebenverkehrsund Nachtverkehrsperioden untersucht werden.

Bild 1: Haltepunkte C, D und E werden zu Haltepunkttyp C' zusammengefasst, gewichtet mit

Für das Modell wird eine Linie als eine Menge von gerichteten Linienvarianten bis definiert. Wichtigstes Attribut einer Linienvariante ist die Linienroute eine geordnete Liste von zu bedienenden Haltepunkten. Eine Fahrt definiert das geplante Abfahren des Verlaufs einer Linienvariante ab einem festgelegten Startzeitpunkt , also.
Durch den Fahrplan wird schließlich jeder Fahrt ein Fahrzeug aus dem Fuhrpark zugeordnet.

Zur Berechnung der Robustheit eines Fahrplans wird für jeden Haltepunkt aus der Menge aller Haltepunkte der im Fahrplan vorgesehene Abstand zwischen jeder Fahrt und deren unmittelbarer Vorgängerin untersucht. ist also die Zeitdauer, die am untersuchten Haltepunkt zwischen der Abfahrt von und der Abfahrt von vergeht. Um kleine Sicherheitsabstände an hochfrequentierten Haltepunkten zu bestrafen, werden zur Berechnung der entsprechenden Komponente der Zielfunktion die Inversen der Sicherheitsabstände verwendet. Als Folge wächst dieser Teil der Zielfunktion umgekehrt proportional zur Robustheit des Fahrplans.

Um die Komplexität dieser immer wieder vorzunehmenden Berechnung zu reduzieren, wird wie von Genç in [7] beschrieben aus aufeinander folgenden, ausschließlich von denselben Linien befahrenen, Haltepunkten ein maximaler Haltepunkttyp h erstellt, der durch die An zahl der einbezogenen Haltepunkte gewichtet wird (siehe Abbildung 1). Die so reduzierte Menge der Haltepunkte wird durch beschrieben.

Formel (1) zeigt die aus diesen Überlegungen resultierende Zielfunktionskomponente eines Fahrplans .

Formel (1) siehe PDF.

Die verkehrsplanerischen Vorgaben sind gegeben als Menge. Um den Lösungskandidaten in Hinblick auf eine planerische Vorgabe bewerten zu können, wird ein von der Ausgestaltung des Fahrplans abhängiger Erfülltheitsgrad eingeführt. Die Werte bilden dabei absteigende Erfüllungsgrade ab, von 1 (komplett erfüllt) über zwei (gut) und drei (akzeptabel) bis zu (nicht erfüllt). Eine einzelne nicht erfüllte planerische Anforderung führt dazu, dass der Kandidat als ungültig zurück gewiesen wird. Zur Berechnung der Zielfunktionskomponente eines Fahrplans werden für alle die Erfüllungsgrade addiert (siehe Formel (2)).

Formel (2) siehe PDF.

Abhängig von der Größe des betrachteten Netzes und der Anzahl der zu beachtenden Vorgaben sind die beiden Bestandteile der Zielfunktion typischerweise nicht direkt miteinander vergleichbar. Daher wird ein Normalisierungsfaktor definiert, der das Verhältnis zwischen theoretisch optimalen Sicherheitsabständen und bestmöglicher Erfüllung aller abbildet.
Die optimalen Sicherheitsabstände zweier Fahrten und an Haltepunkttyp ergeben sich durch äquidistantes Aufteilen des zur Verfügung stehenden Zeitintervalls auf die den Haltepunkttyp bedienenden Linien. Der bestmögliche Erfüllungsgrad einer Anforderung entspricht unabhängig vom konkreten Fahrplan dem mi nimalen vom Planer vorgegebenen Wert, typischerweise ist das. Hierdurch ergibt sich also ein Normalisierungsfaktor wie in Formel (3) beschrieben.

Formel (3) siehe PDF.

Durch Kombination von und entsteht die durch den Faktor normalisierte Zielfunktion (siehe Formel (4)). Um eine Gewichtung der Bestandteile zu ermöglichen wird der Faktor als relatives Gewicht der Erfüllung der planerischen Bedingungen ein geführt.

Formel (4) siehe PDF.

Eine gültige Lösung hat außerdem einigen Nebenbedingungen (siehe Abbildung 2) zu gehorchen: Restriktion (i) bestimmt, dass jede erste Startzeit innerhalb des Taktintervalls, von 0 bis takt – 1 liegt. Restriktion (ii) gibt an, dass zwischen zwei Abfahrten und an jedem Haltepunkttyp mindestens eine Minute Zeit vergehen muss. Ein Haltepunkt darf also nicht gleichzeitig von zwei Fahrzeugen belegt werden, der Fahrplan muss kollisionsfrei sein.

Bild 2: Übersicht über das Optimierungsproblem

Um von Verkehrsplanern vorgetragene Ansprüche an einen Fahrplan berücksichtigen zu können, muss eine gewisse Formalisierung stattfinden. Die folgenden sieben Typen von Vorgaben an einen Fahrplan wurden identifiziert: Abstände zwischen Fahrten, festgesetzte Startzeiten, Verstärkerfahrten, eingleisige Streckenabschnitte, Wendezeiten, Umsteigeverbindungen und Rendezvous-Verbindungen.

Bei näherer Betrachtung (siehe Abschnitt 6.2.3 in [27]) wird klar, dass Abstandsund Startzeitvorgaben fundamental sind, und alle anderen Anspruchstypen durch eine Kombination von Vorgaben dieser beiden Typen abgebildet werden können. So lässt sich z.B. ein eingleisiger Streckenabschnitt durch zwei Abstandsvorgaben abbilden, die Mindestabstände für die Abfahrten an gegenüberliegenden Haltepunkten an den Enden des eingleisigen Streckenabschnitts definieren. Wir betrachten daher im Folgenden nur Abstandsund Startzeitvorgaben.

Das erläuterte Modell wurde als Branch-and-Bound-Solver (siehe [5]) implementiert, dem aus Performanzgründen ein Genetischer Algorithmus (siehe [6]) vorangestellt ist. Dem Branch-and-Bound-Algorithmus wird dabei die beste von der Heuristik gefundene Lösung als initiale obere Schranke übergeben, so dass ein Kaltstart verhindert wird und große Teile des Lösungsbaums schnell ausgeschlossen werden können. Eine lokale untere Schranke wird bestimmt, indem die Zielfunktionskomponenten für die bereits fixierten Linienvarianten berechnet und für noch nicht fixierte Varianten abgeschätzt werden. Die verbliebene Laufzeit wird gemäß [11] abgeschätzt. Weitere Details zur Modellierung werden in [28] und in den Abschnitten 6.2.4 und 6.2.5 von [27] geschildert.

3 Wirksamkeit robuster Stadtbahnfahrpläne

Die Wirksamkeit von Robustheit als Optimierungskriterium für Fahrpläne beruht auf einer Reihe von Grundsätzen: In einem robusten Fahrplan sind aufeinander folgende Fahrzeuge zeitlich entkoppelt, so dass sich kleinere, im Betriebsalltag unvermeidliche Verspätungen weniger stark auf Nachfolgefahrzeuge übertragen können. Dadurch sinkt die Gesamtzahl der verspäteten Abfahrten, da diese lokal auf das direkt betroffene Fahrzeug beschränkt bleiben und seltener globale Auswirkungen haben. Weiterhin sinkt insbesondere die Anzahl der als stark wahrgenommenen größeren Verspätungen (hier: mehr als 60 Sekunden), da sich weniger kleinere Verspätungen im Laufe des Betriebstags zu solchen größeren Verzögerungen akkumulieren können. Ein robuster Fahrplan kann also sowohl die Anzahl der verspäteten Abfahrten reduzieren als auch die durchschnittliche Höhe der Verspätungen.

Als willkommene Nebenwirkung ergibt sich durch die gleichmäßig zwischen den einzelnen Fahrten aufgeteilten Taktintervalle eine größere Zeitspanne für die Planung und Durchführung von ggf. nötigen Recovery-Maßnahmen (siehe [13]) in Folge größerer Störungen. Die Durchschnittslänge der zur Verfügung stehenden Zeitspannen bleibt zwar gleich (da die Anzahl der Abfahrten pro Taktintervall ebenfalls gleich bleibt), es ist aber anzunehmen, dass eine durch höhere Robustheit bewirkte Steigerung von z.B. einer auf zwei Minuten Reaktionszeit wertvoller ist als eine Steigerung von acht auf neun Minuten, dass also der Grenznutzen zusätzlicher Zeit für Recovery-Maßnahmen abnimmt.

Um Robustheit als Zielgröße für einen Stadtbahnfahrplan anwenden zu können, gilt die folgende Vorbedingung: Robuste Fahrpläne können nur da erzeugt werden, wo die Netzund Linienstruktur Freiheitsgrade für die Fahrplangestaltung zulässt. Sind keine Spielräume für den Optimierer vorhanden, ist die robuste Ausgestaltung von Fahrplänen nicht möglich. Insbesondere ergeben sich hier Schwierigkeiten, falls mehrere Linien einen Streckenabschnitt gemeinsam bedienen, sich dann trennen und nach Abschnitten mit unterschiedlichen Fahrzeiten wieder aufeinander treffen. Da der Optimierer nur gültige Fahrpläne erzeugen kann, die an jedem Haltepunkt zwischen zwei Abfahrten einen Mindestabstand von einer Minute vorsehen, reduziert sich der Spielraum für die Planung der betroffenen Linien unter Umständen stark. Wir bezeichnen die Linien dann als verklemmt (für ein Beispiel siehe Abschnitt 4.2).

Damit ein robuster Fahrplan die Anzahl und Höhe der Verspätungen wirksam reduzieren kann, muss das Stadtbahnnetz eine Reihe von Bedingungen einhalten:

Bedingung (a): Gemeinsame Ressourcennutzung. Durch Robustheit werden aufeinander folgende Fahrzeuge an gemeinsam genutzten Ressourcen zeitlich entkoppelt. Als Kriterium kann sie daher nur wirksam sein, wenn Ressourcen wie Gleisabschnitte und Haltepunkte von verschiedenen Linien gemeinsam genutzt werden, also eine Ressourcenkonkurrenz besteht. Existiert diese Konkurrenz nicht, so bestehen keine Abhängigkeiten, die durch einen robusten Fahrplan aufgelöst werden könnten; der Robustheitsgrad eines Fahrplans beeinflusst in diesem Fall die Pünktlichkeit nicht. Diejenigen Ressourcen, die am knappsten sind, profitieren am meisten von einer Entkopplung der Nutzung. Das sind typischerweise Cluster von Weichen im Umfeld zentraler Knotenpunkte, die von vielen Linien mit einer geringen Höchstgeschwindigkeit befahren werden.

Bedingung (b): Geringe Variabilität der Fahrzeiten. Der Robustheitsgrad eines Fahrplans ist ein statisches Planungskriterium. Er kann nur wirksam sein, wenn die Streuung der Fahrzeiten der einzelnen Bahnen auf einem Linienabschnitt klein genug ist, so dass die statische Planung nicht durch das dynamische Verhalten der Fahrzeuge zunichte gemacht wird (auch beschrieben in [26]).

Bedingung (c): Keine Redundanz der Netzressourcen. Im Fahrplan angelegte Robustheit wirkt nur dort, wo sich kleine Verspätungen auf nachfolgende Fahrzeuge auswirken und sich so durch das Netz fortpflanzen können. Falls das Folgefahrzeug durch redundante Netzressourcen die Möglichkeit hat, die verspätete Bahn zu überholen oder ihr auszuweichen, also dynamische, nicht in der Fahrtenplanung berücksichtigbare Entscheidungen getroffen werden, begrenzt dies die Verspätungswirksamkeit der Fahrpläne. Dies kann z.B. durch Überholen an Wendekreisen oder durch Ausweichen auf ein Parallelgleis auftreten.

In einem Stadtbahnnetz, das die Vorbedingung und die Bedingungen (a) bis (c) erfüllt, kann ein robuster Fahrplan dazu beitragen, die durchschnittlichen Verspätungen der Abfahrten zu reduzieren und so die Angebotsqualität zu erhöhen.

4 Experimente

Im Rahmen einiger Experimente auf Basis öffentlich zugänglicher Daten soll überprüft werden, ob der erhöhte Robustheitsgrad eines Fahrplans wie vermutet Auswirkungen auf die Pünktlichkeit hat. Wir betrachten dazu zuerst das Stadtbahnnetz der Kölner Verkehrsbetriebe AG (KVB) in Köln und vergleichen dessen Eigenschaften mit denen des deutlich kleineren, von der Transports de l’agglomération de Montpellier (TAM) betriebenen Tramway-Netzes der südfranzösischen Stadt Montpellier. Abschließend untersuchen wir welchen Einfluss die drei formulierten Bedingungen im Einzelnen haben.

Als Simulationswerkzeug für die Experimente dient die von den Autoren in [12] beschriebene, diskrete Simulationsanwendung.

4.1 Modellierung des KVB-Stadtbahnnetzes in Köln

Das von der KVB betriebene Kölner Stadtbahnnetz besteht aus 243 Stationen (bzw. 531 Haltepunkten) und 80 Weichen, die durch 586 Gleisabschnitte verbunden sind (siehe Abbildung 3). Zur Abdeckung des Netzes werden elf Linien mit 36 Linienrouten verwendet (für den Netzplan des Jahres 2012 siehe [10]). Die 178 im Einsatz befindlichen Fahrzeuge bedienen täglich ca. 2.800 Fahrten.

Dieses Netz erfüllt die Bedingungen (a) bis (c) aus Abschnitt 3 vollständig. In weiten Teilen des Kölner Netzes finden sich gegenseitige Abhängigkeiten verschiedener Linien durch gemeinsame Ressourcennutzung, die Bedingung (a) ist also erfüllt. Besonders hervorzuheben sind hier die Weichencluster an den zentralen Stationen Appellhofplatz, Barbarossaplatz und Ebertplatz. Da die Stadtbahn zu großen Teilen (insbesondere in der Innenstadt) unterirdisch verkehrt, also exklusiv fährt und an Stellen mit gemeinsamer Nutzung mit dem Individualverkehr meist Vorrang genießt, fällt die Variabilität der Fahrzeiten relativ gering aus, Bedingung (b) ist daher auch erfüllt. Bedingung (c) ist ebenfalls erfüllt: Im Stadtbahnnetz von Köln findet sich kaum Ressourcenredundanz. An wenigen Stellen, wie bspw. an den Stationen Neumarkt oder Moltkestraße, finden sich Wendekreise, die aber nicht für Überholvorgänge im laufenden Betrieb verwendet werden.

Bild 3: Stadtbahnnetz der KVB, Köln

Bild 4: KVB, Köln: Häufigkeiten aller Verspätungen

Um unsere Annahmen zu bestätigen verwenden wir das vorgestellte Optimierungsverfahren. Dazu generieren wir Fahrpläne mit dem in Köln üblichen globalen Taktintervall von 10 Minuten und definieren zusätzlich verkehrsplanerische Vorgaben für Wendezeiten und Verstärkerfahrten in der Innenstadt. Nach 500 Generationen mit einer Populationsgröße von 450 Individuen wird der Genetische Algorithmus gestoppt und der Branch-and-Bound-Solver mit dem bis dato besten Fitnesswert gestartet. Nach Abschluss der Optimierung erhalten wir so 1.281 Optimalfahrpläne mit einem Fitnesswert von 175,86. Zum Vergleich: Der durchschnittliche Fitnesswert der initialen Generation des Genetischen Algorithmus liegt bei 192,65 (schlechtester Wert: 200,92). Diese Verbesserung um 8,7 Prozent zeigt, dass die im letzten Abschnitt definierte Vorbedingung erfüllt ist, Robustheit in diesem Netz also offenbar eine gute Zielgröße zur Verbesserung der Pünktlichkeit darstellt.

Um diese Vermutung genauer zu überprüfen, verwenden wir die beschriebene Simulationssoftware. Dazu ziehen wir je zehn Fahrpläne aus den Gruppen der initialen und optimalen Pläne und führen jeweils zehn Simulationsläufe durch. Wir erhalten unter den initialen Fahrplänen einen Wert von 19,4 Sekunden für die durchschnittliche Verspätung aller Abfahrten. Unter den optimalen Fahrplänen reduziert sich dieser Wert um ca. 17,5 Prozent oder 3,4 Sekunden auf 16,0 Sekunden. Die mittlere Verspätung aller verspäteten Abfahrten kann von 36,8 um 5,3 Sekunden oder 14,4 Prozent auf 31,5 Sekunden reduziert werden.

Die Häufigkeitsverteilung der Verspätungen in Abbildung 4 und 5 zeigt wie erwartet, dass die Gesamtzahl der verspäteten Abfahrten und insbesondere die Anzahl der Abfahrten mit Verspätungen von über einer Minute reduziert werden können. Während die Gesamtzahl der verspäteten Abfahrten von 16.848,7 um 3,5 Prozent oder 596,0 Abfahrten auf 16.252,7 reduziert werden kann, kann die Anzahl der größeren Verspätungen von durchschnittlich 3.091,2 um 892,7 Abfahrten oder 28,9 Prozent auf 2.198,5 reduziert werden. Durch die erhöhte Robustheit bleiben also nicht nur kleinere Verspätungen lokal begrenzt, sondern es wird ebenfalls verhindert, dass sich kleine Verspätungen über den Verlauf eines Betriebstages zu größeren Verspätungen aufaddieren.

Bild 5: KVB, Köln: Häufigkeiten größerer Verspätungen

Für eine genauere Betrachtung ziehen wir nun je einen Fahrplan aus jedem Pool (Tabellen 1 und 2 zeigen hierfür die Startminuten im Taktintervall) heran und führen jeweils 100 Simulationsläufe durch. Wie Abbildung 6 zeigt sinkt die durchschnittliche Verspätung der Linien von 19,8 Sekunden unter dem initialen Fahrplan um 4,7 Sekunden oder 24 Prozent auf 15,1 Sekunden. Lediglich die Linien 3, 4 und 5 gewinnen nicht signifikant an Pünktlichkeit. Der extrem hohe Verspätungswert der Linie 7 unter dem initialen Fahrplan erklärt sich durch überaus schlecht gelegte Abfahrtzeiten an den mit Linie 1 und 13 gemeinsam genutzten Netzressourcen. Hierdurch geraten Fahrzeuge der Linie 7 hinter Bahnen anderer Linien, obwohl sie diesen planmäßig voraus fahren sollten. Dadurch sammeln die Fahrzeuge eine große Anzahl von stark verspäteten Abfahrten an. Unter dem ausgewählten Optimalfahrplan gelingt diese Koordination wesentlich besser; die einzelnen Linien bekommen größere Sicherheitsabstände zugewiesen, wodurch sich Verspätungen eines Fahrzeugs nicht unmittelbar auf Folgefahrzeuge auswirken.

Tabelle 1: Inititalfahrplan 133: Startminuten der Linien im Taktintervall für Hin- (jeweils Variante 01) und Rückrichtung (Variante 02)

Tabelle 2: Optimalfahrplan 154: Startminuten der Linien im Taktintervall für Hin- (jeweils Variante 01) und Rückrichtung (Variante 02)

Wir sehen: Ein robuster Fahrplan erhöht die Pünktlichkeit deutlich. Da die Fahrpläne keine Änderungen am Linienverlauf oder Fahrzeugpool vornehmen, muss die Ursache für die Verspätungswirksamkeit des robusten Fahrplans in der Netzstruktur zu finden sein, sich also auf die Erfüllung der Bedingungen aus Abschnitt 3 zurückführen lassen. Um diese Ergebnisse weiter zu validieren unterziehen wir die einzelnen Bedingungen in Abschnitt 4.3 weitergehenden Betrachtungen.

Für eine ausführlichere Betrachtung des Stadtbahnnetzes von Köln siehe [28] und Abschnitt 6.4 in [27].

Bild 6: KVB, Köln: Verspätungen der Linien

4.2 Modellierung des Tramway-Stadtbahnnetzes in Montpellier

Als Nächstes wird die beschriebene Software auf das deutlich weniger komplexe TramwayStadtbahnnetz der TAM, Montpellier (siehe Abbildung 7) angewandt. Die Linienplanung basiert auf dem Fahrplan von 2013 (enthalten in [19], [20], [21] und [22]). Das Netz besteht aus 84 Stationen mit 176 Haltepunkten und 46 Weichen, die durch 232 Streckenabschnitte verbunden sind. Diese Gleisabschnitte haben eine Gesamtlänge von ca. 56 Kilometern, so dass sich eine durchschnittliche Länge von etwa 241 Metern ergibt. Pro Betriebstag werden ca. 1.200 Fahrten auf 24 Linienrouten ausgeführt, dabei werden ca. 282.000 Passagiere befördert (siehe [23]).

Bild 7: Stadtbahnnetz der TAM, Montpellier

Das Stadtbahnnetz von Montpellier erfüllt die Bedingungen (b) und (c) vollständig, die Bedingung (a) jedoch wegen der geringeren Komplexität des Netzes nur an wenigen Punkten, an denen die Ressourcenkonkurrenz durch gemeinsame Nutzung besonders intensiv ist. Dabei handelt es sich um die Weichencluster um die Stationen Corum (COR, siehe Abbildung 7), Gare Saint-Roch (GSR) und Rives du Lez (RDL), die von jeweils mindestens drei Linien genutzt werden.

Das Tramway-Netz verfügt nicht über ein globales Taktintervall, die Fahrzeuge bedienen die Linienrouten während eines Betriebstags in wechselnden Mustern. In der Hauptverkehrszeit durchqueren Züge der Linien 1 und 2 die Innenstadt alle vier bis fünf Minuten. Linie 3 verkehrt alle sechs bis acht Minuten, die Abstände zwischen aufeinanderfolgenden Bahnen der Linie 4 wechseln zwischen acht und neun Minuten. Um eine angemessene Annäherung zu finden, wird ein gemeinsames Taktintervall von acht Minuten angenommen, und zusätzliche Verstärkerlinien 1A und 2A eingefügt, um die Frequenz der Linien 1 und 2 auf vier Minuten zu verdoppeln. Ein Satz verkehrsplanerischer Vorgaben wird definiert, der die Verstärkerlinien 1A und 2A und minimale Wendezeiten an den Endstationen beinhaltet.

Bild 8: TAM, Montpellier: Häufigkeiten aller Verspätungen

Der durchschnittliche Fitness-Wert der initialen Lösungskandidaten beträgt 83,58 (schlechtester Wert: 95,00), der Optimierer findet 128 optimale Lösungen mit einem Fitness-Wert von 75,22. Der Zielfunktionswert wird also um 10,0 Prozent gesenkt, die Optimalfahrpläne sind deutlich robuster als die Initialfahrpläne. Trotzdem ist die Vorbedingung nur teilweise erfüllt: Die Linien 1, 3 und 4 sind verklemmt und können daher relativ zueinander nicht frei gelegt werden. Sie bilden einen Block, der wiederum relativ zur Linie 2 weitgehend frei gelegt werden kann. Die Vorbedingung gilt also für Linie 2 und diesen Block.

Wie bereits in Abschnitt 4.1 werden je zehn Fahrpläne aus den Gruppen der initialen und optimalen Pläne gezogen, und für jeden dieser 20 Fahrpläne zehn Simulationsläufe durchgeführt. Die Läufe ergeben unter den initialen Fahrplänen einen Wert von 9,8 Sekunden als durchschnittliche Verspätung aller Abfahrten. Unter den optimalen Fahrplänen liegt der Wert bei 8,2 Sekunden, dies ist eine Reduktion um 16,3 Prozent oder 1,6 Sekunden. Die Durchschnittsverspätung aller verspäteten Abfahrten wird von 25,8 um 2,3 Sekunden oder 8,9 Prozent auf 23,5 Sekunden reduziert.

Die Häufigkeitsverteilung der Verspätungen (siehe Abbildung 8) zeigt eine Reduktion für jede Klasse. Dieser Effekt ist besonders signifikant bei größeren Verspätungen von mehr als 60 Sekunden (siehe Abbildung 9). Die Gesamtzahl der Verspätungen wird von 5.691,9 auf 5.234,7 um 457,2 Verspätungen oder 8,0 Prozent reduziert. Die Zahl der größeren Verspätungen wird von 521,3 unter den initialen Plänen um 210,7 oder 40,4 Prozent auf 310,6 reduziert.

Ein robusterer Fahrplan reduziert die Verspätungen also auch in diesem Netz. Insbesondere an den drei Punkten, an denen Bedingung (a) besonders stark greift, also den Weichen um die Stationen Corum, Gare Saint-Roch und Rives du Lez, sollte die Robustheit des Fahrplans für bessere Koordination und daher erhöhte Pünktlichkeit sorgen. Dabei wird die Station Rives du Lez jedoch ausschließlich von den verklemmten und daher unverändert bleibenden Linien 1, 3 und 4 befahren, die Pünktlichkeit ändert sich daher nicht. Die anderen beiden Stationen werden sowohl durch diese Blocklinien als auch durch die Linie 2 bedient. Um dies näher zu betrachten, wird im Folgenden der Verspätungsverlauf der Linie 2 betrachtet.

Bild 9: TAM, Montpellier: Häufigkeiten größerer Verspätungen

Dazu entnehmen wir dem Pool der Initialfahrpläne einen Fahrplan A (siehe Tabelle 3, links) mit einem Zielfunktionswert von 92,69 und dem Pool der Optimalfahrpläne einen Fahrplan B (siehe Tabelle 3, rechts). Für jeden dieser Fahrpläne werden 100 Simulationsläufe durchgeführt und ausgewertet.

Unter Fahrplan A entsteht eine durchschnittliche Linienverspätung von 8,7 Sekunden, die unter Fahrplan B um 17,2 Prozent oder 1,5 Sekunden auf 7,3 Sekunden reduziert wird. Wie erwartet entsteht einzig bei der Linie 2 eine signifikant niedrigerer Verspätung, hier wird der Wert um 24,3 Prozent von 21,6 auf 16,3 Sekunden reduziert (siehe Abbildung 10).

Wir betrachten die Fahrten 3 und 4 (siehe Abbildungen 11 und 12) eines Fahrzeugs, das die Linie 2A bedient. Während sich die gemessenen Verspätungen an verschiedenen Haltepunkten unter den beiden Fahrplänen leicht unterscheiden, finden sich die augenfälligsten Unterschiede in den Regionen der Innenstadt um die Stationen Corum und Gare Saint-Roch.

Tabelle 3: Startminuten der Linien im Taktintervall für Hin- (jeweils Variante 01) und Rückrichtung (Variante 02). Inititalfahrplan A (links) und Optimalfahrplan B (rechts)

Während der Fahrt 3 in Richtung Sabines (siehe Abbildung 11), treten Fahrzeuge der Linie 2A nach ihrer Abfahrt an der Station Corum in das Weichencluster ein, das sie mit den Linien 1, 1A, 2 und 4 teilen. Unter Fahrplan A muss das Fahrzeug auf die Ressourcen warten und kann die daraus resultierende Verspätung erst nach der Trennung der Linien nach dem Halt an Nouveau Saint-Roch (NSR) wieder einfahren. Unter Fahrplan B mit den gleichmäßiger aufgeteilten Taktintervallen stehen die benötigten Ressourcen dem Fahrzeug unmittelbar zur Verfügung, die Verspätung bleibt deutlich geringer.

Bild 10: TAM, Montpellier: Verspätungen der Linien

Auf dem Rückweg (siehe Abbildung 12) muss das Fahrzeug vier aufeinander folgende Weichen zwischen den Stationen Rondelet (RND) und Gare Saint-Roch befahren, die auch von allen anderen Linien genutzt werden. Unter dem zufällig erzeugten Fahrplan A gerät das Fahrzeug dabei hinter eine Bahn der Linie 1, obwohl es ihr gemäß Plan eine Minute voraus fahren sollte. Es muss daher darauf warten, dass die voraus fahrende Bahn den Haltepunkt an Gare Saint-Roch frei macht, und erwirbt so eine Verspätung von etwa 80 Sekunden. Es kann erst mit dem Aufholen der Verspätung beginnen, nachdem die Routen der Linien 1 und 2 sich zwischen den Stationen Comedie (CMD) und Corum trennen.
Wie vermutet wird also durch den robusten Fahrplan die Pünktlichkeit im Umfeld der Weichencluster Corum und Gare Saint-Roch positiv beeinflusst. Die Beobachtungen bestätigen daher die in Abschnitt 3 geschilderten Überlegungen.

Für eine ausführlichere Betrachtung des Stadtbahnnetzes von Montpellier siehe [29] und Abschnitt 6.5 in [27].

Bild 11: TAM, Montpellier: Verlauf der Fahrt 3 von Fahrzeug 2005

Bild 12: TAM, Montpellier: Verlauf der Fahrt 4 von Fahrzeug 2005

4.3 Prüfung der einzelnen Bedingungen

Wir unterziehen die in Abschnitt 3 formulierten Bedingungen anhand des komplexeren Kölner Stadtbahnnetzes einer genaueren Betrachtung. Im Rahmen von drei Versuchsreihen wird dabei jeweils eine der Bedingungen gezielt nicht erfüllt und die Auswirkungen auf die Verspätungswirksamkeit der Fahrpläne überprüft.

Zunächst werden die Auswirkungen der gemeinsamen Ressourcennutzung (Bedingung (a)) untersucht. Dazu wird eine Menge von Linien (1, 4, 13 und 15, vgl. Abbildung 3) definiert, die das Kölner Schienennetz weitgehend abdecken, ohne gemeinsame Ressourcen zu nutzen. Unter diesen Versuchsbedingungen verändert sich die durchschnittliche Linienverspätung vom Initialzum Optimalfahrplan nicht mehr signifikant (vgl. Abbildung 13). Die Verspätung der Linien ist also unabhängig vom verwendeten Fahrplan und damit unabhängig von dessen Robustheitsgrad.

Bild 13: Keine gemeinsame Ressourcennutzung: Verspätungen der Linien

Für die Untersuchung der Bedingung (b) wird die Variabilität der Fahrzeiten erhöht, indem die Streuung der Beschleunigszeiten erhöht wird. Die Bremszeiten können nicht beliebig gestreut werden, da die simulierten Fahrzeuge sonst beim Heranfahren an ein Hindernis zu häufig in Unfälle verwickelt sind. Die durchschnittliche Verspätung des robusten Fahrplans 154 sinkt jedoch schon unter diesen Versuchsbedingungen nur noch von 8,2 Sekunden auf 7,9 Sekunden um 3,7 Prozent (vgl. Abbildung 14). Die Auswirkungen der Robustheit auf die Pünktlichkeit wird also durch steigende Variabilität der Fahrzeiten gesenkt.

Bild 14: Erhöhte Variabilität der Fahrzeiten: Verspätung der Linien

Um für den letzten Versuch Ressourcenredundanz herzustellen werden alle Netzressourcen mit unendlicher Kapazität versehen. Unter diesen Bedingungen ändert sich die durchschnittliche Verspätung von Fahrplan 133 zu Fahrplan 154 ebenfalls nicht mehr signifikant (vgl. Abbildung 15). Ohne Ressourcenkonkurrenz hat die Robustheit des Fahrplans also keine Auswirkungen auf die Pünktlichkeit der Fahrzeuge.

Bild 15: Ressourcenredundanz: Verspätung der Linien

Offenbar hat bereits das Nichterfüllen einer einzelnen Bedingung entscheidende Auswirkungen auf die Verspätungswirksamkeit von Robustheit. Robuste Fahrpläne führen also zu Verspätungsreduktionen bei Vorliegen der in Kapitel 3 formulierten Bedingungen an die Netzstruktur.

5 Zusammenfassung und Ausblick

Nach einer kurzen Einführung in Thema und Ziel der Arbeit wurde auf einige Hintergründe der Zielgröße Robustheit eingegangen und eine Methode zur Generierung robuster Fahrpläne vorgestellt, die auch verkehrsplanerische Vorgaben berücksichtigt. Danach wurden einige Bedingungen vorgestellt, bei deren Vorliegen ein robuster Fahrplan zur Verbesserung der Pünktlichkeit beiträgt. Neben der Vorbedingung, dass überhaupt Potential zur Generierung eines robusten Fahrplans vorhanden sein muss, wurden dabei drei Bedingungen identifiziert: Im Stadtbahnnetz muss eine Ressourcenkonkurrenz zwischen einzelnen Linien bestehen, die Fahrzeiten der Bahnen müssen eine geringe Variabilität aufweisen, und die Netzressourcen dürfen nicht redundant ausgelegt sein. Die Überlegungen wurden durch eine Reihe von Experimenten bestätigt, in denen der Einfluss robuster Fahrpläne auf die Pünktlichkeit in den Stadtbahnnetzen der Städte Köln und Montpellier untersucht wurde. Abschließend konnte durch weitere Experimente gezeigt werden, dass bereits das Nichterfüllen einer einzelnen Bedingung entscheidende Auswirkungen auf die Verspätungswirksamkeit von Robustheit hat.

Im Rahmen der weiteren Arbeiten soll die Stadtbahnsimulation um ein Modell von Individualund Busverkehr erweitert werden, und so den gesamten Stadtverkehr abbilden. Erste Untersuchungen hierzu werden in [30] vorgestellt. Weiterhin soll die Eignung der beschriebenen Software-Werkzeuge anhand weiterer Beispielnetze überprüft werden. Welche Netze dies sein werden, ist noch offen.

6 Danksagung

Diese Arbeit wurde zum Teil durch die National Science Foundation unter den Fördernummern I/UCRC IIP-1338922, AIR IIP-1237818, SBIR IIP-1330943, III-Large IIS-1213026, MRI CNS-0821345, MRI CNS-1126619, CREST HRD-0833093, I/UCRC IIP-0829576, MRI CNS-0959985, FRP IIP-1230661 und durch das U.S. Department of Transportation im Rahmen einer TIGER Förderung gefördert.

7 Literatur

[1]    Bampas, E., Kaouri, G., Lampis, M., Pagourtzis, A.: Periodic Metro Scheduling. In: Proceedings of ATMOS, 2006.

[2]    Banks, J., Carson, J.S., Nelson B.L., Nicol D.M.: Discrete-Event System Simulation. Pearson, 2010.

[3]    Cacchiana, V., Caprara, A., Fischetti, M.: A Lagrangian Heuristic for Robustness, with an Application to Train Timetabling. In: Transportation Science, to appear.

[4]    Caimi, G., Fuchsberger, M., Laumanns, M., Schüpbach, K.: Periodic Railway Timetabling with Event Flexibility. In: Networks, 2010, Volume 57, Number 1, pp. 3-18.

[5]    Dakin, R. J.: A tree-search algorithm for mixed integer programming problems. In: The Computer Journal, Volume 8, 1965, pp. 250–255.

[6]    Dréo, J., Pétrowski, A., Siarry, P. and Taillard, E.: Metaheuristics for Hard Optimization. Springer, 2006.

[7]    Genç, Z.: Ein neuer Ansatz zur Fahrplanoptimierung im ÖPNV: Maximierung von zeitlichen Sicherheitabständen. Dissertation, Mathematisch-Naturwissenschaftliche Fakultät, Universität zu Köln, 2003.

[8]    Ginkel, A., Schöbel, A.: To Wait or Not to Wait? The Bicriteria Delay Management Problem in Public Transportation. In: Transportation Science, Vol. 41, Number 4, Nov. 2007, pp. 527-538.

[9]    Institut national de la statistique et des études économiques: La population de Montpellier Agglomération a triplé au cours des cinquante dernières années. http://www.insee.fr/fr/themes/document.asp?ref_id=16088, accessed on June, 26th, 2013.

[10]    Kölner Verkehrsbetriebe AG, Deutsche Bahn AG, VRS GmbH (Hrsg.): Bahnen in Köln 2012. Netzplan, 2012.

[11]    Knuth, D.: Estimating the efficiency of backtrack programs. Mathematics of Computation 29 (129), 1975, pp. 121–136.

[12]    Lückerath, D., Ullrich, O., Speckenmeyer, E: Modeling time table based tram traffic. In: Simulation Notes Europe (SNE), ARGESIM/ASIM Pub., TU Vienna, Volume 22, Number 2, August 2012, pp. 61-68.

[13]    Lückerath, D., Ullrich, O., Speckenmeyer, E.: Applicability of rescheduling strategies in tram networks. In: Proceedings of ASIM-Treffen STS/GMMS 2013, ARGESIM Report 41, ASIM-Mitteilung AM 145, ARGESIM/ASIM Pub., TU Vienna/Austria, Reichardt, R. (Ed.), Februar 2013, 7 pg.

[14]    Middelkoop, D., Bouwman, M.: SIMONE: Large Scale Train Network Simulations. In: B.A. Peters, J.S. Smith, D.J. Medeiros, M.W. Rohrer (Ed.): Proceedings of the 2001 Winter Simulation Conference, Arlington, 2001.

[15]    Nash, A., Huerlimann, D.: Railroad Simulation Using OpenTrack. In: Allan, J., R.J. Hill, C.A. Brebbia, G. Sciutto, S. Sone (Ed.): Computers in Railways IX, WIT Press, Southampton, 2004, pp. 45-54.

[16]    Schöbel, A.: A Model for the Delay Management Problem based on Mixed-IntegerProgramming. In: Proceedings of ATMOS, 2001.

[17]    Speckenmeyer, E., Li, N., Lückerath, D., Ullrich, O.: Socio-Economic Objectives in Tram Scheduling. Technical Report, Univ. Köln, 2012.

[18]    Suhl, L., Mellouli, T.: Managing and preventing delays in railway traffic by simulation and optimization. In: Mathematical Methods on Optimization in Transportation Systems 2001, pp. 3–16.

[19]    Transports de l'agglomération de Montpellier (Ed.: Subra, R.): Horaires tram 1. 2012.

[20]    Transports de l'agglomération de Montpellier (Ed.: Subra, R.): Horaires tram 2. 2012.

[21]    Transports de l'agglomération de Montpellier (Ed.: Subra, R.): Horaires tram 3. 2012.

[22]    Transports de l'agglomération de Montpellier (Ed.: Subra, R.): Horaires tram 4. 2012.

[23]    Transports de l'agglomération de Montpellier: Un réseau en étoile. http://www.montpellier-agglo.com/tam/page.php?id_rubrique=31, accessed on Feb, 21st, 2013.

[24]    Transports de l'agglomération de Montpellier: Le tracé du ligne 5. http://www.ligne5montpellier-agglo.com/?page_id=16, accessed on Feb, 21st, 2013.

[25]    Transports de l'agglomération de Montpellier (Ed.: Subra, R.): Plan du réseau du centre de l'agglomération. 2012.

[26]    Turnquist, M. A., Bowman, L. A.: The effects of network structure on reliability of transit service. In: Transportation Research Part B: Methodological, Volume 14, Issues 1–2, March–June 1980, pp. 79-86.

[27]    Ullrich, O.: Modellbasierte Parallelisierung von Anwendungen zur Verkehrssimulation Ein dynamischer und adaptiver Ansatz. Dissertation, Univ. Köln, to appear.

[28]    Ullrich, O., Lückerath, D., Franz, S., Speckenmeyer, E.: Simulation and optimization of Cologne's tram schedule. In: Simulation Notes Europe (SNE), ARGESIM/ASIM Pub., TU Vienna, Volume 22, Number 2, August 2012, pp. 69-76.

[29]    Ullrich, O., Lückerath, D., Speckenmeyer, E.: A robust schedule for Montpellier's Tramway network. Technical Report, Univ. Köln, 2013.

[30]    Ullrich, O., Proff, I., Lückerath, D., Kuckertz, P., Speckenmeyer, E.: Agent-based modeling and simulation of individual traffic as an environment for bus schedule simulation. In: Proceedings of Mobil.TUM 2013, to appear.

[31]    Verband Deutscher Verkehrsunternehmen e.V.: VDV-Standardschnittstelle Liniennetz/Fahrplan, VDV-Schriften 452, 2008.