Entscheidungsintelligenz zur Steigerung der Produktivität: Der Konfliktlöser
Mikroskopische Konfliktprüfung in der Mittelfristplanung mit Viriato dank MoD
Ein wichtiges Ziel in der mittelfristigen Planungsphase (X-5 bis X-3) ist die Erstellung von Fahrplänen, die konfliktfrei oder zumindest nahezu konfliktfrei sind. Zu diesem Zeitpunkt im Planungsprozess – auch wenn noch etwa fünf bis drei Jahre bis zur Betriebsdurchführung verbleiben – steht die grundlegende Struktur des Fahrplans fest, und es wird entscheidend, dass die geplanten Züge ohne strukturelle Verspätungen gemäss diesem Fahrplan mit hoher Sicherheit tatsächlich fahrbar sind.
Bei der Arbeit im mittelfristigen Zeithorizont wird typischerweise ein Planungstool mit makroskopischen Infrastrukturmodell verwendet. Das Planungstool lässt hierbei wünschenswerterweise Lücken in der Detailplanung zu: Der Planer kann Trassen erstellen, die den High-Level-Anforderungen der Eisenbahnverkehrsunternehmen und den Planungsregeln der Infrastrukturbetreiber entsprechen. In dieser Phase konkretisieren sich die Infrastrukturdaten, und die Anzahl geplanter Züge nähert sich dem endgültigen Umfang. Es ist daher, im Hinblick auf die Fahrbarkeit, wichtig, die erstellten Trassen auf einem detaillierteren Niveau zu prüfen – unser Ansatz hierzu wurde in früheren Jahresberichten unter dem Begriff Microscopy-on-Demand (MoD) beschrieben.
Zusammengefasst ist MoD eine Methode, um in Viriato makroskopisch geplante Fahrpläne mit einem externen mikroskopischen Tool zu testen. Dieses kann die mikroskopischen Fahrwege der Züge bestimmen, die Fahrzeiten auf dieser Infrastruktur berechnen und prüfen, ob es auf mikroskopischer Ebene Konflikte gibt – alles, ohne die Viriato-Planungsansicht zu verlassen. Unabhängig davon, wie gut einzelne Züge makroskopisch geplant wurden, ist es unvermeidlich, dass es zu Konflikten zwischen Zügen kommt, die vor der finalen Freigabe des Plans gelöst werden müssen.
Produktivitätssteigerung durch automatisches Lösen der einfachen Konflikte
Wenn Planer mit einer grossen Anzahl solcher Konflikte konfrontiert werden, stellt sich die natürliche Frage: Können diese Konflikte mithilfe der Flexibilität des Fahrplans – also durch die verschiedenen betrieblichen, technischen oder kommerziellen Reserven – beseitigt oder zumindest minimiert werden? Durch die gezielte Veränderung des Ortes und der Grösse der im Fahrplan vorhandenen Reserven lassen sich viele Konflikte beseitigen, ohne dabei die Struktur des Fahrplans zu verändern. Lässt sich dieser Prozess automatisieren, können viele Konflikte im Voraus entfernt werden. Dies ermöglicht es den Planern, sich auf die wirklich schwierigen Fälle konzentrieren – was ihre Produktivität erheblich steigert. Hier setzt der Konfliktlöser «Conflict Resolver» an, das Thema unseres Artikels.
Der Conflict Resolver ist das Werkzeug zur Produktivitätssteigerung, das dem Nutzer bei der Lösung der einfachen Konflikte helfen soll. Er baut auf dem MoD-Framework auf, das die Brücke zwischen makro- und mikroskopischer Modellwelt schlägt, und integriert frühere Forschungsarbeiten zur Entscheidungsunterstützung bei der Konfliktlösung sowie algorithmische Verbesserungen, um die Anzahl notwendiger Aufrufe an die zeitaufwendigen mikroskopischen Dienste zu reduzieren.
Was befindet sich unter der Haube?
Das Prinzip des Conflict Resolvers besteht darin, einen Korridor auszuwählen, in dem der Nutzer Konflikte aus den geplanten Verkehren beseitigen möchte. Dies darf ein Teil des Netzes sein – der Nutzer kann sicher sein, dass die ausgewählten Züge ausserhalb dieses Bereichs nicht verändert werden. Aus Sicht des Nutzers genügt ein Knopfdruck in Viriato, um den Prozess zu starten. Diese augenscheinliche Einfachheit verbirgt einen komplexen mathematischen Hintergrundprozess.
Viriato selbst hat keine Kenntnisse über die mikroskopische Infrastruktur, die zur Bewertung von Konflikten erforderlich ist. Selbst wenn dies der Fall wäre, müssten die Blockbelegungszeiten der möglicherweise untereinander in Konflikt stehenden Züge bekannt sein und in ein mathematisches Modell überführt werden – sofern keine brute-force Methode im mikroskopischen Tool selbst zur Anwendung kommen soll. Prinzipiell wäre es möglich, die Fahrt jedes Zuges durch jeden Blockabschnitt wiederholt zu simulieren, um alle möglichen Blockbelegungszeiten zu ermitteln und anschliessend die Konflikte zu lösen. Doch angesichts der vielen Freiheitsgrade wäre dieser Vorab-Schritt extrem rechenaufwändig.
Glücklicherweise bieten die Ausgestaltung der Eisenbahninfrastruktur und die Dynamik von Zügen einen Weg, eine gute Näherung für Blockreservierungs- und Freigabezeiten zu finden. In der Praxis hat sich gezeigt, dass sich aufgrund der Dimensionierung der Blockabschnitte und der relativ kleinen zeitlichen Veränderungen durch realistische Planungsreserven diese Zeiten näherungsweise linear mit den geplanten Reserven verändern. Das bedeutet, dass mit nur wenigen Aufrufen (in der Regel vier pro Zuglauf) an das mikroskopische Tool jeweils mit unterschiedlichen Reserven, eine lineare Regression ein gutes statistisches Modell für den zuvor beschrieben Zusammenhang liefert.
Mit diesem Modell des Zusammenspiels von Signalsystem und Fahrzeiten lässt sich ein mathematisches Modell erstellen, in dem die Züge zeitlich umgeplant und lokal umgeleitet werden können – unter Beibehaltung der Gesamtstruktur, allein durch eine Umverteilung von Reserven und durch lokale Umleitungen innerhalb von Bahnhöfen.
Für die Berechnung werden eine Reihe gemischt-ganzzahliger linearer Programme (MILPs) erstellt und an einen mathematischen Solver übergeben, in unserem Fall Gurobi. Dieser minimiert die Anzahl und die Grösse der Konflikte zwischen Zügen, die sich durch sich überschneidende Blockbelegungszeiten ergeben, welche zuvor durch Regression angenähert wurden. Wenn ausreichend Kapazität vorhanden ist, kann der Solver die Konflikte vollständig lösen.
Wie bei allen Fragen im Eisenbahnbereich gibt es zusätzliche, oft kunden- und landesspezifische Nebenbedingungen. Beispielsweise können Regeln bestehen, wie viele Sekunden an Mindestreserven zwischen zwei Knotenpunkten eingehalten werden müssen – diese müssen im mathematischen Modell formuliert werden. Hat der Solver eine Lösung gefunden, wird diese an den Nutzer zurückgegeben, der nun einen Satz aktualisierter Züge erhält, bei denen viele kleinere Konflikte bereits eliminiert und möglicherweise auch größere reduziert wurden – validiert durch die mikroskopische Simulation via MoD.
Das bedeutet einen erheblichen Produktivitätsschub, bei dem der Nutzer die makroskopische Viriato-Welt nie verlassen musste – obwohl er ein mikroskopisches Näherungsmodell erstellt, gelöst und validiert hat.
Von der Forschung in die Praxis
Wie bei allen Projekten dieser Art ist es entscheidend, die Lösung im realen Einsatz mit echten Problemstellungen und Datenkonfigurationen zu testen. Der Conflict Resolver ist aus mehreren akademischen Forschungsprojekten hervorgegangen, unter anderem aus einer Veröffentlichung auf der ICROMA-Konferenz «RailDresden» in Zusammenarbeit mit der TU Dresden. Diese Arbeiten wurden von SMA-Fahrplanexperten getestet und zeigten das Potenzial des Ansatzes. Aktuell befindet sich der Conflict Resolver in der Industrialisierungsphase, in welcher der Algorithmus und die Methode mit standardisierten Softwareentwicklungsprozessen und auf der Algorithmus-Plattform von SMA innerhalb von Viriato neu umgesetzt werden, um den Anforderungen realer Projekte gerecht zu werden. Dabei fliessen auch neue Erkenntnisse und Anforderungen aus der täglichen Arbeit der SMA-Berater in das Tool ein, sodass es nicht bei einem akademischen Experiment bleibt, sondern eine durch die industrielle Praxis gehärtete Software entsteht.