Automated Resource Planning im Bahnbetrieb und die Mathematik hinter integrierter Planung

Wenn ein Fahrplan steht, beginnt die eigentliche Arbeit erst. Für jeden Zug müssen ein passendes Triebfahrzeug, ausreichend Wagen, eine Triebfahrzeugführerin oder ein Triebfahrzeugführer und bei Personenzügen das Bordpersonal bereitstehen. Und zwar nicht irgendwann, sondern auf die Minute genau am richtigen Ort. Die ÖBB planen und steuern täglich rund 7.000 Züge. Bei dieser Größenordnung wird die Ressourcenplanung zu einer der anspruchsvollsten Aufgaben, die es in der Logistik überhaupt gibt.

Lange Zeit wurde diese Aufgabe so gelöst, wie man große Probleme eben löst. Man zerlegt sie. Erst die Fahrzeuge, dann das Personal. Erst die Jahresplanung, dann die Wochenplanung, dann der Tag. Erst die eine Region, dann die nächste. Das funktioniert, hat aber einen hohen Preis. Niemand sieht mehr das Ganze.

Genau hier setzt der Gedanke des Automated Resource Planning an. In diesem Beitrag erklären wir, was damit gemeint ist, welches mathematische Problem sich dahinter verbirgt, warum es so schwer zu lösen ist und was es braucht, um integrierte Planung in einem großen Bahnbetrieb wirklich umzusetzen. Und wir erzählen, welche Rolle Hex und die Anexia Gruppe dabei spielen und spielen können.

Was die ÖBB mit ARP vorhaben

Die ÖBB haben 2020 das konzernweite Programm Automated Resource Planning ins Leben gerufen, kurz ARP. Die Vorarbeiten reichen weiter zurück. Laut der Projektbeschreibung, mit der Hex 2021 beim VCÖ-Mobilitätspreis ausgezeichnet wurde, wurde der Aufbau des Programms bereits seit 2017 in Zusammenarbeit mit der Universität Klagenfurt und Hex vorangetrieben.

Das Ziel ist klar formuliert. Die bisher sequenzielle und nach Phasen und Regionen getrennte Planung soll durch eine rollierende und integrierte Planung ersetzt werden. Trasse, Fahrzeug und Personal sollen gemeinsam und laufend geplant werden, nicht mehr nur auf einen Stichtag wie den Fahrplanwechsel im Dezember hin. Harald Ponweiser, der als Chief Product Owner für ARP verantwortlich ist, hat das Ziel so beschrieben, dass die Auslastung verbessert und die Passgenauigkeit der Schichten erhöht werden soll.

Das Programm hat zwei Stränge. Der eine ist eine konzernweit einheitliche Standardsoftware für Fahrzeug-, Schicht- und Einsatzplanung. Für diese Software haben die ÖBB im Herbst 2023 den Zuschlag an T-Systems und Goal Systems vergeben, mit der Lösung GoalRail und einer Vertragslaufzeit bis 2031. Der andere Strang heißt SHARP, Service Hub ARP. Dort entstehen automatisierte, optimierte Planungsunterstützung und Simulation auf Basis einheitlicher Daten und künstlicher Intelligenz. Zu SHARP gehören Optimierungsprojekte für den Lokeinsatz, für die Einsatzplanung der Triebfahrzeugführer und für das Bordservicepersonal, die in einem Fachbeitrag der ÖBB unter den Kürzeln LEO, TEO und BEO beschrieben wurden.

Bemerkenswert ist, wie offen die ÖBB den Grund für all das benennen. Das System Bahn hat in den vergangenen Jahrzehnten so stark an Komplexität gewonnen, dass selbst die besten Planerinnen und Planer es nicht mehr in seiner Gesamtheit überblicken können. Gleichzeitig beruht gute Planung in manchen Bereichen auf der jahrzehntelangen Erfahrung einzelner Menschen, und der anstehende Generationenwechsel droht, dieses Wissen mitzunehmen.

Warum Zerlegen so teuer ist

Um zu verstehen, was integrierte Planung bringt, hilft ein einfaches Beispiel. Die Lokplanung erstellt einen Umlauf, der mit möglichst wenigen Lokomotiven auskommt. Das ist aus ihrer Sicht optimal. Die Personalplanung bekommt diesen Umlauf und stellt fest, dass eine Lok an einem Bahnhof die Richtung wechselt, an dem kein Personal ablösen kann. Die Triebfahrzeugführerin muss also mitfahren, eine Gastfahrt einlegen oder dort übernachten. Aus Sicht der Personalplanung wäre ein anderer Lokumlauf mit einer zusätzlichen halben Stunde Standzeit viel besser gewesen.

In einem getrennten Prozess erfährt die Lokplanung davon nie. Beide Abteilungen haben ihre Aufgabe gut gemacht, und trotzdem ist das Gesamtergebnis schlechter als nötig. Multipliziert man diesen Effekt mit Tausenden Zügen, Hunderten Loks und Tausenden Mitarbeitenden, wird klar, wie viel Potenzial in der Integration liegt.

Harald Ponweiser hat einen weiteren wichtigen Gedanken formuliert. Ein Gesamtoptimum kann sich gerade dadurch ergeben, dass man die Planung auf den Engpass ausrichtet. Wenn Triebfahrzeugführer knapp sind, müssen die Schichtpläne so gut wie möglich sein, und andere Ressourcen werden bewusst weniger optimal geplant. Genau diese Abwägung kann eine sequenzielle Planung nicht leisten, eine integrierte schon.

Das mathematische Problem

Aus Sicht der Mathematik besteht die Ressourcenplanung im Bahnbetrieb aus mehreren bekannten Problemen, die jedes für sich bereits sehr schwierig sind.

Die Umlaufplanung der Fahrzeuge

Die Zuordnung von Triebfahrzeugen und Wagen zu Zugleistungen heißt in der Fachliteratur Rolling Stock Rotation Problem. Man stellt sich dafür ein Netzwerk vor, dessen Knoten Ereignisse an Bahnhöfen zu bestimmten Zeiten sind. Jede Zugleistung ist eine Kante, jede mögliche Leerfahrt, Abstellung oder Wende ebenfalls. Fahrzeuge fließen durch dieses Netzwerk. Weil es verschiedene Fahrzeugtypen gibt, die nicht beliebig austauschbar sind, handelt es sich um ein Mehrgüterflussproblem.

Dazu kommen viele Nebenbedingungen. Fahrzeuge müssen in bestimmten Abständen gewartet werden, sie haben Zulassungen für bestimmte Länder und Strecken, sie können gekuppelt oder getrennt werden, und manche Loks dürfen nur bestimmte Zuggewichte ziehen. Allein die Wartungsbedingungen machen das Problem deutlich schwerer, weil jedes Fahrzeug einen Zähler für Kilometer oder Tage mitführt, der nicht überschritten werden darf.

Die Dienstplanung des Personals

Aus den Fahrzeugumläufen ergeben sich Arbeitsblöcke, die das Personal übernehmen muss. Die Dienstplanung, im Englischen Crew Scheduling, bildet daraus Dienste, die alle arbeitszeitrechtlichen und tariflichen Regeln einhalten. Mathematisch ist das ein Set Partitioning Problem. Aus einer gewaltigen Zahl möglicher Dienste muss eine Auswahl getroffen werden, die jede Leistung genau einmal abdeckt und dabei möglichst wenig kostet.

Darauf folgt die Turnus- oder Dienstreihenfolgeplanung, im Englischen Crew Rostering. Hier werden die Dienste über Wochen zu Folgen verbunden, die einzelne Menschen fahren. Ruhezeiten, freie Wochenenden, Qualifikationen, Streckenkunde und Wünsche spielen eine Rolle. Und schließlich kommt die tägliche Disposition, in der auf Krankenstände, Verspätungen und Störungen reagiert wird.

Die Integration

Jedes dieser Probleme gehört zur Klasse der NP-schweren Probleme. Für die Praxis bedeutet das, dass es kein bekanntes Verfahren gibt, das jede Instanz in vertretbarer Zeit garantiert optimal löst, und dass der Aufwand mit der Größe explosionsartig wachsen kann. Ein kleines Beispiel macht das greifbar. Schon beim klassischen Rundreiseproblem gibt es bei acht Stationen 40.320 mögliche Reihenfolgen, bei 70 Stationen bereits eine Zahl mit rund hundert Stellen. Das ist mehr, als es Atome im beobachtbaren Universum gibt.

Integrierte Planung bedeutet nun, diese Probleme nicht nacheinander, sondern gemeinsam zu lösen. Die Kopplung entsteht über gemeinsame Ressourcen, über Ablösepunkte, über Gastfahrten des Personals und über die Frage, welche Leistungen überhaupt gefahren werden. Das Ergebnis ist ein Modell, das um Größenordnungen komplexer ist als jedes Teilproblem.

Rollierend statt stichtagsbezogen

Die zweite große Idee hinter ARP ist die rollierende Planung. Statt einmal im Jahr einen großen Plan zu erstellen, wird laufend über einen gleitenden Horizont geplant. Das hat einen enormen Vorteil, weil Baustellen, Krankenstände oder neue Aufträge sofort berücksichtigt werden können. Es stellt aber auch neue Anforderungen. Ein rollierender Plan darf sich nicht bei jeder Neuberechnung komplett ändern, denn Menschen brauchen Planbarkeit. Die Optimierung muss also nicht nur gut, sondern auch stabil sein. In der Forschung spricht man von robuster und wiederherstellbarer Planung, also von Plänen, die Störungen gut vertragen und sich mit wenigen Änderungen reparieren lassen.

Wie man so etwas überhaupt löst

Dass integrierte Ressourcenplanung in großen Bahnbetrieben heute möglich ist, verdankt sich mehreren Jahrzehnten Forschung im Operations Research. International bekannte Beispiele sind die Niederländischen Eisenbahnen, die 2008 für ihre mathematisch optimierte Fahrplan- und Ressourcenplanung den Franz Edelman Award erhielten, eine der wichtigsten Auszeichnungen für angewandte Optimierung, oder die Arbeiten zur Umlaufplanung im Fernverkehr, die etwa am Zuse-Institut Berlin gemeinsam mit der Deutschen Bahn entstanden sind.

Die Werkzeuge, die dabei zum Einsatz kommen, sind im Kern immer ähnlich.

Gemischt ganzzahlige Optimierung

Die Planungsprobleme werden als lineare Modelle mit ganzzahligen Entscheidungen formuliert. Leistungsfähige Solver durchsuchen den Lösungsraum mit Verfahren wie Branch and Bound und Schnittebenen und liefern neben einer Lösung auch eine Schranke, die zeigt, wie weit diese höchstens vom Optimum entfernt ist. Mehr dazu auf unserer Seite zur MILP-Modellierung.

Spaltengenerierung

Weil es viel zu viele mögliche Dienste oder Umläufe gibt, um sie alle aufzuzählen, erzeugt Column Generation nur jene, die das Gesamtergebnis verbessern können. Ein Masterproblem wählt aus, ein Teilproblem sucht gezielt nach neuen Kandidaten. Dieses Verfahren ist heute der Standard für große Dienstplanungsprobleme.

Zerlegung mit Rückkopplung

Um Fahrzeug- und Personalplanung zu koppeln, ohne ein unlösbar großes Modell zu bauen, nutzt man Verfahren wie die Lagrange-Relaxation oder die Benders Decomposition. Die Teilprobleme werden getrennt gelöst, tauschen aber Informationen aus, bis sich ein gemeinsames Optimum einstellt. Einen Überblick gibt die Seite zu Dekompositionsverfahren.

Constraint Programming

Für regelintensive Teile wie die Turnusplanung mit ihren Wochenend- und Ruhezeitregeln ist Constraint Programming oft besser geeignet als klassische lineare Modelle.

Hybride Verfahren und lernende Komponenten

Für sehr große Instanzen und für Echtzeitentscheidungen kombinieren wir exakte Verfahren mit Metaheuristiken und hybriden Ansätzen. Maschinelles Lernen kommt dort ins Spiel, wo Eingangsdaten unsicher sind, etwa bei Fahrzeiten, Verspätungen oder Krankenständen. Warum wir Prognose und Entscheidung bewusst trennen, erklären wir im Beitrag Operations Research oder KI.

Wissen aus Köpfen in Modelle übersetzen

So wichtig die Algorithmen sind, sie sind nicht der schwierigste Teil. Der schwierigste Teil ist, die Wirklichkeit richtig abzubilden. Die ÖBB beschreiben das sehr treffend. Die Planerinnen und Planer verfügen oft über ganz spezielles Wissen zu bestimmten Gegebenheiten, etwa wenn örtliche Besonderheiten die Planannahmen für Lokwenden verändern. Dieses Wissen muss in das Modell, sonst entstehen Pläne, die mathematisch optimal, aber praktisch unbrauchbar sind.

Philipp Hungerländer, der Gründer von Hex, bringt es so auf den Punkt. Für eine erfolgreiche Einführung eines Optimierungssystems braucht es ein sehr genaues Verständnis der Prozesse, die man abbilden will, damit die berechneten Lösungen auch umsetzbar sind. Die Eingangsdaten sind entscheidend, weil das System nur so gut sein kann wie das schwächste Glied in der Kette. Und neben den harten Faktoren zählen die weichen, also eine benutzerfreundliche Oberfläche und die Bereitschaft der Organisation, ihre Arbeitsweisen anzupassen.

Aus unserer Erfahrung heißt das konkret, dass Mathematikerinnen und Mathematiker gemeinsam mit den Planenden am Tisch sitzen müssen, und zwar über Wochen. Jede Regel wird aufgeschrieben, jede Ausnahme besprochen. Erste Ergebnisse helfen dabei enorm, weil erfahrene Planer beim Durchsehen sofort erkennen, wo eine Regel fehlt oder falsch verstanden wurde.

Standardsoftware und spezialisierte Optimierung

Eine häufige Frage in großen Programmen wie ARP ist das Verhältnis zwischen Standardsoftware und eigener Optimierungskompetenz. Beides hat seine Rolle. Eine Standardsoftware bildet Prozesse durchgängig ab, stellt Oberflächen für Hunderte Nutzerinnen und Nutzer bereit, verwaltet Stammdaten und sorgt für einheitliche Abläufe im ganzen Konzern. Das ist eine enorme Leistung, die man nicht selbst nachbauen möchte.

Gleichzeitig gibt es in jedem großen Bahnbetrieb Planungsprobleme, die so spezifisch sind, dass ein allgemeines Werkzeug sie nicht optimal lösen kann. Das kann die Lokplanung auf einer besonders komplexen Achse sein, die Disposition leerer Güterwagen im gesamten Netz oder die Einsatzplanung einer Berufsgruppe mit sehr speziellen Regeln. Für solche Aufgaben lohnen sich spezialisierte Optimierungsmodule, die über Schnittstellen mit dem führenden System zusammenarbeiten. Genau diese Arbeitsteilung spiegelt sich auch in der Struktur von ARP mit den beiden Strängen wider. Wie so eine Anbindung technisch aussieht, beschreiben wir im Beitrag Optimierung ergänzen statt Planungssystem tauschen.

Was Hex in diesem Feld bereits geleistet hat

Hex ist aus der Forschung entstanden. Philipp Hungerländer ist Associate Professor am Institut für Mathematik der Universität Klagenfurt und hat zwei Doktorate sub auspiciis abgeschlossen. Seine Forschung konzentriert sich auf kombinatorische und konvexe Optimierung, auf semidefinite und quadratische Optimierung und auf die Entwicklung exakter und heuristischer Algorithmen für große kombinatorische Probleme. Von 2015 bis 2017 arbeitete er mit einem sechsköpfigen Team der Universität Klagenfurt an Optimierungsprojekten für internationale Großunternehmen, unter anderem für eine der weltweit größten Supermarktketten, der das Team zu Einsparungen von mehreren Millionen Euro pro Jahr verhalf. 2017 wurde aus diesem Team die Hex GmbH.

Seit 2017 arbeitet Hex eng mit dem ÖBB-Konzern zusammen. Einige Stationen dieser Zusammenarbeit sind öffentlich dokumentiert.

In einem von der FFG geförderten Forschungsprojekt entwickelte ein Konsortium aus der Universität Klagenfurt, der TU Wien, der dwh GmbH, Hex und der Rail Cargo Austria ab 2018 Optimierungsalgorithmen für die Umlauf- und Routenplanung von Triebfahrzeugen im Güterverkehr, ergänzt um ein System zur Prognose von Zugverspätungen. Zum Zeitpunkt des Projektstarts setzte die Rail Cargo Austria rund 620 Triebfahrzeuge und 21.500 Güterwagen ein.

Erste Ergebnisse der Zusammenarbeit mit den ÖBB wurden 2020 mit dem Staatspreis Consulting und dem Constantinus Award in der Kategorie Digitalisierung und Internet of Things ausgezeichnet. Laut Projektbeschreibung lassen sich mit den Hex-Algorithmen Kosten und externe Effekte im ein- bis zweistelligen Prozentbereich senken, bei Logistik- und Personalkosten, die jeweils im dreistelligen Millionenbereich liegen. Durch die Zusammenarbeit entstanden zudem sechs postgraduale Forschungs- und Entwicklungsarbeitsplätze.

Im Forschungsprojekt TARO, das die ÖBB mit zahlreichen Partnern von 2020 bis 2023 durchführten, entwickelten die Rail Cargo Group, Anexia und die Universität Klagenfurt im Arbeitspaket Netzwerkoptimierung eine Software, die Bedarf und verfügbaren Bestand an Güterwagen abgleicht und dem Disponenten automatisch Vorschläge macht. Mit mathematischer Optimierung werden die Kilometer leerer Wagen minimiert. Laut ÖBB sollen die Entwicklungen in den Tagesbetrieb überführt werden. Mehr dazu im Beitrag zur Leerwagendisposition im Einzelwagenverkehr.

Im Projekt Anexia Rail entstanden gemeinsam mit den ÖBB und der Universität Klagenfurt Optimierungslösungen für Logistik- und Personaleinsatzplanung im Bahnbetrieb. Ein Planungslauf für Lokumläufe, der zuvor bis zu zehn Tage dauerte, lässt sich damit auf etwa zehn Sekunden verkürzen, mit einem Potenzial zur Senkung der CO₂-Emissionen um 15 bis 20 Prozent. Das Projekt wurde 2024 mit dem Kärntner Innovations- und Forschungspreis in der Sonderkategorie Grüne Technologien und 2026 mit dem TRIGOS Kärnten in der Kategorie Klimaschutz ausgezeichnet. Details finden Sie in den Beiträgen zum Forschungspreis 2024 und zum TRIGOS Kärnten 2026.

Was Hex für integrierte Planung leisten kann

Aus dieser Erfahrung heraus bieten wir Bahnunternehmen, Verkehrsverbünden und Infrastrukturbetreibern eine Reihe von Leistungen, die in Programmen wie ARP oder in kleineren Vorhaben gebraucht werden.

Potenzialanalysen mit echten Daten

Bevor investiert wird, rechnen wir nach, wie viel unter denselben Regeln möglich wäre. Wir nehmen reale Pläne, bauen ein Modell und vergleichen. Weil unsere Verfahren Optimalitätsschranken liefern, lässt sich nicht nur sagen, dass ein Plan besser ist, sondern auch, wie nah er am bestmöglichen liegt.

Modellierung und Algorithmen für die schwierigen Teilprobleme

Lokumläufe mit Wartungsbedingungen, Einsatzplanung von Triebfahrzeugführern und Bordpersonal, Leerwagendisposition, Schienenersatzverkehr, Werkstattplanung. Für diese Probleme entwickeln wir Modelle und Algorithmen, die auf die jeweiligen Regeln zugeschnitten sind. Einen Überblick über unsere Lösungen finden Sie auf den Seiten zum Schienenverkehr, zur Dienstplanung und zum Schienengüterverkehr.

Benchmarking und Qualitätssicherung

Auch wenn ein Unternehmen eine Standardsoftware einsetzt, lohnt sich ein unabhängiger Blick auf die Planungsqualität. Wir können Pläne gegen mathematische Schranken prüfen und zeigen, wo noch Potenzial liegt. Das hilft bei der Konfiguration ebenso wie bei der Entscheidung, wo sich spezialisierte Module lohnen.

Integration und Betrieb

Unsere Module binden sich über Schnittstellen an bestehende Systeme an und laufen auf Wunsch in der Cloud der Anexia Gruppe oder im eigenen Rechenzentrum. Mehr dazu unter Datenintegration und DevOps und Cloud.

Forschung und Förderung

Viele Fragen der integrierten Planung sind noch nicht abschließend gelöst, etwa die Robustheit rollierender Pläne. Gemeinsam mit Universitäten konzipieren und beantragen wir Forschungsprojekte, in Österreich häufig über die FFG. Mehr dazu unter FFG-Forschungsprojekte.

Was die Anexia Gruppe beiträgt

Hex ist eine hundertprozentige Tochter der Anexia Digital Engineering Group GmbH und damit Teil der Anexia Gruppe. Anexia wurde 2006 von Alexander Windbichler in Klagenfurt gegründet und beschäftigt heute rund 400 Menschen, mit Standorten in Klagenfurt, Wien, Graz, Karlsruhe und New York. Die Gruppe betreibt Rechenzentrumsstandorte an mehr als 100 Orten in 70 Ländern und ist nach ISO 9001, ISO 27001, ISO 27701 und ISO 14001 zertifiziert. Anexia engagiert sich zudem im Vorstand von CISPE, dem europäischen Verband der Cloud-Infrastruktur-Anbieter, für digitale Souveränität in Europa.

Für Bahnunternehmen bedeutet das, dass sie mathematische Spezialkompetenz und die ganze Breite eines Technologiepartners aus einer Hand bekommen können. Die Optimierungsmodelle entstehen bei Hex. Oberflächen, Apps und Schnittstellen entwickelt die Softwareentwicklung der Gruppe. Betrieben werden die Systeme in europäischen Rechenzentren unter europäischem Recht. Gerade für Unternehmen mit kritischer Infrastruktur ist diese Kombination ein wichtiges Argument.

Dazu kommt eine weitere Schwester in der Gruppe. Mit maas.maker betreibt Anexia eine Plattform für Bedarfsverkehr und Mikro-ÖV, die aus dem Projekt Anexia Drive hervorgegangen ist. Anexia Drive wurde 2022 mit dem Kärntner Innovations- und Forschungspreis in der Sonderkategorie Grüne Technologien ausgezeichnet. Für Bahnunternehmen ist das interessant, weil Bedarfsverkehre zunehmend als Zubringer zur Schiene geplant werden. Wie das funktioniert, zeigt der Beitrag zum Umstieg vom Bedarfsverkehr auf den öffentlichen Verkehr bei maas.maker.

Worauf es bei integrierter Planung ankommt

Aus vielen Projekten haben wir einige Erfahrungen mitgenommen, die für jedes Unternehmen gelten, das integrierte und rollierende Planung einführen will.

Erstens lohnt es sich, mit dem Engpass zu beginnen. Wo ist die knappste Ressource, und wo liegt der größte Hebel? In vielen Bahnbetrieben ist das heute das Personal. Wer dort zuerst optimiert und die übrigen Planungen daran ausrichtet, erzielt schnell messbare Ergebnisse.

Zweitens braucht es eine gemeinsame Datenbasis. Integrierte Planung funktioniert nur, wenn Fahrzeuge, Personal, Trassen und Infrastruktur in konsistenten Daten vorliegen. Diese Arbeit ist aufwendig, aber sie ist die Voraussetzung für alles andere.

Drittens muss die Planung stabil bleiben. Menschen brauchen verlässliche Dienstpläne. Ein rollierendes System muss deshalb Änderungen gezielt begrenzen und bestehende Zusagen schützen.

Viertens bleibt der Mensch in der Verantwortung. Die Optimierung rechnet Vorschläge, zeigt Alternativen und begründet sie. Freigeben und entscheiden tun die Planerinnen und Disponenten. Mit dem europäischen AI Act gewinnt dieser Grundsatz auch rechtlich an Bedeutung, gerade wenn Systeme Personal einplanen.

Und fünftens braucht es Geduld und Partnerschaft. Integrierte Planung ist kein Softwareprojekt, das nach einem Jahr abgeschlossen ist, sondern ein Umbau, der über viele Jahre wächst. Der Rahmenvertrag der ÖBB für die Standardsoftware läuft bis 2031. Dieser Zeitrahmen ist realistisch.

Für wen dieser Ansatz sonst noch passt

Nicht jedes Unternehmen hat die Größe der ÖBB. Die Prinzipien gelten aber auch für kleinere Eisenbahnverkehrsunternehmen, für Güterbahnen, für Verkehrsverbünde und für Busunternehmen. Wie sie sich in der Praxis anwenden lassen, beschreiben wir unter anderem in den Beiträgen zur Einsatzplanung des Bordpersonals, zur Lokdisposition im Güterverkehr und zur Planung des Fahrplanwechsels.