Numerator: Schneller warten

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.

• 1
• | 2
• weiter

• 1. Teil: Schneller warten
• 2. Teil: Was hat das nun mit Sudoku zu tun?