Mathematische Fahrplanoptimierung für die Berliner U-Bahn. 

Niemand wartet gern, schon gar nicht in öffentlichen Verkehrsmitteln. Für die Planer der Verkehrsbetriebe ergibt sich daraus ein Dilemma: Lassen sie zum Beispiel einen U-Bahn-Zug im Bahnhof stehen, um einen Anschluss abzuwarten, werden die Fahrgäste im Zug ungeduldig; fährt die Bahn aber ohne zu warten weiter, ärgern sich diejenigen, die ihren Anschluss verpassen. 

Vor allem nach 20 Uhr und an Sonntagen, wenn die Züge nur alle zehn Minuten oder noch seltener verkehren, müssen die Wartezeiten geschickt austariert werden, um möglichst viele Fahrgäste zufrieden zu stellen. "Die Erfahrung zeigt, dass Wartezeiten von mehr als fünf Minuten bereits als lang empfunden werden", sagt Heinrich Coenen, Leiter der Fahr- und Dienstplanung bei der Berliner U-Bahn. "Wenn man im Zug sitzt, empfindet man sogar eine Minute schon als unangenehm - manche laufen dann zur Tür, weil sie denken, irgendetwas sei nicht in Ordnung." 

Vor dem Fahrplanwechsel im Dezember 2004 warteten die U-Bahnen am Hermannplatz und am Zoo bis zu 3,5 Minuten. "Das ist eine Ewigkeit", sagt Coenen. Trotzdem: Coenen und seine Mitarbeiter waren auch damals schon mit ihrer Arbeit zufrieden. Bei den 48 wichtigsten Anschlüssen (von insgesamt 170) garantierte der Fahrplan Wartezeiten von nicht mehr als fünfeinhalb Minuten. Deshalb reagierten die Planer der Berliner Verkehrsbetriebe (BVG) auch zurückhaltend, als ihnen Mathematiker der Technischen Universität (TU) Berlin vor zwei Jahren vorschlugen, den Fahrplan mit mathematischen Methoden zu verbessern. "Wir waren skeptisch und haben uns, ehrlich gesagt, nicht allzu viel von der Sache versprochen", gibt Coenen heute zu. Dennoch bekamen Rolf Möhring und sein Doktorand Christian Liebchen von der TU-Arbeitsgruppe "Kombinatorische Optimierung und Graphenalgorithmen" die Chance, den Spätverkehrsfahrplan für das Jahr 2005 am Computer zu berechnen. 

Der Berliner U-Bahn-Fahrplan gehört damit europaweit zu den ersten Plänen, die mit mathematischen Methoden optimiert wurden. Vergleichbare Projekte laufen zurzeit bei den Verkehrsbetrieben in Basel und Zürich. Bis 2004 hatten Coenens Mitarbeiter den Fahrplan von Hand erstellt. Dazu wurden zunächst die Abfahrtzeiten an den wichtigsten Umsteigebahnhöfen festgelegt, etwa am Mehringdamm, Wittenbergplatz und Alexanderplatz. Die Zeiten wurden dann leicht nach vorne oder hinten verschoben, um auch an den weniger frequentierten Umsteigepunkten - zum Beispiel an der Spichernstraße und dem Fehrbelliner Platz - gute Anschlussverbindungen zu gewährleisten. Doch solche kleinen Änderungen können weit reichende Konsequenzen nach sich ziehen. "Wenn man Pech hat, führt die Verbesserung an einer Stelle woanders zu Verschlechterungen", sagt Ehrfried Hummel von der BVG. 

Die Mathematiker machten es ganz anders. Dabei war der erste Schritt der mühsamste: Die Umsteigezeiten an allen Bahnhöfen, die erfahrene Fahrplaner wie Ehrfried Hummel im Blut haben, mussten per Stoppuhr erfasst und in ein Computersystem eingegeben werden. Dann wurden alle Anschlüsse nach Wichtigkeit - als Maß dafür gilt die Zahl der betroffenen Fahrgäste - geordnet. Erst nach diesen Vorarbeiten konnten Rolf Möhring und Christian Liebchen ihr Optimierungsprogramm laufen lassen. Dabei mussten sie eine Bedingung der BVG beachten: Sie durften aus Kostengründen keine zusätzlichen Züge einsetzen. Das Ergebnis verblüffte die Fahrplanexperten bei der BVG. Im Vergleich zum bisherigen Fahrplan für den Spätverkehr bot der mathematisch optimierte Fahrplan 103 statt bisher 95 Anschlüsse mit einer Wartezeit von maximal fünf Minuten. 

Im Durchschnitt senkten Möhring und Liebchen die Wartezeiten im Spät- und Sonntagsverkehr um zirka acht Prozent auf durchschnittlich 2,5 Minuten, und kein U-Bahn-Zug muss nun länger als zweieinhalb Minuten im Bahnhof stehen. Zwei Beispiele: Am Bahnhof Zoo trafen die Züge der sich hier kreuzenden Linien 2 und 9 vor dem Fahrplanwechsel etwa gleichzeitig ein: Sie mussten jeweils bis zu drei Minuten im Bahnhof stehen bleiben, um den Fahrgästen genug Zeit zum Umsteigen zu geben. Jetzt kommen die Züge der beiden Linien um fünf Minuten versetzt an, sodass sie nicht mehr warten müssen. Und am Fehrbelliner Platz haben die BVG-Kunden nun fünf Minuten, um von der U7 in die U1 zu wechseln. Im vergangenen Jahr fuhr ihnen der Anschlusszug meist vor der Nase weg. 

Besonders überrascht war man bei der BVG, dass der neue Fahrplan mit einem kompletten Zug weniger auskam als der alte. "Dieses Ergebnis hätten wir nicht für möglich gehalten", räumt Heinrich Coenen ein. Auch wenn sie mit ihrer Methode den U-Bahn-Fahrplan verbessern konnten, so loben die Mathematiker doch die bisherige Arbeit von Coenen und Hummel: "Bei den 48 wichtigsten Anschlüssen konnten wir kaum etwas verbessern", sagt Christian Liebchen. Nur bei den untergeordneten Umsteigepunkten habe der Computer die Wartezeiten deutlich verkürzen können. Mit dem neuen Fahrplan lieferten die Mathematiker auch noch eine Art Qualitätssiegel mit: Sie bewiesen, dass sie unter den gegebenen Bedingungen die optimale Lösung gefunden haben. "Ich denke, es ist nicht nur aus mathematischer Sicht eine feine Sache, wenn man weiß, dass es für das System nicht besser geht", sagt Liebchen. Ehrfried Hummel bezweifelt allerdings, dass sich diese Begeisterung auch den Fahrgästen vermitteln lässt: "Die Fahrgäste interessieren sich überwiegend für die Situation an ihren eigenen Umsteigebahnhöfen. Verbesserungen woanders sind ihnen herzlich egal." 

Daher hielten sich die BVG-Experten auch nach dem Fahrplanwechsel im vergangenen Dezember noch einige Zeit mit öffentlichen Kommentaren zurück. Sie wollten erst abwarten, ob es mehr Probleme und Beschwerden geben würde als ohnehin nach jedem Fahrplanwechsel üblich sind. Inzwischen ist aber klar, dass die mathematische Optimierung so gut funktioniert hat, dass nur Detailänderungen nötig waren. Der nächste Fahrplan, der am 11. Dezember in Kraft tritt, wird daher dem aktuellen ganz ähnlich sein. Inzwischen überlegt man bei der BVG sogar, auch die Fahrpläne anderer Verkehrsnetze - etwa der Nacht- und Metrolinien - mathematisch zu verbessern. 

(Das Original im Archiv der Berliner Zeitung ist leider nicht mehr zugänglich.)