Automatische Dispositionsunterstützung mit ADA-PMB

Mehr Verkehr auf der Schiene zu ermöglichen und gleichzeitig eine deutliche Verbesserung der Pünktlichkeit zu erzielen, sind die beiden wesentlichen Herausforderungen des Systems Schiene, sowohl für Eisenbahninfrastruktur- (EIU) als auch –verkehrsunternehmen (EVU). Um diesen Ansprüchen gerecht zu werden, konzentriert sich die DB Netz AG als EIU neben dem relativ langwierigen Ausbau der Infrastruktur und der Verbesserung ihrer technischen Verfügbarkeit vor allem auf Maßnahmen, welche die Fahrplanung und die Zugdisposition optimieren. Dieser Artikel bietet einen Einblick in die Möglichkeiten zur automatischen Unterstützung der Zugdisposition mit Algorithmen der mathematischen Optimierung in Kombination mit Künstlicher Intelligenz (KI). Vorgestellt wird auch ein laufender Pilot des Verfahrens Automatische Dispositionsassistenz auf Basis des Produktionsmodell Betrieb (ADA-PMB) in der Betriebszentrale S-Bahn Berlin der DB Netz AG.

Die Zugdisposition, im Folgenden kurz Disposition, ist der Prozess zur operativen Koordinierung der auf dem Netz verkehrenden Züge, zum Beispiel durch Zugreihenfolge- und Umleitungsentscheidungen. Sie ist abzugrenzen von der Steuerung der Ressourcen Personal, Triebfahrzeug und Wagen, welche durch die EVU disponiert werden. Auf EVU-Seite gibt es ebenfalls Aktivitäten im Bereich Disposition. So wurde im vergangenen Jahr von Erfolgen bei der Unterstützung der EVU-seitigen Disposition bei der S-Bahn Stuttgart mit einem auf maschinellem Lernen basierenden Ansatz berichtet.

Dispositionsunterstützung bei der DB Netz AG

Bei der DB Netz AG arbeitet das Team Algorithmik Betrieb seit über 10 Jahren an der algorithmischen Unterstützung der Zug- und Bereichsdisposition im Betrieb. Die zwei herausstechenden Herausforderungen bei der Disposition sind:

dass die Entscheidungen binnen kurzer Zeit getroffen werden müssen, während die Züge bereits auf dem Netz unterwegs sind, und
dass sich eine Dispositionsentscheidung nicht nur an dem Ort, an dem sie umgesetzt wird, auswirkt, sondern auch an weiter entfernten Orten für weitere Züge erhebliche Folgen haben kann. Sie fordert von Menschen folglich Konzentration, einen guten Überblick und große Erfahrung.

Eine weitere Besonderheit bei der Disposition seitens der DB Netz AG ist ihre Verpflichtung als Infrastrukturbetreiber zur Diskriminierungsfreiheit. Das bedeutet, alle EVU müssen den gleichen Zugang zum Schienennetz erhalten und dürfen weder bevorzugt noch benachteiligt werden. Um dies zu gewährleisten, müssen alle Dispositionsentscheidungen objektiv nachvollziehbar getroffen werden. Dadurch scheidet für die DB Netz AG ein Großteil der auf maschinellem Lernen basierenden Ansätze aus, da diese in der Regel als „Black Box“ ausgelegt sind, deren Entscheidungen nicht oder nicht vollständig erklärt werden können.

Anfangs wurde zur Dispositionsuntersützung ein heuristischer Ansatz im Verfahren Konflikterkennung und Konfliktlösung (KE/KL) verwendet, welcher iterativ Konflikte für jeweils zwei Züge auf Basis definierter Regeln löst. Diese Regeln wurden vorab mit Expert*innen aus dem Betrieb der DB Netz AG festgelegt sowie in einem einjährigen Feldtest 2011/2012 mit den Betriebszentralen (BZ) getestet und weiterentwickelt. Dabei konnte gezeigt werden, dass KE/KL eine sinnvolle Unterstützung für die Disposition ist. Auch wenn KE/KL nicht in die produktive Nutzung übernommen wurde, konnten die entwickelten Algorithmen für die Zuglaufregelung (ZLR) genutzt werden und versorgen seit 2018 Fahrassistenzsysteme für Triebfahrzeuge mit Geschwindigkeitsfahrempfehlungen.

Den nächsten Entwicklungsschritt bildet die gleichzeitige Betrachtung aller Züge in einem Betrachtungsbereich mit dem Verfahren Automatische Dispositionsassistenz auf Grundlage des Produktionsmodell Betrieb (ADA-PMB). ADA-PMB ermöglicht es, die Folgen einer Dispositionsmaßnahme auf mehr als einen Zug gleichzeitig zu betrachten und so zu besseren Ergebnissen zu gelangen. Dies ist allerdings mit einer deutlich größeren Anforderung an die Verarbeitungskapazität verbunden, da dazu wesentlich mehr Daten gleichzeitig zu verarbeiten sind. Dadurch wird der mögliche Betrachtungsbereich limitiert. Eine Gegenüberstellung der Lösungen einer beispielhaften Dispositionssituation mittels der 2-Zug-Konfliktlösung und der Lösung bei gleichzeitiger Betrachtung aller Züge illustriert den Vorteil von ADA-PMB in Abbildung 1.

Abbildung 1: 2-Zug-Konfliktlösung und simultane Lösung (Quelle: DB Netz AG)

ADA-PMB baut auf der bereits für KE/KL entwickelten Versorgung mit Live-Daten aus den BZ auf und nutzt für die simultane Lösung einen Optimierungsansatz. Dazu werden die Eingangsdaten bestehend aus Infrastrukturverfügbarkeitsinformationen, Fahrplänen und Zug-Ist-Meldungen in einem Präprozess geprüft und in ein mathematisches Modell überführt. Eine Standard-Optimierungssoftware findet dann eine möglichst optimale beziehungsweise die optimale Lösung, welche die Summe der Verspätung für alle Züge im Betrachtungsbereich minimiert. Dies führt auf einem transparenten Weg zu einer optimierten Lösung und erfüllt damit die Anforderungen an die Diskriminierungsfreiheit. Schließlich werden in einem Postprozess aus dem gelösten Gleichungssystem für Menschen verständliche Dispositionsempfehlungen generiert. Dieser Prozess ist in Abbildung 2 dargestellt.

Abbildung 2: Elemente von ADA-PMB (Quelle: DB Netz AG/Böttcher 2019, S. 15)

Pilotierung von ADA-PMB in der BZ S-Bahn Berlin

Um die Praxistauglichkeit von ADA-PMB zu testen, wird das Verfahren seit 2020 in der DB Netz-BZ für die S-Bahn Berlin pilotiert. Die verwendeten Dispositionsempfehlungen und Algorithmen wurden in enger Abstimmung mit der BZ schrittweise in den Piloten eingeführt. Im April 2022 wurden die letzten geplanten Anforderungen der BZ fertiggestellt. Der für den Piloten, ebenfalls in Zusammenarbeit mit der BZ, gewählte Betrachtungsbereich ist in Abbildung 3 dargestellt. Er reicht von Wartenberg, Ahrensfelde und Biesdorf bis zum Beginn der „Stadtbahn“ am Ostbahnhof. Hier werden Empfehlungen zur Zugreihenfolge an Einfädelungen und für Gleiswechsel gegeben. Für endende Züge wird zusätzlich empfohlen, ob diese am Bahnsteig oder in der Kehranlage wenden sollen. Insgesamt wird so die Disposition im Betrachtungsbereich für fünf S-Bahnlinien mit rund 1.170 Zugfahrten pro Tag unterstützt.

Abbildung 3: Pilotbereich von ADA-PMB mit optimierten Dispositionsempfehlungen (Quelle: DB Netz AG/Karte: Wikipedia)

Die Dispositionsempfehlungen werden dem Bereichsdisponenten Ost/West auf einem bestehenden BKU-Rechner als Kacheln in einer browserbasierten Web-App angezeigt. Eine solche Kachel und die Bedienmöglichkeiten sind in Abbildung 4 dargestellt. Die Dispoempfehlungen sind in der App nach der verbleibenden Zeit zur Umsetzung gereiht, so dass die jeweils als nächste umzusetzende Empfehlung oben steht. Eine Dispositionsempfehlung besteht aus der Angabe zu Betriebsstelle(n), den relevanten Zügen, der Handlungsempfehlung, wie in der Abbildung 4 eine „Reihenfolgeempfehlung“ und der verbleibenden Zeit zur Abstimmung mit den Fahrdienstleiter*innen. Über die Buttons „Daumen hoch“ und „Daumen runter“ können Disponent*innen freiwillig ein anonymes Feedback geben und so zur weiteren Verbesserung des Verfahrens beitragen.

Abbildung 4: Dispositionsvorschläge und Bedienmöglichkeiten von ADA-PMB (Quelle: DB Netz AG)

Neben dieser Feedbackmöglichkeit steht das Projektteam im engen Kontakt mit den Nutzer*innen in der BZ. So konnten schnell kleine „Kinderkrankheiten“ überwunden werden. Im Rahmen des Austausches bekam die DB Netz AG ein konstruktives und positives Feedback (Abbildung 5). Diese heben einerseits die Bedeutung des gewählten, partizipativen Ansatzes hervor. Durch die frühe und offene Einbindung konnte eine gute Akzeptanz für ADA-PMB geschaffen werden. Gleichzeitig zeigen die Rückmeldungen auch, dass das die Dispositionsempfehlungen aus der Praxis als sinnvoll und hilfreich bewertet werden. Dies spricht für das Potenzial des Verfahrens.

Abbildung 5: Rückmeldungen aus der BZ zu ADA-PMB (Quelle: DB Netz AG)

Ausblick

Bei Erfolg des Piloten ist ein weiterer Einsatz in der BZ S-Bahn Berlin beabsichtigt. Gleichzeitig ist geplant, ADA-PMB auch an weiteren Einsatzorten mit Mischverkehren, statt nur S-Bahnverkehr weiter zu erproben. Wenn sich das Verfahren auch dort als hilfreich für die Disposition erweist, können weitere Pilotstandorte relativ schnell hinzugenommen werden, da der Präprozess grundsätzlich mit den Daten aller BZ funktioniert und die Optimierung ortsunabhängig ist. Es wäre einzig die Qualität der Eingangsdaten, insbesondere der Modellierung der Infrastruktur, zu prüfen und wahrscheinlich punktuell zu korrigieren, da ADA-PMB hier höhere Anforderungen an die Genauigkeit stellt als bei der rein manuellen Disposition. Bereits in Arbeit ist eine Schnittstelle, um ADA-PMB auch nach PRISMA-Redesign weiter mit Daten zu versorgen. In Abstimmung mit den Pilotbereichen könnten zudem weitere Dispositionsempfehlungstypen entwickelt werden.

Parallel dazu wird im Team der Algorithmik Betrieb an einer Beschleunigung der Verarbeitungszeit von ADA-PMB gearbeitet, welche entscheidend ist für die Größe des räumlichen und zeitlichen Betrachtungsbereiches. Dabei werden neben einer Optimierung des Programmcodes und der Modellierung auch Heuristiken und unterstützend Ansätze aus dem Bereich des maschinellen Lernens erprobt. Diese erfolgt stets unter Berücksichtigung der Anforderung zur Diskriminierungsfreiheit.

Das nächste Ziel ist, einen gesamten Streckendispositionsbereich gleichzeitig zu betrachten. Ideal wäre es eine simultane, netzweite Optimierung im Sinne eines globalen Optimums zu erreichen. Diese wird allerdings wahrscheinlich nicht, oder zumindest nur in Zukunft mittels dann leistungsfähigerer Quantencomputer möglich sein. In Zusammenarbeit mit dem Quantencomputerteam des DB Skydeck in Berlin wurde bereits in einer gemeinsamen Untersuchung festgestellt, dass die Modellierung von ADA-PMB mit einer quantencomputergestützten Optimierung kompatibel ist. Die Anzahl der in Quantencomputern momentan verfügbaren Qubits, welche deren Rechenleistung bestimmen, ist allerdings noch zu gering. Daher ist bis auf weiteres bei der Auswahl der Pilotbereiche jeweils ein sinnvoller Schnitt zu finden und gegebenenfalls ist eine Kombination aus unterschiedlichen, optimierungs- und heuristikbasierten Ansätzen zu wählen.

Mittelfristig ist eine Aufnahme von Dispositionsempfehlungen direkt in das Dispositionssystem LeiDis-D der DB Netz AG in Diskussion. Hierfür liefern ADA-PMB und alle anderen gerade in Erprobung befindlichen Ansätze wertvolle Erkenntnisse und möglicherweise bereits die technische Grundlage.

Quellen

Böttcher, Jochen: Künstliche Intelligenz und mathematische Optimierung für eine automatische Disposition, Deine Bahn 11/2019: 10-15.

Große, Stefan/Schröder, Alexander/Weidner, Tibor: Die Grünen Funktionen der Zuglaufregelung, Deine Bahn 11/2016: 14-17.

Koenen, Jens: Bahn bringt Künstliche Intelligenz aufs Gleis, Handelsblatt (26.5.2021). Online unter: www.handelsblatt.com/unternehmen/handel-konsumgueter/schienenverkehr-bahn-bringt-kuenstliche-intelligenz-aufs-gleis/27222608.html (Abruf 16.07.2022).

Hoffmann, Michael T./Böttcher, Jochen: Entwicklung und Einführung der Zuglaufregelung, Deine Bahn 10/2018: 6-13.

o.V.: Warum Schienenprojekte in Deutschland so lange dauern, Handelsblatt (3.10.2021). Online unter: www.handelsblatt.com/politik/deutschland/verkehrspolitik-warum-schienenprojekte-in-deutschland-so-lange-dauern/27672336.html (Abruf 05.03.2022).

o.V.: Künstliche Intelligenz macht die Bahn pünktlicher und zuverlässiger, Eisenbahn International 5/2021. Online unter: https://eisenbahn-international.com/news/41346-k%C3%BCnstliche-intelligenz-macht-die-bahn-p%C3%BCnktlicher-und-zuverl%C3%A4ssiger (Abruf 16.07.2022).

Pänke, Ingo/Klimmt, Andreas: Vernetzung von Technologie und Anwenderwissen, Deine Bahn 3/2012: 44-47.

Richta, Hannah Noriko: Big Data und Prognostik im Schienenverkehr: Trends und Herausforderungen, Deine Bahn 4/2021: 23-29.

Rudin, Cynthia/Radin, Joanna: Why Are We Using Black Box Models in AI When We Don’t Need To? A Lesson From an Explainable AI Competition, Harvard Data Science Review, 1(2) 2019. Online unter: https://hdsr.mitpress.mit.edu/pub/f9kuryi8/release/7 (Abruf 16.07.2022).