Intelligente Instandhaltungsplanung für die Schieneninfrastruktur der DB InfraGo

Anstelle kurzfristiger Eingriffe in den Fahrplan, welche den regulären Betrieb unterbrechen, verfolgt die DB InfraGO einen neuen Ansatz. Die Idee: Im Vorfeld geplante Sperrzeiten des Zugbetriebs werden als feste Zeiträume, in denen Instandhaltungsarbeiten stattfinden sollen, in die Fahrpläne integriert. Diese festen Zeitfenster erlauben es, Instandhaltungsmaßnahmen planbar und mit geringerer Störung des Fahrbetriebs durchzuführen. Jedoch bringt diese neue Planungsweise auch Herausforderungen mit sich, insbesondere für die Planungsmitarbeiter der DB InfraGO, die dafür verantwortlich sind, die verfügbaren Sperrzeiten möglichst effizient zu nutzen.

Das Ziel besteht darin, aus dem Vorrat erforderlicher Instandhaltungsmaßnahmen auf dem insgesamt 33.000 km langen Schienennetz für einen bestimmten Streckenabschnitt diejenigen auszuwählen und zu kombinieren, die die Sperrzeit optimal ausnutzen. Dabei müssen zahlreiche betriebliche, technische und fachliche Randbedingungen, die sich aus der nachgelagerten Planung und Durchführung der Maßnahmen ergeben, beachtet werden, welche die Kombinierbarkeit der Maßnahmen untereinander einschränken.

Modellierung des Optimierungsproblems als “Rucksack”

Diese Problemstellung lässt sich als eine Variante des sogenannten Rucksackproblems modellieren. Das Rucksackproblem ist ein klassisches Optimierungsproblem aus der Informatik und Mathematik. Es zielt darauf ab, eine optimale Auswahl von Objekten zu treffen, die in eine begrenzte Menge an Kapazitäten passt. Stellen Sie sich vor, Sie wollen einen Rucksack mit einer festen Traglast optimal packen. Aus einer Menge von Gegenständen müssen Sie jene auswählen, die in den Rucksack passen und gleichzeitig den maximalen Nutzen bringen. Übertragen auf das Problem der Instandhaltungsplanung bedeutet dies, dass die Sperrzeit als der begrenzte Rucksack betrachtet wird, in den möglichst viele nützliche Maßnahmen „verstaut“ werden müssen, ohne dass die Kapazität überschritten wird. Das Ergebnis der Optimierung – der gepackte Rucksack – sind sogenannte Instandhaltungsbündel.

Dabei handelt es sich um die Kombinationen aus jeweils einer Sperrzeit und den dazu passenden Instandhaltungsmaßnahmen. In der Umsetzung der realen Problemstellung werden dabei sämtliche verfügbaren Sperrzeiten und Instandhaltungsmaßnahmen betrachtet.

Gegenwärtig gibt es keine exakte Lösung in endlicher Zeit

Das Rucksackproblem ist ein klassisches Beispiel für ein NP-hartes Problem (nicht-polynomiell). Bei NP-harten Problemen gibt es keine bekannte Möglichkeit, in sehr großen Suchräumen eine exakte Lösung in polynomieller Zeit zu berechnen oder auch alle möglichen Kombinationen der Objekte (in diesem Fall Instandhaltungsmaßnahmen) systematisch zu prüfen. Für kleine bis mittelgroße Problemgrößen bietet das Branch-and-Bound-Verfahren (BB) einen Ansatz zur Ermittlung von exakten Lösungen. Darüber hinaus gibt es heuristische und metaheuristische Ansätze wie den genetischen Algorithmus (GA), die auch große Problemgrößen bearbeiten können, die allerdings nur näherungsweise optimale Lösungen bieten.

Eine Annäherung an die Lösung findet sich daher durch die Verwendung exakter Verfahren oder meta-/ heuristischer Ansätze

Aus diesem Grund wurde eine Lösung auf Basis des BB entwickelt. Auch ein alternativer Ansatz unter Verwendung eines genetischen Algorithmus wurde untersucht. Das BB ist besonders geeignet, wenn es darum geht, eine exakte Lösung für die Vielzahl an Nebenbedingungen und Einschränkungen zu finden. Er prüft systematisch alle möglichen Kombinationen, um eine optimale Lösung zu berechnen. Dabei kann ein signifikanter Teil des Lösungsraums logisch ausgeschlossen werden, ohne die einzelnen Ausprägungen tatsächlich zu berechnen. Allerdings stößt er bei sehr großen Datensätzen schnell an seine Grenzen und liefert kein Ergebnis.

Der GA bietet hier eine ergänzende Möglichkeit. Der GA ist eine Metaheuristik, die auf dem Prinzip der natürlichen Selektion basiert. Er sucht nicht nach einer einzigen, exakten Lösung, sondern generiert eine Vielzahl von Lösungen und verbessert diese schrittweise durch Evolution.

Letztendlich konnte das Problem von unserem Team der #zukunftsfabrik mit dem Branch-and-Bound-Verfahren in zufriedenstellender Zeit gelöst werden. Grundlegend war die Optimierung der Planungsorganisation, so dass die Problemgröße – die Anzahl der möglichen Kombinationen – beherrschbar blieb. Durch eine sinnvolle Strukturierung der Daten und eine gezielte Einschränkung der zu berechnenden Instandhaltungsmaßnahmen auf spezifische Zeiträume und Streckenabschnitte war es uns möglich, die Komplexität des Problems zu reduzieren. Dadurch können wir auch mit der exakten Methode effiziente Lösungen generieren, ohne dass die Berechnungszeiten unvertretbar anstiegen.

Ausblick: Wie wird das Sperrzeit-System umgesetzt und wann voraussichtlich im Deutsche Bahn Netz angewendet?

Das System wird derzeit bereits von den Planungsmitarbeitern der DB InfraGO testweise genutzt, um wertvolles Feedback von den Experten einzuholen und so das Verbesserungspotenzial hinsichtlich der Planungsqualität voll auszuschöpfen. Auf Grundlage dieser Rückmeldungen können Anpassungen vorgenommen werden, um den Planungsprozess noch effizienter zu gestalten. Zukünftige Ausbaustufen der Software beinhalten die Integration der Verfügbarkeitsprüfung von Personal, Maschinen – wie zum Beispiel Gleisarbeitsfahrzeuge – und benötigtem Material bei der Erstellung der Instandhaltungsbündel. Zudem wird eine intelligente Verwertung der abgelehnten Bündelvorschläge durch die Planungsmitarbeiter angestrebt, um zu verhindern, dass bereits durch Mitarbeiter verworfene Vorschläge erneut generiert werden. Diese Funktionen werden dazu beitragen, die Planungsprozesse weiter zu optimieren und den Einsatz der verfügbaren Ressourcen effektiver zu gestalten.

Fazit & Kontakt

Wir konnten durch die Entwicklung und den Einsatz einer modernen Optimierungsmethode eine Möglichkeit finden, den Planungsprozess zu automatisieren. Dies leistet einen Beitrag zur Effizienzsteigerung in der Instandhaltungsplanung und damit zu einem zuverlässigeren und störungsfreieren Bahnverkehr. Ebenfalls wird der Wechsel zu systematischen Sperrzeiten für die Instandhaltung nachhaltig unterstützt.

Titelbild/ Header: © Copyright: Deutsche Bahn AG / Oliver Lang

Verweise: