Fotostrecke

Optimierter Fahrplan: Schneller warten

Foto: Wolfgang Kumm/ picture-alliance/ dpa

Numerator Schneller warten

O nein, schon wieder die U1 verpasst! Wer viel mit öffentlichen Verkehrsmitteln unterwegs ist, mag sich regelmäßig schwarz ärgern: Wieder nur die Rücklichter des Zugs gesehen, wieder warten. Dabei kann Bahnfahren ganz entspannt sein - dank moderner Mathematik.

Von einer U-Bahn in eine andere umzusteigen ist wie ein Lotteriespiel. Steht die Bahn schon da, kommt sie gleich oder erst in acht Minuten? Besonders ärgerlich ist es, wenn die Anschlussbahn einem direkt vor der Nase wegfährt. Hätte sie nicht noch 30 Sekunden warten können? Oder die andere Bahn eine Minute früher ankommen?

Diese Fragen haben sich die Planer der Berliner U-Bahn immer wieder gestellt. Sie wissen genau, dass ihre Fahrgäste zufriedener sind, wenn die Warte- und Umsteigezeiten möglichst kurz sind. Im Laufe der Jahre haben sie deshalb einen Fahrplan entwickelt, den sie für perfekt hielten. Allerdings nur so lange, bis ihn Mathematiker des Forschungszentrums Matheon der TU Berlin genauer unter die Lupe genommen haben.

Das Team von Christian Liebchen hat das Problem analysiert und festgestellt, dass der Fahrplan letztlich in das Gebiet der sogenannten Graphentheorie fällt. Die Aufgabe ähnelt damit auch der Suche nach einer Sudoku-Lösung oder der klassischen Frage, wie viele Farben man braucht, um die Länder einer Landkarte so einzufärben, dass aneinandergrenzende Staaten stets verschieden gefärbt sind.

"Es gibt keinen besseren Fahrplan"

Liebchen hat das U-Bahn-Problem in einen Graphen übersetzt, also ein komplexes Netzwerk aus Knoten und Verbindungslinien, das zunächst Abermilliarden von Lösungen besitzt. Durch geschicktes Ausprobieren und anschließendes Bewerten und Aussortieren von Lösungen konnte der eigens dafür entwickelte Algorithmus die Menge der in Frage kommenden Fahrpläne immer weiter eingrenzen, bis schließlich die optimale Lösung gefunden war. "Das Ergebnis ist nicht nur ein bisschen besser als der vorher genutzte Plan, es handelt sich um die exakte Lösung", erklärt Sebastian Stiller, der gemeinsam mit Liebchen an dem Projekt gearbeitet hat. "Wir haben bewiesen, dass es keinen besseren Plan gibt."

Seit 2005 fährt die Berliner U-Bahn in den für Umsteiger besonders kritischen Randzeiten so, wie es die Mathematiker ausgerechnet haben. In diesen Zeiten verkehren die Züge im Zehn-Minuten-Takt. Die mittlere Wartezeit beim Umsteigen hat sich durch den neuen Fahrplan von 2 Minuten 48 Sekunden auf 2 Minuten 30 Sekunden verkürzt. Der Anteil schneller Anschlüsse mit besonders kurzen Wartezeiten ist von 55 auf 60 Prozent gestiegen. Und was die Controller der Berliner Verkehrsbetriebe (BVG) besonders freute: Dank der neuen Planung wurde ein ganzer U-Bahn-Zug eingespart.

Wie ist dieses Kunststück geglückt? Das Prinzip des Graphen, den die Mathematiker genutzt haben, lässt sich sehr gut an einem extrem vereinfachten U-Bahn-Netz erklären, das aus nur zwei Linien mit je drei Haltestellen besteht. Die mittleren Stationen beider Linien sind identisch, hier können Fahrgäste umsteigen (siehe Fotostrecke oben). Die Linien verkehren nur in einer Richtung.

Minuten zählen statt Erbsen

Wir nehmen an, dass beide Linien in einem Vier-Minuten-Takt fahren. Wenn wir weiterhin annehmen, dass die U-Bahnen exakt eine Minute halten und die Fahrgäste beim Umsteigen von einer Linie zur anderen wegen des Weges exakt eine Minute brauchen, dann wird sofort klar, dass beide Linien besser nicht zugleich in der mittleren Station ankommen sollten. Sonst würden die Benutzer beider Linien nämlich immer ihre Anschlüsse so verpassen, dass sie drei Minuten warten müssten (der Weg von Bahnsteig zu Bahnsteig ist bereits abgezogen).

In welchem Abstand sollten die beiden Linien die Umsteigestation also erreichen? Denkbar sind eine, zwei oder drei Minuten. Was hat das für Konsequenzen für die Wartezeiten? Im ersten und im dritten Fall muss ein Teil der Fahrgäste zwei Minuten warten, bis die Anschlussbahn in die Station einfährt. Die anderen Umsteiger kommen nach einer Minute Weg auf dem anderen Bahnsteig an - und in diesem Moment rollt die U-Bahn auch ein. Wartezeit null Minuten.

Im Fall zwei, die Linien erreichen den Umsteigebahnhof im Abstand von zwei Minuten, beträgt die Wartezeit für Fahrgäste beider Züge immer eine Minute - auch hier ist die Wegzeit bereits abgezogen.

Was wäre dann die fairste Lösung? Wahrscheinlich würden sich die Planer für die Variante mit dem Zwei-Minuten-Abstand entscheiden. Allerdings ist die durchschnittliche Wartezeit in allen drei Fällen gleich: eine Minute.

Erweitert man diese simple Variante auch um Züge, die in der Gegenrichtung fahren, kommen weitere Umsteigeoptionen dazu.

Was hat das nun mit Sudoku zu tun?

An welcher Stelle kommt nun Graphentheorie ins Spiel? Die Berliner Mathematiker weisen jedem Knoten einfach eine Zahl zu. Diese besagt, zu welcher Minute sich ein U-Bahn-Zug genau an diesem Knoten befindet. In unserem simplen Modell startet der Zug der Linie 1 zur Minute null, der Knotenpunkt bekommt deshalb den Wert 0. Eine Minute später rollt er in der mittleren Station ein, der Knoten bekommt den Wert 1. Eine Minute später fährt er weiter - ein weiterer Knoten mit dem Wert 2. Und noch eine Minute später erreicht der Zug den Endbahnhof (Knoten = 3). Wir sehen, dass benachbarte, miteinander verbundene Knoten keinesfalls gleiche Zahlenwerte besitzen dürfen - ganz ähnlich wie beim Sudoku.

Analog weisen wir nun den Knoten der zweiten Linie Zahlenwerte zwischen 0 und 3 zu. Der Zug startet bei Minute 2, erreicht den mittleren Bahnhof bei Minute 3, fährt in Minute 4 weiter.

Zahlen größer als 3 dürfen in dem System jedoch nicht auftauchen, denn die Züge sollen ja im Vier-Minuten-Takt fahren. Was in Minute 4 in dem Netz passiert, ist deshalb identisch mit der Situation in Minute 0. Fährt ein Zug also in Minute 3 los und braucht eine Minute bis zur nächsten Station, dann kommt er dort in Minute 0 an. Mathematiker nennen diese Berechnungsmethode Modulo 4. Dabei wird der Rest aus der Division durch 4 ermittelt.

Wenn die Graphentheorie-Experten der TU Berlin die Umsteigezeiten minimieren wollen, dann suchen sie letztlich Lösungen, bei denen die Differenz der Knotenpunkt-Werte an den Umsteigepunkten möglichst klein ist - im Idealfall sogar null.

Man kann sich leicht vorstellen, wie komplex ein solcher Graph, also das System aus Knoten und Linien, wird, wenn das beschriebene Netz nicht nur aus zwei, sondern wie in Berlin aus neun Linien und 170 Stationen besteht. Hinzu kommen Nebenbedingungen, wie etwa jene, dass in der Station Wittenbergplatz zwei verschiedene Linien immer zugleich einfahren müssen, weil sie auf zwei Seiten desselben Bahnsteiges halten und die Leute in beide Richtungen umsteigen wollen.

Für die Lösung des Berliner Umsteigeproblems interessieren sich mittlerweile auch Verkehrsbetriebe in Potsdam und die Niederländische Eisenbahngesellschaft Nederlandse Spoorwegen. Der Mathematiker Christian Liebchen hat sich sogar neue, noch größere Ziele gesetzt. Er ist vom Matheon zur Deutschen Bahn gewechselt, um den Güterverkehr zu optimieren.