1. Ausgehend von einer Route aus der Routensuche (grün) werden innerhalb von Betriebsstellen alle weiteren zur Zugcharakteristik passende Fahrwege (blau) gesucht. Dies soll später ermöglichen, dass Züge abseits der üblicherweise in der Routensuche gefundenen durchgehenden Hauptgleises für Überholungen halten können bzw. mehrere Alternativen zur Durchfahrt einer Betriebsstelle haben. Um einen Halt einplanen zu können, muss auf den entsprechenden Überholungsgleisen auch ein Halteplatz ausreichender Länge vorhanden sein.

2. Die Route wird nun in die Teilabschnitte der Schnipsel aufgeteilt. Um diese sinnvollen Überholungsabschnitte zu definieren, müssen betriebliche Restriktionen beachtet werden. So benötigt beispielsweise ein Güterzug eine gewisse Strecke, bis er aus dem Halt bis zur Höchstgeschwindigkeit beschleunigt hat. Sind die Teilabschnitte bis zum nächsten Halt zu kurz, dann ergeben sich Fahrtprofile für den Güterverkehr, die aus energetischer und infrastrukturkapazitiver Sicht unerwünscht sind, da die Züge ausschließlich in Beschleunigungs- und Bremsphasen geplant werden. Aus diesem Grund hat sich ein Mindestabstand zwischen zwei Haltemöglichkeiten von sieben Kilometern als praktisch sinnvoll etabliert. Für jeden Schnipsel wird die Fahr- und Belegungszeit ermittelt, um den Kapazitätsverbrauch und die Konfliktfreiheit in der Trassenberechnung (siehe nachfolgendes Kapitel) korrekt zu berücksichtigen.

3. Die zu planende Trasse für den Güterzug soll aus aufeinanderfolgenden Schnipseln zusammengesetzt werden. Dazu müssen die Verbindungsstellen der Schnipsel geeignet zusammenpassen. Es müssen beispielsweise die aktuelle Geschwindigkeit an den Übergängen der Schnipsel und auch das befahrene Gleis übereinstimmen, damit eine durchgängige Zugfahrt ohne „Sprünge“ auf ein anderes Gleis oder ruckartige Geschwindigkeitsänderungen entstehen können. Aus diesem Grund werden sinnvolle Verbindungsschnipsel für die Folge von haltenden und durchfahrenden Schnipseln generiert, die genügend glatte Übergänge sicherstellen. Zusätzlich ist es für die Kapazitätsausnutzung vorteilhaft, wenn aufeinanderfolgende Züge mit ähnlichen Geschwindigkeiten verkehren. Dazu werden auf jedem Ausschnitt zusätzliche Schnipsel mit reduzierten Maximalgeschwindigkeiten erzeugt, die eine Planung von geschwindigkeitsharmonisierten Fahrten ermöglichen. Als Resultat der Schnipselerzeugung entsteht ein gerichteter, azyklischer Graph von Teilabschnitten der zu planenden Trasse des Güterzuges, der die sinnvoll möglichen Fahrtbeziehungen auf den relevanten Strecken einschließlich sinnvoller Zwischenstopps enthält. Ein Weg von der Quelle zur Senke des so genannten Schnipselgraphs stellt immer eine zulässige Fahrtmöglichkeit des Güterzuges dar, die jedoch noch mit der zur Verfügung stehenden Kapazität auf der Strecke und den möglichen Abfahrtszeiten in Einklang gebracht werden muss.

Der letzte Schritt zur Berechnung der Trasse besteht darin, einen passenden Weg aus dem Schnipselgraph und die passenden Fahrplanzeiten der zu planenden Trasse so zu bestimmen, dass sie einerseits eine möglichst geringe Fahrzeit mit wenigen Überholungshalten hat, andererseits muss sie konfliktfrei zu allen bereits geplanten Trassen sein. Dazu wird für jeden Schnipsel die Menge der zulässigen Abfahrtszeiten ermittelt, damit er nicht im Konflikt zu anderen Zügen steht, indem die Sperrzeiten anderer Züge auf die Abfahrtszeiten des Schnipsels projiziert werden. Daraus ergibt sich ein Intervall möglicher Abfahrtszeiten für jeden Schnipsel. Als nächstes werden die Intervalle weiter reduziert, um sicherzustellen, dass nur noch solche Intervalle übrigbleiben, die von einem der Vorgänger der Schnipsel erreicht werden können. Zusätzlich werden für jeden Schnipsel die möglichen Ankunftszeitintervalle rückwärts anhand der bekannten Abfahrtsintervalle bestimmt. Jeder Schnipsel, der nicht mit einem Halt endet, hat Intervalle der gleichen Länge wie sein Vorgänger oder Nachfolger, allein verschoben um die Fahrzeit des Schnipsels. Das Intervall eines haltenden Schnipsels kann verlängert werden, solange das betreffende Überholungsgleis nicht von einem Zug genutzt wird und die maximale Haltezeit dadurch begrenzt wird. Abschließend wird für jeden Schnipsel des Schnipselgraphs die Vereinigung der Ankunftsintervalle all seiner Vorgänger und mit dieser Vereinigung die Schnittmenge der möglichen Abfahrtszeiten Schnipsels gebildet. Da der Schnipselgraph gerichtet und azyklisch ist, kann eine topologische Sortierung der Schnipsel gefunden werden, sodass der Prozess der Intervalleinschränkung nur einmal pro Schnipsel erfolgen muss.

Zur Bestimmung der Fahrplanzeit der zu konstruierenden Trasse für den Güterzug wird als erstes die Ankunftszeit der Senke des Schnipselgraphs aus dem zulässigen Ankunftszeitintervall bestimmt. Hier wird die früheste mögliche Ankunftszeit aus dem Intervall ausgewählt und anschließend rückwärts die Ankunftszeit der jeweiligen Vorgängerschnipsel ausgewählt, die eine kompatible Abfahrtszeit haben. Falls es mehr als einen kompatiblen Vorgänger gibt, werden zusätzliche Kriterien der möglichen Schnipsel für die Auswahl herangezogen. So wird beispielsweise ein Schnipsel mit Durchfahrt vor einem Schnipsel mit Halt bevorzugt und bei haltenden Schnipseln eine möglichst kurze Haltezeit bei der Auswahl. Durch diese Rückwärtssuche wird eine konfliktfreie Trasse mit möglichst wenigen Betriebshalten und einer möglichst geringen Beförderungszeit bestimmt, falls die vorhandene Kapazität dies zulässt. Dieser Algorithmus läuft ausreichend schnell für die automatisierte Fahrplankonstruktion und erfordert eine Anzahl Berechnungsschritte, welche polynomiell in der Anzahl der Schnipsel und der Anzahl der Kanten im Schnipselgraph ist. Die theoretisch maximale Anzahl der Zeitintervalle pro Schnipsel ist konstant und begrenzt auf die Anzahl Sekunden pro Tag. Sie wird weiter eingegrenzt durch den so genannten Konstruktionsspielraum der Trasse, der beispielsweise für den sehr kurzfristig angemeldeten Schienengüterverkehr +/- 120 Minuten um die Wunschabfahrtszeit der Trasse liegt.

Ergebnis des eben beschriebenen Algorithmus ist eine konfliktfreie Trasse zusammengesetzt aus einer Folge von Schnipseln vom Start bis zum Ziel der Bestellung des Verkehrsunternehmens oder die Information, dass unter den (technischen) Restriktionen keine zulässige Lösung existiert. Ein Beispiel für eine automatisiert berechnete Trasse ist in Bild 7 innerhalb eines Zeit-Wege-Diagramms (Bildfahrplan) als schwarze Zeit-Wege-Linie mit den zugehörigen Sperrzeitentreppen dargestellt. Der Algorithmus hat für die Trasse die „Lücke“ zwischen den in grün dargestellten Personenzügen genutzt und auf dem eingleisigen Abschnitt eine Kreuzung mit dem entgegenkommenden Regionalverkehrszug geplant.

Bild 7: Automatisiert berechnete Trasse (schwarze Trasse im Konstruktionstool RuT-K)

4 Anwendungsfall kurzfristiger Schienengüterverkehr

4.1 Click & Ride App

Dank der vollständig automatisierten Fahrplanerstellung kann insbesondere für sehr kurzfristige Anfragen, z.B. eine Zugfahrt für den nächsten Tag, die Reaktionszeit gegenüber den EVU verbessert werden.

Für eine vereinfachte Eingabe von einfachen Anfragen wurde die Click & Ride-App entwickelt, die auch per Browser aufgerufen werden kann. Die DB Netz AG hat sich zum Ziel gesetzt, den EVU innerhalb von drei Minuten ein Fahrplanangebot zur Verfügung zu stellen. Im Vergleich dazu dauert der heutige Prozess der manuellen Konstruktion von Fahrplänen in den meisten Fällen mehrere Stunden und kann bis zu drei Tage dauern.

Um eine maximale Dauer von drei Minuten zu gewährleisten, wurden alle Prozessschritte der Trassenbestellung automatisiert. Eine vereinfachte Prozessabfolge ist in Bild 8 dargestellt.

Bild 8: Übersicht der automatischen Fahrplanerstellung

Nach dem Einloggen können die Anwender ihre Anfrage eingeben (vgl. Bild 9). Dazu müssen nur die wesentlichen Angaben wie Start, Ziel sowie die Zugcharakteristik angegeben werden. Die Angaben sind bewusst so einfach gehalten, dass diese auch ein Lokführer kurz vor seiner Abfahrt verwenden kann.

Die Anfrage wird in das Backend der DB Netz AG übertragen. Dort findet zunächst eine Bestelleingangsprüfung statt. Diese prüft, ob die Anfrage grundsätzlich plausibel und fahrbar ist oder ob beispielsweise mit einer E-Lok ein Start auf einer nicht elektrifizierten Strecke bestellt worden ist. Falls die Anfrage abgelehnt wird, erhält der Anwender ein direktes Feedback und kann seine Anfrage ggf. entsprechend anpassen.

Bild 9: Bestellung einer Trasse in der Click & Ride App.

Nach einer erfolgreichen Bestelleingangsprüfung wird die in Kapitel 3 beschriebene automatische Fahrplanerstellung durchgeführt. Dafür werden u.a. die aktuell bereits geplanten Trassen, Baustellen und Streckenöffnungszeiten berücksichtigt.

Anschließend wird die Trasse im Fahrplankonstruktionssystem RuT-K reserviert, so dass die Kapazität blockiert wird. Zudem wird aus dem Trassenpreissystem der Trassenpreis ermittelt.

Bild 10 zeigt das Ergebnis, das anschließend in der Click & Ride App angezeigt wird. Der Anwender hat dann 10 Minuten Zeit, das Angebot anzunehmen. Nach der Annahme wird umgehend ein Fahrplan erzeugt und veröffentlicht, so dass die Zugfahrt sofort begonnen werden kann.

Bild 10: Trassenangebot für die Bestellung aus Bild 9 (Quelle: Dahms et. al 2019).

4.2 Qualität und Performance

Zur Bewertung der Qualität und Performance der Click & Ride Anwendung werden 1.301 echte Anfragen von EVU vom 14. November 2013 verwendet, zu denen auch die manuell geplanten Fahrplantrassen vorliegen. Eine Kundenanfrage besteht aus den bestellten Wegpunkten, der zeitliche Lage sowie der Zugcharakteristik:

· Die Wegpunkte beinhalten mindestens Start und Ziel der Anfrage, können aber auch bestellte Via-Punkte beinhalten.

· Für die zeitliche Lage wird ein Zeitintervall am Start der Anfrage verwendet.

· Die Zugcharakteristiken beinhalten alle Informationen, die zur Berechnung ihrer dynamischen Eigenschaften wie Beschleunigung und ihrer statischen Eigenschaften wie Länge, Breite und Masse des angeforderten Zuges erforderlich sind.

Als Basis werden die Infrastruktur von 2013 sowie die Sperrzeiten der für den 14. November 2013 geplanten Personenzüge verwendet.

Zur Bewertung der Qualität wird der sogenannte Beförderungszeitquotient (BFQ) verwendet, für den die Fahrzeit t_plan der geplanten Fahrplantrasse durch die Fahrzeit t_leer auf leerer Infrastruktur dividiert wird

BFQ = t_plan/t_leer

Aus technischen Gründen wird für den Click & Ride BFQ die Fahrzeit auf leerer Infrastruktur auf der kürzesten Route im Nenner verwendet, während der manuelle BFQ mit der Fahrzeit auf der vom Konstrukteur gewählten Route berechnet wird. In den folgenden Auswertungen ist dies für den Click & Ride BFQ eher nachteilig, da dadurch die Route im Nenner kürzer sein kann.

Tabelle 1: Perzentile für Reaktionszeiten, BFQ (manuell & Click&Ride) für 1.301 Anfragen (Quelle: Dahms et. al 2019)

Die Ergebnisse in Tabelle 1 zeigen, dass 95% der Anfragen innerhalb von 82,98 Sekunden bearbeitet werden. Nur 4 von den 1.301 Anfragen benötigen bei der Berechnung zwischen 3 und 4 Minuten, was immer noch eine deutliche Verbesserung gegenüber dem heutigen Prozess darstellt, bei dem die Bearbeitungszeit bis zu 3 Tagen betragen kann.

95% der Anfragen haben einen Click & Ride BFQ von höchstens 1,73, während das gleiche Perzentil bei manueller Konstruktion einen BFQ von 2,52 hat. Die BFQ-Auswertung zeigt, dass der automatische Prozess im Durchschnitt zu Trassen mit kürzeren Fahrzeiten führt als der manuelle Prozess.

5 Fazit und Ausblick

Mit dem vorgestellten Ansatz der Bearbeitung einzelner Anfragen im Gelegenheitsverkehr ist die DB Netz in der Lage ihre Infrastruktur kundenfreundlicher und effizienter zu nutzen und dabei den manuellen Aufwand erheblich zu reduzieren. Dafür war es nicht nur nötig, die Algorithmen zur automatischen Fahrplanerstellung zu entwickeln, sondern auch zunächst die Datengrundlagen für eine automatisierte Bearbeitung zu schaffen und die bestehenden Systeme anzubinden.

Als Erweiterung des Prozesses im Gelegenheitsverkehrs ist geplant, den EVU in der Click & Ride App nicht nur einen Fahrplan anzubieten, sondern bis zu drei Alternativen, aus denen der Anwender dann auswählen kann. Dadurch können EVU noch besser, beispielsweise zur Wagenumlauf- oder Dienstplanung, passende Fahrpläne auswählen.

Darüber hinaus sollen automatisiert erstellte Fahrplantrassen auch in weiteren Anwendungsfällen zum Einsatz kommen:

1. Bei der Erstellung des sogenannten Netzfahrplans werden Anfragen nicht einzeln, sondern ca. 16.000 Güterverkehrsanfragen und ca. 50.000 Personenverkehrsanfragen für das kommende Fahrplanjahr simultan bearbeitet. Hier sollen die nach dem vorgestellten Ansatz erzeugte Fahrpläne des Güterverkehrs mit Hilfe einer Spaltengenerierung simultan erstellt werden. Der Ansatz einer iterativen Bearbeitung zwischen manueller Konstruktion des Personenverkehrs tagsüber und automatisierter Konstruktion des Güterverkehrs nachts wurde bereits in Schlaich & Pöhle (2017) beschrieben. Numerische Ergebnisse für einen einzelnen Tag zeigen, dass der Ansatz zu einer besseren Kapazitätsnutzung und gleichzeitig besserem BFQ führen (vgl. Dahms et al. 2019).

2. Bei der Erstellung von Baufahrplänen müssen durch baubedingte Einschränkungen der Infrastruktur bereits geplante Trassen zeitlich und räumlich angepasst werden. Für diesen Anwendungsfall ist eine Erweiterung der Algorithmen für den Personenverkehr wie die Berücksichtigung von Bahnsteiglängen erforderlich, da nicht nur Güterverkehre sondern auch Personenverkehre von Baumaßnahmen betroffen sind und behandelt werden müssen.

6 Danksagungen

7 Literatur

Feil, M., Pöhle, D. (2014), Why Does a Railway Infrastructure Company Need an Optimized Train Path Assignment for Industrialized Timetabling, International Conference on Operations Research, Aachen.

Hart, P. E., Nilsson, N. J., Raphael, B. (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics.

Großmann, P., Hölldobler, S., Mantey, N., Nachtigall, K, Opitz, J., Steinke, P. (2012), Solving Periodic Event Scheduling Problems with SAT, In: Advanced Research in Applied Artificial Intelligence, Springer Berlin Heidelberg.

Großmann, P., Labinsky, A., Opitz, J., Weiß, R. (2013), Capacity-utilized Integration and Optimization of Rail Freight Train Paths into 24 Hours Timetables, In: Tagungsband der 3rd International Conference on Models and Technologies for Intelligent Transportation Systems 2013, TUDpress, Dresden.

Li, X., Nachtigall, K., Martin, U., Oetting, A. (2017), Methodik zur effizienten markt geeigneten Trassenbelegung im spurgeführten Verkehr, Eisenbahntechnische Rundschau, vol. 6.

Nachtigall, K. (1998), “Periodic Network Optimization and Fixed Interval Timetables, Habilitationsarbeit, Hildesheim.

Nachtigall, K., Opitz, J. (2014), Modelling and Solving a Train Path Assignment Model, International Conference on Operations Research, Aachen.

Nachtigall, K., (2014), “Modelling and Solving a Train Path Assignment Model with Traffic Day Restriction, In: Operations Research Proceedings 2015, Springer, Heidelberg.

Dahms, F., Frank, A-L., Kühn, S., Pöhle, D. (2019), Transforming automatic scheduling in a working application for a railway infrastructure manager, 8th International Conference on Railway Operations Modelling and Analysis (ICROMA), Norköpping, Schweden.

Opitz, J., (2009), Automatische Erzeugung und Optimierung von Taktfahrplänen in Schienenverkehrsnetzen”, Dissertation, Dresden.

Schlaich, J., Pöhle, D. (2017), Einsatz von Optimierungsverfahren in der Fahrplanerstellung, Tagungsbericht Heureka 2017, FGSV Verlag, Cologne, Germany.

Streitzig, C., Nachtigall, K., Martin, U., Oetting, A. (2016), Anforderungsgerechte Algorithmen zur effizienten marktgeeigneten Trassenbelegung, Eisenbahntechnische Rundschau, vol. 8.

EWIV-Korridor Rhein-Alpen EWIV (2019), https://www.corridor-rhine-alpine.eu/about-us.html, heruntergeladen am 31.01.2019.