Energy-efficient optimization of railway operation : an algorithm based on Kronecker algebra

Abstract

Ein Eisenbahnnetz besteht im Allgemeinen aus einer umfangreichen Infrastruktur, auf der eine Vielzahl an Zügen verkehrt. In einem derart komplexen System ist es für den einzelnen Triebfahrzeugführer oder Disponenten schwierig, die jeweils richtige Entscheidung für den optimalen Betriebsablauf zu treffen. Zur Gewährleistung der Sicherheit wird ein Großteil des Betriebs automatisiert durchgeführt. Allerdings wird in Dispositionsentscheidungen der Energiebedarf nicht oder nur am Rande berücksichtigt, wodurch sich ein großes Potential zur Einsparung ergibt, das auf zwei Ebenen aufgeteilt werden kann. Zum Einen kann jede einzelne Zugfahrt optimiert werden, um das Fahrziel mit möglichst wenig Energiebedarf zu erreichen. Zum Anderen muss das Gesamtsystem betrachtet werden und aufgrund des aktuellen Fahrplans, etwaiger Verspätungen oder auch aufgrund von gesperrten oder nur eingeschränkt nutzbaren Abschnitten eine optimale Strategie zur Minimierung des Energiebedarfs entwickelt werden. Diese beiden Ebenen zur Optimierung müssen sich allerdings wichtigen Kriterien, wie zum Beispiel der Sicherheit, der Pünktlichkeit und auch dem Fahrkomfort unterordnen. Basierend auf diesen Anforderungen berechnet der Optimierungsalgorithmus eine Gesamtlösung mit möglichst geringem Energiebedarf. Dem Disponenten bzw. dem Triebfahrzeugführer können somit Informationen zum optimierten Gesamtsystem bzw. zur optimalen Einzelfahrt zur Verfügung gestellt werden. Der erste Teil des Algorithmus besteht aus der Optimierung der Einzelfahrten, dessen Ergebnis sich aus den Fahrtypen Beschleunigung, Halten der Geschwindigkeit, Ausrollen und Bremsen zusammensetzt. Der zweite Teil optimiert das Gesamtsystem, bei der die sogenannte Kronecker-Algebra und die Einzelfahrt-Optimierung zur Anwendung kommen. Die Kronecker-Algebra besteht aus der Kronecker-Summe und dem Kronecker-Produkt und dient dazu, eine Matrix zu erzeugen, die alle Zugbewegungen im System beinhaltet. Für die Berechnung werden die Routen der Züge als Abfolge von Streckenabschnitten in einer quadratischen Matrix dargestellt. Die Abschnitte selbst werden als Semaphore modelliert und ebenfalls in Matrizen bereitgestellt. Die Kronecker-Summe berechnet alle möglichen Verschachtelungen der beteiligten Züge, sofern diese keinen Streckenabschnitt gemeinsam nutzen. Andernfalls können über das Kronecker-Produkt alle Varianten berechnet werden, in denen mehrere Züge einen gemeinsamen Abschnitt befahren. In diesem Fall wird sichergestellt, dass der Zugriff sequentiell erfolgt. Das bedeutet, dass ein Zug einen Abschnitt erst dann befahren darf, wenn er von einem anderen Zug freigegeben wurde. Die Anwendung dieser mathematischen Operationen erzeugt als Ergebnis wiederum Matrizen, die zur Visualisierung der Ergebnisse in Form von Graphen dargestellt werden können. Die optimale Fahrkurve der einzelnen Züge wird als Weg-Geschwindigkeit-Diagramm zur Verfügung gestellt. Die Verwendung dieses mathematischen Modells erlaubt es, Konflikte (z.B. Deadlocks, Auflaufen) zu erkennen und diese nicht mehr als potentielle Lösungen zur Verfügung zu stellen. Für die verbleibenden Zugbewegungen wird mittels der zuvor erwähnten Einzelfahrtoptimierung der Energiebedarf errechnet und anschließend die optimale Strategie zur Verfügung gestellt.

In general, a railway system consists of several trains which use a large infrastructure. In such complex systems it is very difficult for the train driver and the dispatcher to find a solution where each train will arrive at its destination in time and the energy consumption is minimal. To ensure the requirement of a safe system, few operations are done by automated systems. Often there is less consideration on the energy consumption resulting in a high potential for saving traction energy. This potential can be divided into two parts. On one hand each single trip can be optimized by using an optimal driving strategy, where the demand of traction energy is minimal. On the other hand, the complete railway system is analyzed. In the latter case the schedule, delays, and restriction on the tracks are taken into account for the calculation of an optimal solution. The optimization of such a system must satisfy important criteria, such as safety, punctuality and passenger comfort. Based on these restrictions, the optimization algorithm determines an overall solution where the energy consumption is as small as possible. The results of the algorithm can be used to support train drivers and dispatchers. The first part of the algorithm consists of finding an optimal solution for a single journey, which consists of four driving types, namely acceleration-phase, speed-hold-phase, coasting-phase, and braking-phase. The second part of the algorithm is the optimization of the complete system by applying the so-called Kronecker Algebra and the single-trip optimization. Kronecker Algebra consists of Kronecker Sum and Kronecker Product and is used to create a matrix, which contains all possible movements of the trains within the system. Each train has a route for its journey which consists of a sequence of track sections. This information is given as matrix and used as input for the algorithm. Each track section is modeled by a semaphore and given as a matrix, too. Kronecker Sum calculates all possible interleavings of the trains, but only if they do not use the same track sections. If several trains use a common track section, Kronecker Product is used to ensure that the access on each section is done sequentially. In particular a train can enter a section only if it has been released by another train. The result of the application of Kronecker Algebra is again a matrix, which can be represented by a graph. The optimal driving strategy for each train is given as a distance-speed-diagram. This model is used to determine and to avoid conflicts (e.g. deadlocks or headway-conflicts). All conflict-free solutions are calculated and as a result, the best solution in terms of energy consumption is given.