Kurzfassung

Zur Instandhaltung von Eisenbahnnetzen sind regelmäßig Baumaßnahmen erforderlich. Diese erfordern stets Anpassungen der Fahrpläne. Um den Fahrgästen trotz der Baumaßnahme weiterhin einen möglichst großen Teil des Regelangebotes bieten zu können, bewegen sich die resultierenden Baufahrpläne insbesondere in Schnellbahnnetzen mit ihren dichten Zugfolgen häufig nahe der Kapazitätsgrenze der Infrastruktur.

Etablierte Verfahren zur Taktfahrplanoptimierung können diesen Anforderungen nicht genügen, da in der Praxis Anpassungen von Laufwegen der Linien, sowie der Gleisbelegungen häufig Teil der realisierten Lösungen sind. Für diese Aufgabe haben die Autoren zuletzt ein Optimierungsmodell vorgestellt, welches diese Möglichkeiten ausschöpft. In dem vorliegenden Beitrag wird erstmalig dessen Anwendung auf ein unmittelbar der Praxis der Baufahrplanung entnommenes Beispiel aus dem Netz der Berliner S-Bahn im Detail beschrieben.

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

1 Einleitung

Auf dem Netz der S-Bahn Berlin gibt es jährlich etwa 1.300 Baumaßnahmen. Für jede einzelne davon ist eine Anpassung des regulären Angebots notwendig. Insbesondere müssen Linienkonzepte, Fahr- und Umlaufpläne entsprechend der Bausituation verändert werden. Je nach Umfang der Einschränkungen – von Sperrungen für wenige Stunden in der Nacht bis hin zu monatelangen Streckensanierungen – bindet dieser Umplanungsbedarf erhebliche Planungskapazitäten beim Infrastrukturbetreiber DB Netz AG. Die Erstellung von Baukonzepten erfolgt dabei in der Praxis weitestgehend von Hand, sodass kleinere Baumaßnahmen zeitintensive Routinearbeit bedeuten, während bei größeren der Überblick über die möglichen Planungsoptionen ins Hintertreffen geraten kann.

In diesem Beitrag widmen wir uns daher dem Ziel, diesen Planungsprozess für Baustellenszenarien durch den Einsatz mathematischer Methoden zu digitalisieren, zu automatisieren und zu optimieren. Dabei werden wir folgende vier Teilaspekte betrachten:

• Linienplanung: Auf welchen Abschnitten des Streckennetzes sollen welche Linien mit welcher Taktfrequenz verkehren?
• Taktfahrplanung: Zu welchen Zeitpunkten sollen die Fahrten der einzelnen Linien abfahren bzw. ankommen?
• Gleisbelegung: Welche Gleise sollen die Fahrten nutzen?
• Umlaufplanung: Wie sollen Fahrten miteinander verknüpft werden?

Wir orientieren uns an dazu an folgenden Planungsparametern:

• Fahr- und Umlaufplanung sind periodisch.
• Der Detailgrad ist mesoskopsich: Der Fahrplan enthält nicht nur eine Ankunfts- bzw. Abfahrtszeit pro Betriebsstelle, sondern unterscheidet innerhalb einer Betriebsstelle zwischen den Bahnsteig- und Kehrgleisen. Er verweist jedoch nicht auf mikroskopische Infrastrukturelemente, wie z. B. Weichenanfänge- oder enden.

Diese Punkte treffen auf viele Schienennahverkehrsnetze zu und sind auch die Grundlage für die aktuelle manuelle Planung bei der DB Netz AG für das Netz der S-Bahn Berlin.

Obwohl die Linien-, Fahr- und Umlaufplanung traditionell als getrennte Planungsschritte aufgefasst werden [1], ist es insbesondere im Baustellenkontext äußerst sinnvoll, eine integrierte Betrachtung vorzunehmen. Denn Baustellen führen nicht nur direkt zum Ausfall der gesperrten Infrastruktur, sondern auch zu indirekten Einschränkungen, wenn zum Beispiel Fahrten an anderen Betriebsstellen gebrochen werden müssen und dort zusätzliche Kehrkapazitäten in Anspruch nehmen. Zum einen sollen die baubedingte Angebotsreduktion so gering wie möglich sein, so dass möglichst viele Züge möglichst weit an den gesperrten Bereich herangeführt werden. Zum anderen erfordert das Brechen von Zugfahrten an den Grenzen gesperrter Bereiche Wendevorgänge, welche zu einer stärkeren Kapazitätsbeanspruchung in Form von längeren Gleisbelegungen als reguläre Fahrten führen. Speziell in zentralen Bereichen des Netzes wie beispielsweise sogenannter „Stammstrecken“ ergibt sich hieraus ein Betriebsprogramm, welches sich häufig dicht an der Kapazitätsgrenze bewegt.

Ein besonderes Beispiel sind die im 5-Minuten-Takt verkehrenden Züge der Linien S41 und S42 auf der Berliner Ringbahn, die im Regelbetrieb überhaupt nicht die Fahrtrichtung wechseln, aber im Falle einer Sperrung eines Teils der Berliner Ringbahn Wendekapazitäten von 12 Zügen pro Stunde an jeweils 2 Betriebsstellen erfordern. Erschwerend kommt noch hinzu, dass Teile der Ringbahn noch von 9 weiteren Zügen pro Stunde und Richtung bedient werden. Bahnhöfe erweisen sich daher als Flaschenhals, sodass eine detaillierte Planung von Kehr- und Bahnsteiggleisbelegungen unabdingbar ist. Ein guter Linienplan muss also auch bereits die Wendesituation berücksichtigen, die aber ohne Fahr- und Umlaufplan nicht präzise bewertet werden kann.

Im Gegensatz zur etablierten Anwendung von Taktfahrplanoptimierung mit festem Linienplan und ebenfalls vorab festgelegter Gleisbelegung weist das in diesem Beitrag verwendete und in [7] vorgestellte Modell einerseits eine deutlich höhere Komplexität des Optimierungsproblems auf. Andererseits umfassen die resultierenden Instanzen aufgrund des regelmäßig verfolgten Ziels der Begrenzung baubedingter Einschränkungen üblicherweise deutlich weniger zu planende Linien als das Regelangebot. Insgesamt können damit von Planerinnen und Planern als anspruchsvoll bezeichnete Planfälle mit Optimierungsverfahren optimal gelöst werden. Die Lösung eines solchen Szenarios beschreiben wir in Kapitel 3 erstmals im Detail.

Wir rekapitulieren daher zunächst in Kapitel 2 unser auf gemischt-ganzzahliger Programmierung beruhendes Optimierungsmodell, das Linien-, Fahr- und Umlaufplanung entsprechend der oben beschriebenen Planungsparameter integriert [7]. Anschließend demonstrieren wir in Kapitel 3 die Praxistauglichkeit des Modells anhand einer zukünftig geplanten Baumaßnahme am Berliner S-Bahnhof Westkreuz.

2 Das integrierte wendesensitive Taktfahrplanungsproblem

Der Kern unseres Optimierungsmodells ist eine Erweiterung des Periodic Event Scheduling Problems (PESP) [12] zum integrierten wendesensitiven Taktfahrplanungsproblem. Wir diskutieren zunächst, warum eine solche Erweiterung vonnöten ist.

2.1 Unzulänglichkeiten des reinen PESP-Modells

Das PESP-Modell ist das weitgehend verwendete mathematische Modellierungswerkzeug für Taktfahrplanoptimierung und kann viele praktische Aspekte abbilden [12]. Es hat aber aus der Perspektive von Eisenbahnfahrplänen zwei fundamentale Schwächen, die beide insbesondere innerhalb von Bahnhöfen auftreten:

1. Es wird ein festes Routing der Züge vorausgesetzt [4]. Diese starre Festlegung nutzt im Allgemeinen nicht alle betrieblichen Möglichkeiten aus, kann jedoch durch eine Erweiterung von PESP umgangen werden („Track Choice“) [13].
2. Mindestzugfolgezeiten werden für gewöhnlich durch Abstandskanten modelliert, die beispielsweise festlegen, dass zwischen zwei Abfahrten oder zwei Ankünften auf dem gleichen Gleis immer mindestens h Minuten liegen müssen. Ist die Aufenthaltszeit größer gleich h, wie es häufig bei Wendesituationen vorkommt, kann es zum sogenannten Gleisbelegungsproblem („Track Occupation Problem“) kommen [6], siehe Bild 1.

Bild 1:  Gleisbelegungsproblem. Im dargestellten Taktfahrplan mit der Periode T =20 halten zwei Züge zur gleichen Zeit an der gleichen Bahnsteigkante: von Minute 3 bis Minute 8, obwohl die Mindestzugfolgezeit von 3 Minuten bezogen auf die Ankünfte und Abfahrten eingehalten wird. Würde die Abfahrt der unteren Zugfahrt bereits zur Minute 5 erfolgen, so würde auf demselben Gleis eine betrieblich nicht mögliche Überholung stattfinden, obwohl sämtliche Restriktionen erfüllt wären.

Das Gleisbelegungsproblems kann zwar mit einigem Aufwand innerhalb des PESP-Modells realisiert werden, es ist aber günstiger, dies mit speziell zugeschnittenen Abstandsbedingungen zu realisieren, die auch die Aufenthaltszeit miteinbeziehen [6].

Eine fundamentale Beobachtung ist, dass die Track-Choice-Erweiterung nicht nur eine freie Wahl von Fahrwegen innerhalb von Betriebsstellen erlaubt, sondern auch außerhalb. Insbesondere kann so auch der Laufweg einer Linie mit dem gleichen Ansatz modelliert werden. Ähnliches gilt für Fahrzeugübergänge. Track Choice ist also nicht nur für Fahrplanung wertvoll, sondern ermöglicht gleichzeitig auch Linien- und Umlaufplanung [7]. Dies steht im Unterschied zu weiteren integrierten Modellen (z. B., [2], [9], [11]).

2.2 Fahrplanungsgraph

Bevor wir uns dem eigentlichen Optimierungsmodell widmen, beschreiben wir das Herzstück des Modells, den Fahrplanungsgraphen G als Ereignis-Aktivitäts-Netzwerk, siehe auch [7].

Für dessen Konstruktion leiten wir zunächst aus der Eisenbahninfrastruktur einen gerichteten Infrastrukturgraphen I ab. Dessen Knoten sind Infrastrukturpunkte, wie z. B. Bahnsteig- oder Kehrgleise, die alle einer Betriebsstelle zugeordnet sind. Zwei Knoten v und w werden durch eine Gleiskante ( v , w ) verbunden, wenn ein Zug von v nach w ohne Fahrtrichtungswechsel fahren kann. Ein Infrastrukturpunkt kann in höchstens zwei Richtungen verlassen werden, die wir mit + bzw. − markieren. Jeder Gleiskante ordnen wir daher auch ein Paar von Richtungsmarkierungen zu.

Werden die Infrastrukturpunkte kontrahiert, die zur gleichen Betriebsstelle gehören, entsteht aus I der Betriebsstellengraph B, dessen Knoten die Betriebsstellen sind. Zwischen zwei Betriebsstellen s und t existiert dann genau dann eine gerichtete Kante ( s , t ), wenn es zwischen s und t eine direkte Gleisverbindung ohne Passieren einer weiteren Betriebsstelle gibt.

Bild 2:  Die Abbildung zeigt von oben nach unten ein schematisches Infrastrukturlayout, den Infrastrukturgraphen I mit Richtungsmarkierungen, den Betriebsstellengraphen B mit zwei Linien L₁ und L₂ und den resultierenden Fahrplanungsgraphen G. Die Knoten von G sind entsprechend ihrer Betriebsstelle positioniert und mit ihrer Richtungsmarkierung + bzw. − beschriftet. Die Linie ist durch die Farbe der Umrandung markiert, der Ereignistyp durch die Hintergrundfarbe (grau: Abfahrt, weiß: Ankunft). Die blau eingefärbten Kanten des Fahrplanungsgraphen G sind Haltekanten, Wendekanten sind orange und Fahrtkanten schwarz.

Ein Routing von einem gerichteten Pfad L in B ist ein gerichteter Pfad in I , dessen Folge von Betriebsstellen mit der durch L gegebenen übereinstimmt, und auf dem Züge keine Richtungswechsel benötigen. Eine Linie ist ein gerichteter Pfad L in B, der mindestens ein Routing in I besitzt. Die Vereinigung der Kanten aller Routings einer Linie L nennen wir Routingbündel R ( L).

Wir können nun den Fahrplanungsgraphen G definieren: Sei ℒ eine Menge von Linien und C ⊆ ℒ×ℒ eine Menge von möglichen Fahrzeugübergängen zwischen zwei Linien. Jeder Knoten von G wird durch ein 4-Tupel ( L , S , D , R ) beschrieben, bestehend aus einer Linie L ∈ ℒ, einer Betriebsstelle S, einem Ereignistyp D aus {an , ab} für Ankünfte bzw. Abfahrten, und einer Richtungsmarkierung aus {+, −}. Die Kantenmenge A (G ) von G wird wie folgt konstruiert:

• Für jede Linie L ∈ ℒ und jede Kante ( v , w ) von L mit Richtungsmarkierungen (α , β ) im Routingbündel R ( L): Füge eine Fahrtkante von ( L , v , ab , α ) nach ( L , w, an , β ) zu G
• Füge eine Haltekante von ( L , v , an , α ) nach ( L , v , ab , β ) zu G hinzu, wenn es Kanten (u , v ) und ( v , w ) in R ( L) gibt, für die die Richtungsmarkierungen α von v bezüglich (u , v ) und β von v bezüglich ( v , w ) verschieden sind.
• Füge eine Übergangskante ( L , v , an , α ) nach ( L ' , v , ab , β ) hinzu, wenn ( L , L ' ) ein Fahrzeugübergang in C ist und es Kanten (u , v ) in R ( L) und ( v , w ) in R ( L' ) mit den Richtungsmarkierungen α von v bezüglich (u , v ) und β von v bezüglich ( v , w ) Ist α ≠ β, so nennen wir diese Kante auch Haltekante, andernfalls eine Wendekante.

Bild 2 zeigt eine beispielhafte Konstruktion eines Fahrplanungsgraphen ausgehend von der Infrastruktur.

Jeder gerichtete Kreis im Fahrplanungsgraphen G beschreibt einen möglichen Umlauf eines Fahrzeugs. Ein Umlaufplan ist daher eine Menge von paarweise knotendisjunkten gerichteten Kreisen in G. Wir werden einen Umlaufplan Q als Teilgraphen von G mit Knotenmenge V (Q ) und Kantenmenge A (Q ) auffassen. Die Wahl eines Umlaufplans legt auch die benutzten Fahrtkanten fest, die Kanten im Routingbündel und damit Teilstücken von Linien zugeordnet werden können. Wir verlangen aber nicht a priori, dass ein Umlaufplan jede Linie komplett abdeckt. Dies ist im Hinblick auf den Baustellenkontext zu interpretieren, weil so Verkürzungen, Verlängerungen und gebrochene Verkehre wie Pendelverkehr möglich werden.

2.3 Infrastrukturbasierte Taktfahrplanung

Der letzte Baustein ist die Integration von Fahrplänen, um insbesondere die Umsetzbarkeit eines Umlaufplans und des darin impliziert kodierten Linienplans zu gewährleisten. Wir betrachten dafür Taktfahrpläne mit einer Periode T . Für jede Kante (i , j) ∈ A (G ) sei zusätzlich eine untere Schranke lij und eine obere Schranke uij vorgegeben. Damit können z. B. Mindestfahrzeiten oder Mindestwendezeiten modelliert werden [5]. Ein Taktfahrplan für einen Umlaufplan Q ist ein Vektor π ∈{0 ,1 , ..., T − 1}^{V (Q)} mit der Eigenschaft, dass für jede Kante (i , j )∈ A (Q ) ein Wert x_ij ∈[l_ij ,u_ij ] existieren muss, der π _j −π_i ≡x_ij mod T erfüllt.

Wegen des in §2.1 angesprochenen Gleisbelegungsproblems greift diese Definition von Taktfahrplänen, wie sie im Kontext des Periodic Event Scheduling Problems üblich ist, jedoch zu kurz. Die Modellierung von Sicherheitsabständen zwischen Zügen muss daher etwas feingliedriger erfolgen: Die Halte- und Wendekanten in A (G ) lassen sich immer einem eindeutigen Infrastrukturpunkt, also Knoten im Infrastrukturgraphen I, zuordnen. Die Fahrtkanten zeigen hingegen auf Kanten in I . Zusammengefasst lassen sich also alle Kanten in A (G ) einem Infrastrukturelement zuweisen. Wir verlangen nun für jedes Infrastrukturelement e, dass zwischen zwei Fahrten immer zwei zeitliche Abstände eingehalten werden müssen, siehe auch Bild 3:

• Die Mindestzugfolgezeit h_e, welche für jede Zugfahrt vom Zeitpunkt, zu dem sie in das Infrastrukturelement e einfährt, bis zum Zeitpunkt der Einfahrt jeder anderen Zugfahrt in dasselbe Infrastrukturelement mindestens vergehen muss,
• Die Räumungszeit ε _e welche für jede Zugfahrt vom Zeitpunkt, zu dem sie das Infrastrukturelement e verlässt, bis zu dem Zeitpunkt der Einfahrt jeder anderen Zugfahrt in dasselbe Infrastrukturelement mindestens vergehen muss.

Diese beiden Kriterien sind an tatsächliche Planungsparameter für die weit verbreitete blockbasierte Zugsicherung angelehnt [8]. Wir nennen einen Taktfahrplan konfliktfrei, wenn diese beiden Abstandsbedingungen für alle Infrastrukturelemente bezüglich der durch den Umlaufplan Q gewählten Kanten in A (Q ) erfüllt werden.

Bild 3: Visualisierung von Mindestzugfolgezeit he und Räumungszeit ε_e auf einer Uhr mit Periode T =12 für zwei Kanten (i₁ , j₁) und (i₂ , j₂ ), die dem gleichen Infrastrukturelement zugeordnet sind.

2.4 Problemdefinition

Mit den Konstruktionen von § 2.2 und § 2.3 können wir unser zentrales Problem definieren:

Definition 1 (Integriertes wendesensitives Taktfahrplanungsproblem). Sei I ein Infrastrukturgraph, B der dazugehörige Betriebsstellengraph, ℒ eine Menge von Linien auf B und C ⊆ ℒ×ℒ eine Menge von Fahrzeugübergängen. Finde einen optimalen konfliktfreien Taktfahrplan π für einen Umlaufplan Q bezüglich G.

Da wir nicht fordern, dass der Umlaufplan alle Linien vollständig abdecken muss, hat dieses Problem immer die durch einen leeren Umlaufplan gegebene triviale Lösung.

Für den Kontext von Baustellenszenarien erweitern wir diese Definition leicht. Dazu teilen wir den Fahrplanungsgraphen G in drei Teile mit paarweise disjunkten Kantenmengen auf:

• den Sperrgraphen, der aus den Kanten besteht, die wegen einer Infrastruktursperrung nicht benutzt werden können,
• den Planungsgraphen, auf dem beliebig umgeplant werden kann,
• den Fixgraphen, auf dem der Regelfahrplan ̅π und der Regelumlaufplan ̅Q beibehalten werden müssen.

Der genaue Zuschnitt des Planungsgraphen kann dabei wesentlichen Einfluss auf die erzielbare                    Lösungsqualität besitzen. Zwar ist es das generelle Ziel baubedingter Einschränkungen, diese nur räumlich begrenzt wirken zu lassen. Doch führen in der Praxis beispielsweise Sperrungen entlang der Berlinger Ringbahn nicht selten sowohl im nördlichen als auch im südlichen Bereich der Stadt zu einem – ggf. nur leicht – veränderten Angebot. Sofern die verfügbare Rechenkapazität dies also zulässt, sollte der Planungsgraph tendenziell großzügig gewählt werden, um die volle algorithmische Stärke ausschöpfen und qualitativ hochwertige Lösungen erzielen zu können.

Definition 2 (Integriertes wendesensitives Bautaktfahrplanungsproblem). Sei G ein Fahrplanungsgraph wie oben mit der Zerlegung in Sperr-, Planungs- und Fixgraph. Sei ̅π ein Fahrplan für einen Umlaufplan ̅Q auf G. Finde einen optimalen konfliktfreien Taktfahrplan π für einen Umlaufplan Qbezüglich der Vereinigung des Planungsgraphen G_P und des Fixgraphen G_F, sodass Q ∩G_F =̅Q∩G_F und π_i=̅π_i für alle i ∈ V (G_F ) gilt, oder entscheide, dass es keine solche Kombination aus Fahr- und Umlaufplan gibt.

Beide Definitionen lassen offen, was „optimal“ bedeutet. Wir schlagen im nächsten Abschnitt eine konkrete Zielfunktion vor.

2.5 Gemischt-ganzzahliges Optimierungsmodell

Formel in der PDF

Für das integrierte wendesensitive Bautaktfahrplanungsproblem verwenden wir das oben dargestellte Optimierungsmodell. Wir erklären kurz die wesentlichen Punkte und verweisen auf [6] und [7] für die Details.

Die binären Variablen b_ij geben für jede Kante (i, j )∈ A (G ) des Fahrplanungsgraphen an, ob sie  Teil  des  gewählten  Umlaufplans  Q  ist.  Die  Flusserhaltung  (3)  und  die Ausgangsflussbeschränkung  (4)  stellen  sicher,  dass  die  Kreise  in  Q  einfach  und knotendisjunkt sind. Die Bedingungen (6) und (7) fixieren den Fahr- und Umlaufplan im Fixgraphen G_F.

Für eine Wahl von b-Variablen sind die Bedingungen (1)-(2) in Kombination mit (14), (16),

(19) die üblichen PESP-Bedingungen [12] für einen Taktfahrplan π, wobei der Wert x_ij durch y_ij+ l_ij ersetzt wird. Dabei greifen die unteren und oberen Schranken für eine Kante (i , j ) aber nur, wenn auch b_ij=1 gewählt wurde, ansonsten wird die obere Schranke derart vergrößert, dass jeder Fahrplan für die Kante zulässig wird.

Die Bedingungen (8)-(13) stellen die Konfliktfreiheit sicher. Wir bezeichnen die Menge der Infrastrukturelemnete mit E und für jedes e ∈ E die Menge der Paare verschiedener Kanten von A (G ), die auf e zeigen, mit P_e. Die Abstandsbedingungen werden nur aktiviert, wenn beide Kanten auch mittels der b-Variablen gewählt wurden. Es werden dafür neue binäre Variablen benötigt, die durch Paare von Knoten von G beschriftet werden können; wir fassen diese Paare in der Menge P zusammen. Die genaue Logik der Bedingungen wird in [6] ausführlich geschildert.

Schließlich erläutern wir die Zielfunktion, die aus zwei Komponenten besteht. Die erste Komponente minimiert die Summe der Angebotsreduzierungen ca für jede Kante a ∈ A (B ) des Betriebsstellengraphen B. Der Wert von c_a wird durch die Bedingung (5) bestimmt, in der für jedes a ∈ A (B ) die dazugehörigen gewählten Fahrtkanten gezählt und in Relation zum Regelangebot ̅f _a gesetzt werden. Ein größeres Angebot als im Regelfahrplan wird dabei wegen (15) nicht in der Zielfunktion belohnt. Der zweite Teil der Zielfunktion minimiert die Anzahl der gewählten Wendekanten. Dies soll einen Anreiz setzen, unnötige Umstiege durch gebrochene Linien zu vermeiden.

3 Fallstudie: Berlin Westkreuz

Wir demonstrieren hier die Anwendung des in Kapitel 2 beschriebenen Optimierungsmodells für eine konkrete geplante Baumaßnahme auf dem Netz der Berliner S-Bahn. Dies erfolgt im Gegensatz zu [7], wo eher die Analyseebene von Kennzahlen eingenommen wurde, hier nun erstmalig in Form einer detaillierten Beschreibung der berechneten Lösung, des berechneten Baufahrplans.

3.1 Charakteristika des Berliner S-Bahn-Netzes

Die S-Bahn Berlin ist ein weitgehend autarkes Schienennahverkehrssystem. Auf dem 340 km großen Netz mit 168 Bahnhöfen betreibt die S-Bahn Berlin GmbH 16 Linien, die im Jahr 2022 ca. 410 Millionen Passagiere bei einer Betriebsleistung von knapp 33 Millionen Zugkilometern befördert haben. Ein großer Teil des Netzes ist zweigleisig ausgebaut, vor allem außerhalb der Berliner Stadtgrenze gibt es aber nicht wenige eingleisige Abschnitte. Die maximale Gleisbelegung liegt bei 21 Zügen pro Stunde und Richtung. Pro Jahr gibt es etwa 1.300 Baumaßnahmen unterschiedlicher Ausdehnung [10].

3.2 Das Westkreuz-Szenario

Der S-Bahnhof Westkreuz ist ein Turmbahnhof und daher in zwei unabhängige Betriebsstellen aufgeteilt. Wir befassen uns mit der unteren Ebene, der Betriebsstelle BWKS an der verlängerten Berliner Stadtbahn, die von den Linien S3, S5, S7 und S9 bedient wird. Eine schematische Übersicht über die Infrastruktur findet sich in Bild 4. Die Betriebsstelle BWKS besitzt zwei Bahnsteige, zwischen denen ein weiteres Gleis verläuft. Im Westen gibt es drei Kehrgleise, von denen im Regelfahrplan zwei von der im 10-Minuten-Takt verkehrenden Linie S5 belegt werden. Außerdem verzweigen sich am Westkopf des Bahnhofs die Strecken nach Potsdam (S7, alle 10 Minuten) und Spandau (S3, S9, jeweils alle 20 Minuten). Im Osten schließt sich der Bahnhof Charlottenburg an, der ebenfalls über zwei Bahnsteige und einige Kehrmöglichkeiten im Westen verfügt.

Bild 4:  Infrastruktur und Regellinienplan rund um die Betriebsstelle BWKS (Westkreuz). Durchgehende Hauptgleise sind blau markiert, der gesperrte Abschnitt ist rot unterlegt. Jedes Liniensymbol steht hier für eine Zugfahrt alle 20 Minuten.

Im Zusammenhang mit dem Umbau des Autobahndreiecks Funkturm muss am S-Bahnhof Westkreuz Baufreiheit für einen Brückenpfeiler hergestellt werden. Dazu müssen alle drei westlichen Kehrgleise gesperrt werden, und auch das von der S7 befahrene Richtungsgleis von Potsdam/Grunewald nach Westkreuz steht nicht zur Verfügung, siehe Bild 4. Die Bahnhofsinfrastruktur lässt für die S5 nur betrieblich ungünstige Wendemöglichkeiten übrig, und die S7 muss von Grunewald bis Charlottenburg das Gegengleis benutzen. Dieser Engpass ist umso dramatischer, als dass die S7 an ihrem westlichen Ende in Potsdam mehrere eingleisige Abschnitte bedient. Die Linien S3 und S9 sind von der Sperrung nicht betroffen.

3.3 Planungsparameter

Wir modellieren das Szenario nun im Rahmen des integrierten wendesensitiven Bautaktfahrplanungsproblems.

Für den Infrastrukturgraphen benutzen wir von der DB Netz AG bereitgestellte Infrastrukturdaten. Wir verwenden folgende Linien, die wir jeweils als alle 20 Minuten fahrende Zuggruppen betrachten, zusammen mit folgenden Fahrzeugübergangsmöglichkeiten:

Tabelle 1: Linien und Fahrzeugübergänge für das Westkreuz-Szenario

Jede dieser Zuggruppen fährt in beide Richtungen. Im Regelfahrplan fährt die S5 nur bis Westkreuz, wo die Züge von Zuggruppe E zu EI und umgekehrt wechseln. Wir sehen also explizit eine Verlängerung entlang der Strecke nach Spandau bis Olympiastadion vor, weil dort ausreichend Wendekapazitäten bestehen. Die Möglichkeit des Fahrzeugübergangs E/EI behalten wir bei.

Der Sperrgraph ergibt sich aus der in Bild 4 ersichtlichen gesperrten Gleisabschnitte. In Einklang mit Tabelle 1 wählen wir als Planungsgraphen die Infrastruktur der in Tabelle 2 angegebenen Streckenabschnitte:

Tabelle 2: Streckenabschnitte des Planungsgraphen

Östlich Zoologischer Garten, wo auch ein Kehrgleis zu Verfügung steht, müssen die Züge der Linien S3, S5, S7, S9 demnach wie im Regelfahrplan fahren. Das gleiche gilt für S3 und S9 zwischen Olympiastadion und Spandau. Westlich Zoologischer Garten sind S5 und S7 jedoch völlig frei planbar, auch eine komplette Einstellung des Zugverkehrs auf dem Abschnitt Potsdam Hbf – Westkreuz (der dann durch Busse ersetzt werden müsste) wäre prinzipiell erlaubt. Dem wirken wir mithilfe der Zielfunktion wie in §2.5 besprochen entgegen, die ein Minderangebot verglichen mit dem Regelfahrplan stark bestraft. Für diese Fallstudie gewichten wir die Minimierung der Angebotsreduzierung 100-mal stärker als die Minimierung der Anzahl der Wenden.

Zum Schluss besprechen wir noch einige Fahrplanparameter. Der Fahrplan der S-Bahn Berlin wiederholt sich alle 20 Minuten, wird aber mit einer Auflösung von 0,1 Minuten geplant. Daher planen wir in ganzen Zehntelminuten mit der Periode T =200. Für Fahrtkanten verwenden wir die Fahrzeit des Regelfahrplans, mit einem Zuschlag für Fahrten ins Gegengleis. Haltekanten haben eine untere Schranke von 30 Sekunden und eine obere von 5 Minuten. Die Mindestwendezeit beträgt 2 Minuten, dies ist allerdings nur mit einem zweiten Lokführer möglich. Die Mindestzugfolgezeit h beträgt einheitlich 2,5 Minuten, die Räumungszeit ist ortsabhängig.

3.4 Lösungsberechnung und -beschreibung

Unter Berücksichtigung der in §3.3 angegeben Planungsparameter können wir nun das Optimierungsmodell aus §2.5 anwenden, um einen integrierten Linien-, Fahr- und Umlaufplan für das Westkreuz-Szenario zu berechnen. Dazu benutzen wir eine am Zuse- Institut Berlin eigens für Baufahrplanoptimierung entwickelte Python-Bibliothek, die eine komfortable Eingabe der Daten ermöglicht. Die Software stellt das gemischt-ganzzahlige Programm auf, das mit Gurobi 10.0.2 [3] als Solver auf einer Intel Xeon E3-1270 CPU mit 3,8 GHz und 32 GB RAM gelöst wird.

Das erste Ergebnis ist ernüchternd: Es dauert knapp 8 Stunden Rechenzeit (wall time), bis eine zulässige Lösung gefunden wird, und erst nach weiteren eineinhalb Stunden wird eine optimale Lösung erreicht. Um diese Zeit zu verringern, konstruieren wir basierend auf dem in Tabelle 3 angegebenen Routing im Planungsgraphen eine Startlösung:

Tabelle 3: Routing für eine Startlösung unter Ausnutzung von Bahnhöfen (Charlottenburg, Grunewald, Olympiastadion) mit ausreichenden Kehrkapazitäten und unter Vermeidung des eingleisigen Abschnitts der S7 rund um Westkreuz

Das Routing von Tabelle 3 ist das Ergebnis einer simplen Heuristik: Die mitten in ihrem Laufweg von der baubedingten Sperrung betroffene S7, welche nur unter Inkaufnahme eines eingleisigen Betriebs durchgebunden werden können würde, wird stattdessen aufgeteilt und zu Bahnhöfen mit genügend Kehrkapazität zurückgezogen. Hingegen wird die S5 zu einem anderen durchgehend auf zweigleisigen Strecken erreichbaren Bahnhof mit genügend Kehrkapazität verlängert, der Rest ist wie im Regelfahrplan. So erhält dieses Routing auch größtenteils das Regelangebot, nur auf den Abschnitten Grunewald – Westkreuz und Westkreuz – Charlottenburg werden durch die Aufteilung der S7 jeweils 2 Fahrten pro Richtung in 20 Minuten weniger angeboten. Auf der Strecke Westkreuz – Olympiastadion gibt es sogar ein Mehrangebot, dies wird aber von der Zielfunktion vom Modell in §2.5 ignoriert.

Unsere Software kann ein solches Routing automatisch in eine echte Startlösung, also einen Fahr- und Umlaufplan, umwandeln. Dies dauert hier nur wenige Sekunden. Mit dieser Startlösung ist der Optimierungsprozess wesentlich schneller: Bereits nach knapp 15 Minuten wird ein Fahrplan gefunden, der die gleichen Bedienungsfrequenzen wie das Regelangebot bietet, allerdings mit zahlreichen getrennten Umläufen auf der S7. Nach bereits 45 Minuten endet die Rechnung mit einer optimalen Lösung.

Bild 5: Ein optimales Routing für das Westkreuz-Szenario mit gleichem Bedienungsstandard wie im Regelfahrplan. In dieser Abbildung stehen die Symbole der Linien S3 und S9 für jeweils eine Fahrt in eine Richtung innerhalb von 20 Minuten, für die Linien S5 und S7 – aufgrund des Befahrens des Gegengleises – für jeweils eine Fahrt in beide Richtungen innerhalb von 20 Minuten.

Die gefundene optimale Lösung (siehe Bild 5) hat keine gebrochenen Linien. Die S7 nutzt tatsächlich mit ihren beiden im Regelfahrplan geplanten Fahrten pro Richtung in 20 Minuten das nördliche Gleis zwischen Grunewald und Charlottenburg mit Kreuzung in Westkreuz. Aufgrund der zwischen Charlottenburg und Westkreuz bestehenden Fahrzeit von knapp unter zwei Minuten ist dies unter Einhaltung von Mindestzugfolge- und Räumungszeit möglich, obwohl zwischen Westkreuz und Charlottenburg noch die S3 und S9 Richtung Spandau dasselbe Gleis befahren. Nach einem ähnlichen Prinzip kann die S5 alle 10 Minuten auf dem südlichen Streckengleis bis Westkreuz geführt werden und dort am Bahnsteig kehren, die Verlängerung bis Olympiastadion wird damit unnötig. Die Kopplung der Zuggruppen E und EI bleibt dabei bestehen. Die Wendezeit beträgt 4 Minuten, sodass genug Zeit für den Führerstandswechsel bleibt und kein zusätzliches Fahrpersonal eingesetzt werden muss.

Dieser berechnete Fahrplan zeichnet sich zwischen Westkreuz und Charlottenburg durch eine sehr gleichmäßige Struktur und Aufteilung aller Fahrten aus. So verkehren auf beiden Gleisen alle 10 Minuten jeweils zwei Zugfahrten in der Regelfahrrichtung, sowie zusätzlich eine in der Gegenrichtung. Möglich wird der vollständige Erhalt des Regelangebots auf allen Linien aber nur durch lange Haltezeiten: Die Obergrenze von 5 Minuten wird bei der S7 in Grunewald und bei der S5 in Charlottenburg ausgeschöpft, um die Gegengleisfahrten zu ermöglichen.

4 Schlussbemerkungen

Die Optimierung von Taktfahrplänen hat in den vergangenen rund zwanzig Jahren nur eine eher begrenzte Anwendung in der Praxis der Angebotsplanung öffentlicher Verkehrsunternehmen finden können. Grundlegend anders verhält es sich bei der Optimierung von Fahrzeug- und Personaleinsatzplänen, wo mehrere kommerzielle Software- Produkte am Markt etabliert sind. Ein struktureller Unterschied besteht darin, dass zumindest für den Jahresfahrplan, bzw. gar für größere Umplanungen von Linienkonzepten, Taktfahrplanoptimierung nicht zuletzt aufgrund ihrer vergleichsweise seltenen Durchführung kaum als regelmäßig zu lösende Routineaufgabe aufzufassen ist.

Nicht zuletzt aufgrund der auch mindestens mittelfristig zu erwartenden hohen Instandhaltungsintensität von Schienennetzen verhält es sich bei der Erstellung von Baufahrplänen grundlegend anders, denn dabei handelt es sich um eine häufig wiederkehrende Aufgabe. Mit dem in der vorliegenden Arbeit genutzten innovativen Modell, welches die gerade im Kontext von Baufahrplänen kaum sinnvoll trennbaren Teilaufgaben Linienplanung, Fahrplanung, Gleisbelegung und Umlaufplanung integriert, wurde entsprechend eine Tür geöffnet, um Verfahren der Taktfahrplanoptimierung für die Praxis der Planung öffentlicher Verkehrsunternehmen zugänglicher zu machen.

Die in diesem Beitrag erstmals im Detail berichtete erfolgreiche Anwendung dieses Modells auf einen unmittelbar der Praxis entnommenen anspruchsvollen Planfall im Netz der Berliner S-Bahn kann dabei als Nachweis dafür angesehen werden, dass das integrierte Optimierungsmodell methodisch reif ist, künftig in der häufig durchzuführenden Erarbeitung von Baufahrplänen regelmäßig Anwendung finden zu können. Voraussetzung hierfür bleibt gleichwohl, dass die zahlreichen benötigten detaillierten Eingangsdaten den Optimierungsverfahren mittels passender Softwarelösungen auf effizientem Wege zugänglich gemacht werden.

5 Danksagung

Wir danken der DB Netz AG Region Ost, Bereich Fahrplan und Kapazitätsmanagement S- Bahn Berlin für die Bereitstellung von Daten und die sehr fruchtbare Zusammenarbeit.

6 Literatur

1. M. R. Bussieck, T. Winter, and U. T. Zimmermann (1997). Discrete optimization in public rail transport. Mathematical Programming 79(1), S. 415-444.
2. F. Fuchs, A. Trivella und F. Corman (2022). Enhancing the interaction of railway timetabling and line planning with infrastructure awareness. Transportation Research Part C: Emerging Technologies, 142:103805.
3. Gurobi Optimization, LLC (2022). Gurobi Optimizer Reference
4. L. Kroon et al. (2009). The New Dutch Timetable: The OR Revolution. Interfaces 39(1), 6-17.
5. C. Liebchen und R. H. Möhring (2007). The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables — and Beyond. Algorithmic Methods for Railway Optimization, Lecture Notes in Computer Science, S. 3-40. Springer.
6. B. Masing, N. Lindner und C. Liebchen (2022). Periodic Timetabling with Integrated Track Choice for Railway Construction Sites. ZIB-Report 22-26, Zuse-Institut Berlin.
7. B. Masing, N. Lindner und C. Liebchen (2023). Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice. 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Vol. 115, S. 5:1-5:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl.
8. J. Pachl (2013). Systemtechnik des Schienenverkehrs: Bahnbetrieb planen, steuern und sichern, 7. Aufl. Springer Vieweg.
9. J. Pätzold, A. Schiewe, P. Schiewe und A. Schöbel (2017). Look-Ahead Approaches for Integrated Planning in Public Transportation. 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). OpenAccess Series in Informatics (OASIcs), Vol. 59, S. 17:1-17:16. Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik, Dagstuhl.
10. S-Bahn Berlin GmbH. Zahlen und Fakten auf einen Blick.
    https://sbahn.berlin/das- unternehmen/unternehmensprofil/auf-einen-blick-zahlen-und-fakten, abgerufen am 09.2023.
11. P. Schiewe (2020). Integrated Optimization in Public Transport Planning. Springer Optimization and Its Applications, Vol. 160. Springer International Publishing, Cham.
12. P. Serafini und W. Ukovich (1989). A Mathematical Model for Periodic Scheduling Problems. SIAM J. Discrete Math 2(4), S. 550-581.
13. R. Wüst, S. Bütikofer, S. Ess, C. Gomez, A. Steiner, M. Laumanns und J. Szabó (2018). Periodic timetabling with ’track choice’-pesp based on given line concepts and mesoscopic infrastructure. Operations Research Proceedings 2018, S. 571-578. Springer.