02.07.2004 - MATHEMATIK

Busse und Bahnen besser planen

Mathematiker optimieren den Öffentlichen Nahverkehr

Reinhard Huschke

Foto: Schaake

Nehmen wir an, wir hätten zwei Buslinien zu planen: Linie 1 fährt von Aheim nach Bedorf, Linie 2 von Bedorf nach Ceburg. Das heißt, die beiden Linien berühren sich in Bedorf, wo die Fahrgäste zwischen beiden Linien umsteigen können. Erreicht der Busfahrer von Linie 1 sein Ziel, soll er dann nach der Pause an der Endhalte- stelle wieder nach Aheim zurückfahren? Oder vielleicht besser sofort auf Linie 2 Richtung Ceburg weiterfahren, um einerseits die Wartezeit in Bedorf und andererseits einen zusätzlichen Bus auf Linie 2 einzusparen? Wenn er aber auf Linie 2 „übergeht“ (so nennen das die Verkehrsplaner), könnte es sein, dass er nicht rechtzeitig in Ceburg ankommt, um seine tariflich vorgeschriebene Pause von mindestens 15 Minuten einzulegen. Dann muss er unterwegs abgelöst werden, was wiederum einen weiteren Fahrer erfordert; außerdem muss der ablösende Fahrer irgendwie zur Ablösestelle gelangen. 

Schon an diesem einfachen Beispiel wird klar, welche Komplikationen die Einsatzplanung von Fahrzeugen und Personal selbst in kleinen Ver- kehrsbetrieben mit sich bringt. Dies gilt erst recht für Groß- stadtnetze wie das der Berliner Verkehrsbetriebe (BVG), wo wochen- tags 28.000 Busfahrten auf 160 Linien organisiert werden müssen. Kein Mensch kann ein solches Planungsproblem noch überschauen, geschweige denn die optimale Kombination aller Fahrzeug- und Fahrereinsätze herausfinden. Deshalb werden die Planungen bei den meisten Verkehrsbetrieben schon lange mit Computerhilfe gemacht.

Aber es geht noch eleganter: Seit Mitte der Neunzigerjahre ent- wickeln Prof. Dr. Martin Grötschel und seine Kollegen am Berliner ZIB „Scientific Computing“ Rechenverfahren – so genannte Algorithmen –, mit denen sich derartige Optimierungsprobleme binnen Stunden oder sogar Minuten vollautomatisch lösen lassen: „Wir schauen uns die Anforderungen und Bedingungen in einem Verkehrsbetrieb genau an und bilden sie in einem mathematischen Modell ab. Mathematisch gesehen ist zum Beispiel die Fahrzeugumlaufplanung ein so genann- tes Mehrgüterflussproblem, die Dienstplanung für die Fahrer ein Pfadüberdeckungsproblem. Für die Lösung solcher Probleme haben wir schnelle Algorithmen entwickelt.“

Bereits 1994 starteten erste Versuche von „Busumlaufoptimierungen“ in Hamburg, weitere große und kleine deutsche Verkehrsbetriebe folgten dem Beispiel. Allein im Berliner Betriebshof Spandau, einem von zehn Busdepots der Hauptstadt, konnten nach Angabe der BVG durch die mathematische Optimierung der Fahrzeugeinsätze 38 Bus- se (d.h. fast jeder fünfte Bus) und 377 Betriebsstunden eingespart werden, ohne den Service für die Fahrgäste einzuschränken – eine erhebliche Kostenreduktion, wenn man bedenkt, dass der Einsatz eines Busses nach betriebs- wirtschaftlicher Rechnung mit 150.000 bis 200.000 Euro jährlich zu Buche schlägt.

Nach der Umlaufplanung nahmen sich die Berliner Mathematiker der Dienstplanung an. Dieses Problem ist weitaus komplizierter, weil es dabei, wie sich Grötschels Mitarbeiter Dr. Ralf Borndörfer ausdrückt, „nicht um die Planung von Maschinen, son- dern von Menschen geht“.  Tatsächlich sind die Menschen in- soweit anspruchsvol- ler, als bei der Pla- nung der Fahrer- dienste eine Vielzahl von Regeln zu be- rücksichtigen sind, die sich zudem von Ver- kehrsbetrieb zu Ver- kehrsbetrieb unter- scheiden. Dazu gehö- ren zum Beispiel Ar- beits-, Lenk- und Pau- senzeiten und tarif- liche Vergütungsre- geln für unterschiedliche Dienstarten. „Da kommen je nach Betriebsgröße schnell Gleichungssysteme mit Millionen oder sogar Milliarden von Variablen zusammen“, erklärt Ralf Borndörfer, „die sogar Großrechner in die Knie zwingen könnten. Unser Ziel war jedoch, schlanke Rechenverfahren zu entwickeln, die auf jedem handelsüblichen Laptop laufen. Und  das ist uns schließlich gelungen.“

Auf der Basis des mathematischen Modells entwickelte Grötschels Institut in einer Industriepart- nerschaft mit dem Berliner Software-Unternehmens IVU eine Software, die heute bei mehreren deutschen Verkehrsbetrieben im Einsatz ist. Die Software-Module „Umlaufop- timierung“ und „Dienstplanoptimierung“ sind inzwischen so ausgefeilt, dass sie laut Ralf Borndörfer eine optimale Umlaufplanung und eine nahezu (zu 99 %) optimale Dienstplanung hinbekommen, und das für ganz unterschiedlich strukturierte Verkehrsbetriebe. Modellrechnun- gen für verschiedene deutsche Verkehrsunternehmen haben gezeigt, dass fast immer ein paar Prozent Einsparungen drin sind, und in manchen Fällen haben sie bereits überraschende Planungsvarianten zu Tage gefördert, auf die ein menschlicher Planer nie gekommen wäre.

Trotzdem sind nicht alle von diesen Erfolgen begeistert. Manch einem kommunalen Verkehrs- betrieb sind Strukturänderungen wenig willkommen, und verständ- licherweise gibt es häufig auch große Skepsis von Seiten des Fahrpersonals und der Betriebs- räte. Auf diese Vorbehalte stoßen nicht nur die ZIB-Forscher, die manchmal wie die „McKinseys der Mathematik“ betrachtet werden; auch IVU-Vertriebsleiter Andreas Langenhan, der den Einsatz der Optimierungssoftware in der Praxis begleitet, bestätigt diesen Eindruck: „Nach den vielen schlechten Erfahrungen mit so genannten Beratern stehen natürlich auch wir erst einmal unter Rationalisierungsverdacht.“

Dass die Erkenntnisse der Mathe- matiker in den – notorisch klam- men – städtischen Verkehrsbe- trieben zuallererst fürs Sparen genutzt werden, ist kein Geheim- nis. Andreas Langenhan legt den Akzent jedoch lieber auf die mit der Optimierung verbunden Chancen: „Neben den betriebs- wirtschaftlichen Vorteilen eröffnet die mathematische Optimierung den Verkehrsbetrieben neue Spielräume: Die Planer können erstmals in kürzester Zeit ver- schiedene Szenarien durchrech- nen und vergleichen.“ Bisher dauert die Dienstplanerstellung Tage oder sogar Wochen, sodass man froh ist, rechtzeitig zum Fahrplanwechsel wenigstens ei- nen funktionierenden Plan fertig zu haben.

Letztlich geht es heute mehr denn je darum, ein gutes Verkehrsan- gebot zu möglichst geringen Kosten auf die Beine zu stellen. Eine wirtschaftliche Arbeitsweise ist die Voraussetzung für die kommunalen Verkehrsbetriebe, sich im liberalisierten europäischen Wettbewerb um Verkehrsleistungen behaupten zu können. So gesehen kann die mathematische Optimierung den Betrieben nicht nur dabei helfen, Spielräume zu erweitern, sondern überhaupt eigene Spielräume zu behalten.

Mehr im Internet:
Projektbeschreibung 
Zuse-Institut-Berlin
DFG-Forschungszentrum Mathematik für Schlüsseltechnologien 
IVU Taffic Technologies AG