Busumlaufplanung optimieren und warum sich jeder eingesparte Bus rechnet

Vor jedem Fahrplanwechsel spielt sich in vielen Verkehrsunternehmen dieselbe Szene ab. Die Planung sitzt über Hunderten oder Tausenden Fahrten, schiebt Wendezeiten hin und her, prüft Depotkapazitäten, rechnet Leerfahrten nach und stellt am Ende fest, dass es in der Morgenspitze wieder einen Bus zu viel braucht. Oder zwei. Niemand weiß genau, ob es auch mit weniger gegangen wäre. Man weiß nur, dass der Plan funktioniert, und nach Wochen Arbeit ist das schon viel.

Wir arbeiten seit Jahren mit Verkehrsunternehmen, Verbünden und Bahnbetreibern an genau dieser Frage. Wie gut ist ein Umlaufplan wirklich, und wie viel steckt noch darin? Die ehrliche Antwort ist fast immer dieselbe. Es steckt mehr darin, als man mit freiem Auge sehen kann. In diesem Beitrag erklären wir, warum das so ist, wie mathematische Optimierung die Busumlaufplanung verändert und worauf Sie achten sollten, wenn Sie das Thema in Ihrem Unternehmen angehen.

Was Umlaufplanung eigentlich leistet

Der Fahrplan legt fest, wann welche Fahrt von wo nach wo führt. Die Umlaufplanung beantwortet die nächste Frage. Welcher Bus fährt welche Fahrten, in welcher Reihenfolge, und wie kommt er zwischen zwei Fahrten an den richtigen Ort? Ein Umlauf ist damit die Tagesaufgabe eines Fahrzeugs, vom Ausrücken aus dem Betriebshof über alle Linienfahrten und Leerfahrten bis zum Einrücken am Abend.

Klingt übersichtlich. Ist es aber nicht. Jede Fahrt hat eine Startzeit, einen Startort, eine Endzeit und einen Endort. Dazwischen liegen Mindestwendezeiten, Leerfahrten zu anderen Endstellen, Pausenplätze, Betriebshöfe mit begrenzter Stellfläche und Fahrzeugtypen, die nicht auf jeder Linie fahren dürfen. Ein Gelenkbus passt nicht durch jede Ortsdurchfahrt, ein Midibus reicht in der Schulspitze nicht aus, und ein Elektrobus muss irgendwann laden.

In der Fachliteratur heißt diese Aufgabe Vehicle Scheduling Problem. Sobald mehrere Betriebshöfe im Spiel sind, spricht man vom Multi Depot Vehicle Scheduling Problem. Beide gehören zu einer Klasse von Problemen, die mit wachsender Größe extrem schnell schwierig werden. Mathematiker nennen sie NP-schwer. Für die Praxis heißt das schlicht, dass man nicht einfach alle Möglichkeiten durchprobieren kann, weil es schon bei einem mittelgroßen Netz mehr Kombinationen gibt, als ein Computer in Jahrzehnten prüfen könnte.

Warum gute Planer trotzdem an Grenzen stoßen

Wir sagen das mit großem Respekt. Erfahrene Umlaufplanerinnen und Umlaufplaner leisten Erstaunliches. Sie kennen ihr Netz, wissen, wo es morgens staut, und haben Regeln im Kopf, die in keinem Handbuch stehen. Ihr Wissen ist unersetzlich, und jedes gute Optimierungsprojekt baut darauf auf.

Was ein Mensch aber nicht kann, ist Tausende Wechselwirkungen gleichzeitig im Blick behalten. Wer an einer Stelle zwei Fahrten neu verknüpft, verschiebt damit oft eine Kette von Anschlüssen an ganz anderer Stelle. Viele Planungswerkzeuge helfen hier mit Heuristiken, also mit Faustregeln, die schnell einen brauchbaren Plan liefern. Das Problem ist, dass niemand sagen kann, wie weit dieser Plan vom bestmöglichen entfernt ist. Es kann ein Prozent sein. Es können aber auch zehn Prozent sein.

Bei einem Bus, der pro Jahr je nach Region und Antrieb einen hohen fünfstelligen oder sechsstelligen Betrag an Fixkosten, Personal und Energie verursacht, ist dieser Unterschied kein akademisches Detail. Jeder Bus, der in der Spitze nicht gebraucht wird, ist Geld, das an anderer Stelle für mehr Angebot fehlen würde.

Die Stellschrauben einer guten Umlaufplanung

Bevor wir zur Methode kommen, lohnt sich ein Blick darauf, was eigentlich optimiert wird. In unseren Projekten tauchen immer wieder dieselben Hebel auf.

Fahrzeugbedarf in der Spitze

Der größte Kostentreiber ist fast immer die Zahl der Fahrzeuge, die in der Hauptverkehrszeit gleichzeitig unterwegs sein müssen. Wer hier einen oder zwei Umläufe einspart, spart Fahrzeuge, Stellplätze, Wartung und oft auch Personal.

Leerkilometer und Leerzeiten

Jede Fahrt ohne Fahrgäste kostet Energie, Verschleiß und Arbeitszeit. Leerfahrten lassen sich nie ganz vermeiden, aber ihre Summe hängt stark davon ab, wie geschickt Fahrten miteinander verknüpft werden. Das gilt auch für lange Standzeiten an Endstellen, die zwar keine Kilometer, aber Arbeitszeit und Fahrzeugzeit binden.

Depotzuordnung

Wenn mehrere Betriebshöfe zur Verfügung stehen, stellt sich die Frage, welcher Bus wo übernachtet. Eine gute Zuordnung verkürzt Aus- und Einsetzfahrten und entlastet Höfe, die an ihrer Kapazitätsgrenze arbeiten.

Fahrzeugtypen und Linienbindung

Nicht jeder Bus darf überall fahren. Länge, Höhe, Barrierefreiheit, Kapazität und Antrieb schränken die Möglichkeiten ein. Gleichzeitig kann es sinnvoll sein, Fahrzeuge linienübergreifend einzusetzen, statt jede Linie für sich zu planen. Wie stark man mischt, ist eine betriebliche Entscheidung, die ein gutes Modell als Parameter abbildet.

Robustheit

Ein Plan, der nur bei perfekter Pünktlichkeit funktioniert, ist in der Praxis wertlos. Pufferzeiten an kritischen Stellen sind deshalb kein Luxus, sondern Teil der Optimierung. Die Kunst liegt darin, Puffer dort einzuplanen, wo Verspätungen erfahrungsgemäß entstehen, und nicht pauschal überall.

Wie mathematische Optimierung funktioniert, ganz ohne Formeln

Die Grundidee ist einfacher, als sie klingt. Wir beschreiben das Planungsproblem als mathematisches Modell. Dieses Modell besteht aus drei Teilen.

Erstens aus Entscheidungen. Für jede mögliche Verknüpfung zweier Fahrten gibt es eine Variable, die sagt, ob diese Verknüpfung genutzt wird oder nicht. Zweitens aus Regeln, die wir Nebenbedingungen nennen. Jede Fahrt muss genau einmal gefahren werden, Wendezeiten müssen eingehalten werden, ein Depot darf nicht mehr Fahrzeuge aufnehmen, als Platz ist, und so weiter. Drittens aus einem Ziel. Meist ist das eine Kostenfunktion, die Fahrzeuge, Leerkilometer, Standzeiten und weitere Faktoren mit Ihren tatsächlichen Kostensätzen gewichtet.

Dieses Modell übergeben wir einem sogenannten Solver. Das ist eine hochspezialisierte Software, bei uns häufig Gurobi, die mit Verfahren wie Branch and Bound und Schnittebenen systematisch den Lösungsraum durchsucht. Der entscheidende Unterschied zu einer Heuristik ist, dass der Solver nicht nur eine gute Lösung findet, sondern gleichzeitig eine untere Schranke berechnet. Aus beiden ergibt sich die sogenannte Optimalitätslücke. Sie sagt Ihnen schwarz auf weiß, wie weit der gefundene Plan höchstens vom theoretisch besten Plan entfernt ist. Wenn diese Lücke bei null liegt, ist der Plan unter den gegebenen Regeln nachweislich optimal.

Diese Form der Modellierung nennt sich gemischt ganzzahlige lineare Optimierung, abgekürzt MILP. Wer tiefer einsteigen möchte, findet eine ausführlichere Erklärung auf unserer Seite zur MILP-Modellierung und in unserem Überblick zur mathematischen Optimierung.

Wenn das Problem sehr groß wird

Bei großen Netzen mit vielen Tausend Fahrten und mehreren Betriebshöfen stößt auch der beste Solver irgendwann an Rechenzeitgrenzen. Dann greifen wir zu Verfahren, die das Problem geschickt zerlegen. Column Generation etwa erzeugt nur jene Umläufe, die überhaupt eine Chance haben, im optimalen Plan vorzukommen, statt alle denkbaren Varianten aufzuzählen. Andere Dekompositionsverfahren teilen das Netz in Teilprobleme, die sich einzeln lösen und wieder zusammensetzen lassen.

Wo selbst das nicht reicht, kombinieren wir exakte Verfahren mit Heuristiken. Ein heuristischer Rahmen wählt dabei immer neue Ausschnitte des Plans, und der Solver optimiert diese Ausschnitte exakt. Solche hybriden Ansätze verbinden Geschwindigkeit mit messbarer Qualität. Welche Methode passt, entscheiden wir nicht nach Vorliebe, sondern nach Größe und Struktur Ihres Netzes.

Ein Beispiel aus der Praxis

In einem unserer Projekte betrieb ein Verkehrsunternehmen ein Busnetz mit 48 Linien und mehreren Betriebshöfen. Die Umläufe wurden bis dahin weitgehend manuell geplant, ein vollständiger Planungslauf dauerte rund zwei Tage. Wir haben das Problem als Multi Depot Vehicle Scheduling Problem formuliert, mit Fahrzeugtypen, Depotkapazitäten, Wartungsintervallen und den Ladezyklen der Elektrobusse als Nebenbedingungen.

Das Modell umfasste rund 48.000 binäre Entscheidungsvariablen und über 12.000 Nebenbedingungen. Gelöst wurde es in wenigen Sekunden, der vollständige Planungslauf dauerte 4,2 Sekunden. Die Leerkilometer sanken deutlich, die Auslastung der Flotte stieg, und die CO₂-Emissionen gingen um rund 340 Tonnen pro Jahr zurück. Die Investition hatte sich nach etwa acht Monaten amortisiert. Die Details finden Sie in unseren Case Studies.

Mindestens so wichtig wie die Einsparung war ein anderer Effekt. Weil ein Planungslauf nur noch Sekunden dauert, kann die Planung Varianten vergleichen. Was passiert, wenn wir die Wendezeit an einer Endstelle um zwei Minuten verlängern? Was kostet es, wenn Linie 12 künftig nur noch mit Gelenkbussen fährt? Solche Fragen lassen sich jetzt beantworten, bevor man sie entscheidet, und nicht erst danach.

Elektrobusse verändern die Spielregeln

Mit der Umstellung auf Elektrobusse wird die Umlaufplanung noch einmal deutlich anspruchsvoller. Ein Dieselbus fährt den ganzen Tag, ein Elektrobus hat eine begrenzte Reichweite, die zudem von Temperatur, Topografie und Heizung abhängt. Ladezeiten müssen in den Umlauf eingebaut werden, Ladepunkte im Depot und an Endstellen sind knapp, und teure Lastspitzen beim Netzbetreiber gilt es zu vermeiden.

Wer Umläufe und Ladeplanung getrennt betrachtet, verschenkt viel. Deshalb optimieren wir beides in einem gemeinsamen Modell. Wie das funktioniert und warum es für die Beschaffung neuer Fahrzeuge so wichtig ist, lesen Sie in unserem Beitrag zur E-Bus-Umlaufplanung und Ladeplanung sowie auf der Seite zum E-Bus Lademanagement.

Umlauf und Dienst gehören zusammen

In vielen Unternehmen folgt auf die Umlaufplanung die Dienstplanung. Erst werden die Fahrzeuge verplant, dann das Personal. Das ist nachvollziehbar, aber nicht ideal. Denn ein Umlauf, der aus Fahrzeugsicht optimal ist, kann für die Dienstplanung ungünstig sein, etwa weil Ablösepunkte fehlen oder Pausen nicht sinnvoll unterzubringen sind.

Die integrierte Fahrzeug- und Personalplanung betrachtet beides gleichzeitig. Das ist mathematisch deutlich schwieriger, aber gerade in Zeiten des Fahrermangels lohnt sich der Aufwand. Mehr dazu in unserem ausführlichen Beitrag zur Dienstplanung im ÖPNV und auf der Seite zur Dienst- und Personalplanung.

Vom Plan in den Betrieb

Ein Umlaufplan ist eine Absicht. Der Betrieb ist die Wirklichkeit. Ein Bus fällt aus, eine Straße wird gesperrt, eine Veranstaltung sorgt für volle Fahrzeuge. Gute Planung denkt diese Abweichungen mit. Die Pufferzeiten im Plan helfen bei kleinen Verspätungen, für größere Störungen braucht es eine Echtzeitdisposition, die in Sekunden neue Varianten berechnet.

Und dann ist da noch die Werkstatt. Fahrzeuge müssen regelmäßig gewartet werden, und wenn die Umlaufplanung die Wartungsfenster nicht kennt, entstehen Engpässe. Eine abgestimmte Werkstattdisposition sorgt dafür, dass Fahrzeuge dann in die Werkstatt kommen, wenn sie im Umlauf am wenigsten fehlen.

Muss dafür das Planungssystem getauscht werden?

Das ist eine der häufigsten Fragen, die wir hören, und die Antwort ist fast immer nein. Die meisten Verkehrsunternehmen arbeiten mit etablierten Planungssystemen, in denen Fahrpläne, Netze und Betriebsdaten gepflegt werden. Diese Systeme haben ihre Berechtigung, und niemand möchte sie ohne Not ersetzen.

Unsere Optimierung setzt deshalb meist als eigenständiges Modul an. Die Daten kommen über Standardformate wie VDV 452, GTFS oder vorhandene Schnittstellen, das Ergebnis geht auf demselben Weg zurück. Wie das technisch aussieht und welche Varianten es gibt, beschreiben wir im Beitrag Optimierung ergänzen statt Planungssystem tauschen und auf der Seite zur Datenintegration.

Fünf Fehler, die wir in Umlaufplänen immer wieder sehen

Aus vielen Potenzialanalysen kennen wir Muster, die fast überall auftauchen. Keines davon ist ein Vorwurf an die Planung. Sie entstehen fast zwangsläufig, wenn Menschen mit begrenzter Zeit ein sehr großes Problem lösen müssen.

Linien werden isoliert geplant

Viele Pläne entstehen Linie für Linie. Das ist übersichtlich, verschenkt aber Möglichkeiten. Ein Bus, der auf Linie 3 an der Endstelle zwanzig Minuten wartet, könnte in dieser Zeit eine Fahrt auf Linie 5 übernehmen, die dort ohnehin in der Nähe beginnt. Eine linienübergreifende Optimierung findet solche Verknüpfungen systematisch.

Wendezeiten sind historisch gewachsen

Manche Wendezeit wurde vor Jahren festgelegt, als der Straßenverkehr anders aussah oder eine Baustelle die Fahrzeit verlängerte. Niemand hat sie seither überprüft. Wenn Wendezeiten aus aktuellen Ist-Daten abgeleitet werden, entstehen Pläne, die gleichzeitig robuster und effizienter sind.

Depotgrenzen werden als unverrückbar behandelt

Oft ist jeder Linie ein fester Betriebshof zugeordnet. In der Optimierung zeigt sich regelmäßig, dass eine flexiblere Zuordnung Aus- und Einsetzfahrten deutlich verkürzt. Ob man das umsetzt, ist eine betriebliche Entscheidung. Man sollte aber wissen, was sie kostet.

Fahrzeugtypen werden zu streng getrennt

Wenn jede Fahrt nur mit genau einem Fahrzeugtyp gefahren werden darf, sinkt die Flexibilität. Häufig wären auf vielen Fahrten mehrere Typen zulässig. Ein Modell, das diese Wahlmöglichkeiten kennt, braucht in der Spitze oft weniger Fahrzeuge.

Die Kosten sind nicht bekannt

Das klingt überraschend, ist aber häufig. Wie viel kostet eine Stunde Standzeit im Vergleich zu einem Leerkilometer? Wie viel ist ein eingesparter Bus pro Jahr wert? Ohne diese Zahlen lässt sich kaum sinnvoll abwägen. Deshalb erarbeiten wir mit Ihnen zu Beginn ein Kostenmodell, das in die Zielfunktion einfließt.

Welche Daten wir für eine Potenzialanalyse brauchen

Viele Unternehmen befürchten, dass für eine Optimierung erst ein großes Datenprojekt nötig ist. Das ist selten der Fall. Für eine erste Analyse reichen in der Regel ein Export des Fahrplans mit allen Fahrten, die Netzdaten mit Haltestellen und Fahrzeiten zwischen den Endstellen, die aktuellen Umläufe zum Vergleich, die Fahrzeugflotte mit Typen und Einsatzbeschränkungen sowie die Betriebshöfe mit ihren Kapazitäten.

Die meisten Planungssysteme können diese Daten in einem Standardformat wie VDV 452 exportieren. Wo Ist-Daten aus der Betriebsleitstelle vorliegen, nutzen wir sie zusätzlich, um Fahrzeiten und Wendezeiten realistischer abzubilden. Alles Weitere, etwa Kostensätze oder betriebliche Sonderregeln, erarbeiten wir gemeinsam in den ersten Workshops.

So läuft ein Projekt bei uns ab

Kein Projekt gleicht dem anderen, aber einige Schritte wiederholen sich.

Am Anfang steht eine Potenzialanalyse. Wir nehmen einen bestehenden Fahrplan und Ihre aktuellen Umläufe und rechnen nach, was unter denselben Regeln möglich wäre. Das gibt Ihnen eine belastbare Zahl, bevor Sie größere Entscheidungen treffen.

Danach folgt die gemeinsame Modellierung. Hier sitzen unsere Mathematikerinnen und Mathematiker mit Ihren Planern zusammen und schreiben die Regeln auf, auch die ungeschriebenen. Das ist oft der spannendste Teil, weil dabei Wissen sichtbar wird, das bisher nur in Köpfen existierte.

Dann kommt die Parallelphase. Für einen oder mehrere Fahrplanperioden entstehen Pläne in beiden Welten, die klassisch erstellten und die optimierten. So sieht Ihr Team, wo die Unterschiede liegen, und kann Vertrauen aufbauen. Erst danach geht das System in den Regelbetrieb.

Und schließlich bleibt die Entscheidung immer beim Menschen. Das System macht Vorschläge, zeigt Alternativen und begründet sie. Freigeben tut Ihre Planung. Das ist uns wichtig, und es ist auch die Grundlage dafür, dass solche Werkzeuge im Alltag wirklich genutzt werden.

Förderung und Finanzierung

Digitalisierungs- und Optimierungsprojekte im Verkehrssektor sind in vielen Fällen förderfähig, sowohl auf Landes- und Bundesebene als auch über europäische Programme. In Österreich kommen zudem Forschungsförderungen der FFG infrage, wenn ein Projekt neue methodische Fragen aufwirft. Wir unterstützen bei der Auswahl und Einreichung, mehr dazu unter Fördermittel und Einreichung und FFG-Forschungsprojekte.