FGSV-Nr. FGSV 002/127
Ort online-Konferenz
Datum 13.04.2021
Titel Automatisierte Fahrplanerstellung bei der DB Netz
Autoren Prof. Dr.-Ing. Johannes Schlaich, Dr.-Ing. Daniel Pöhle, M.Sc. Anna-Lena Frank, Dr. Sebastian Kühn, Dr. Florian Dahms
Kategorien HEUREKA
Einleitung

Dieses Paper stellt eine vollständig implementierte und produktiv eingesetzte Anwendung für die automatisierte und optimierte Fahrplanerstellung im Schienengüterverkehr vor. Die Anwendung wird von der Deutschen Bahn (DB Netz AG), Deutschlands größtem Eisenbahninfrastrukturanbieter, eingesetzt.

Fokus dieses Papers ist dabei die Erstellung von Fahrplänen im sehr kurzfristigen Schienengüterverkehr. Hier können Eisenbahnverkehrsunternehmen (EVU) mit der Smartphone-App Click & Ride Anfragen abgeben und erhalten innerhalb weniger Minuten ein Fahrplanangebot bestehend aus räumlicher und zeitlicher Lage der Trasse. Allein diese sehr schnelle Bearbeitungszeit sowie der entsprechende Wegfall der manuellen Fahrplanerstellung sind große Vorteile gegenüber dem bisherigen Prozess. Darüber hinaus erreicht die automatisierte Fahrplanerstellung auch Fahrpläne mit geringeren Fahrzeiten für die EVU.

PDF
Volltext

Der Beitrag ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einführung

Die Fahrplanung im Eisenbahnverkehr ist bis heute ein durch IT-Planungswerkzeuge unterstützter, jedoch weitestgehend manueller Prozess. Jede Fahrplantrasse wird mit ihren individuellen Zugeigenschaften von den Trassenkonstrukteuren konfliktfrei zu den anderen Verkehren auf den Strecken und in den Knoten eingeplant. Durch die Vielzahl an zu beachtenden Restriktionen (z.B. Streckeneigenschaften, betriebliche Regeln und der Maßgabe möglichst effizient mit der verfügbaren Kapazität umzugehen) steigt die Komplexität und damit die Bearbeitungsdauer bei der manuellen Trassenkonstruktion, wenn auf den Strecken oder in den Knoten die Kapazität knapp wird. Feil und Pöhle (2014) haben die Notwendigkeit gezeigt, den manuellen Prozess zu überwinden, um bei einer industrialisierten Fahrplanerstellung die Chance zu nutzen, global optimale Lösungen finden zu können.

Insbesondere der Schienengüterverkehr benötigt mit kurzfristiger Vorlaufzeit freie Kapazität im Schienennetz. Die Trassenbestellungen der Eisenbahnverkehrsunternehmen (EVU) gehen bei der DB Netz AG zum Großteil wenige Tage bis einige Stunden vor der gewünschten Abfahrtszeit ein und werden vom Planungsteam im Schichtbetrieb sukzessive bearbeitet. Die freie Restkapazität wird nach dem Prinzip „first come first serve“ vergeben und nach durchschnittlich ein paar Stunden erhält das EVU ein Trassenangebot. Bei komplizierten Fällen, oder wenn aufgrund der langen Strecke mehrere Bearbeiter an einer Trassenplanung mitwirken müssen, kann die Rückmeldung bis zu drei Tage dauern. Bei mehreren beteiligten Trassenkonstrukteuren spielen auch die Wartezeiten bis zur Weiterbearbeitung durch den nächsten Mitarbeiter eine Rolle und verlängern die Rückmeldezeit des Trassenangebots an das EVU.

Um die Effizienz des Prozesses der kurzfristigen Fahrplanerstellung zu verbessern und die Zeitdauer bis zur Angebotsabgabe drastisch zu reduzieren, soll der Fahrplanungsprozess digitalisiert und automatisiert werden. Ziel ist es, den Verkehrsunternehmen mit einem voll automatisierten Planungsprozess ein Trassenangebot für kurzfristige Bestellungen im Schienengüterverkehr innerhalb von maximal drei Minuten zu unterbreiten. Mit Hilfe von mathematischen Optimierungsalgorithmen soll neben der Beschleunigung des Planungsprozesses die planerische Ausnutzung der vorhandenen Infrastruktur ebenfalls verbessert werden. Dies resultiert in einer digitalen Kapazitätssteigerung.

In diesem Beitrag wird gezeigt, wie akademische Optimierungsmodelle in eine für die Praxis verwendbare Lösung transformiert werden konnten. Durch die Produktivsetzung kann gleich in dreifacher Weise Nutzen für die EVU generiert werden: Erstens lässt sich durch den Einsatz der Algorithmen die verfügbare Infrastrukturkapazität besser ausnutzen und somit ohne Neuund Ausbau steigern. Zweitens lässt sich die durchschnittliche Beförderungszeit durch die globale Optimierung der Trassen verkürzen. Drittens verkürzt sich die Wartezeit für die EVU von der Anfrage bis zum Trassenangebot deutlich auf maximal drei Minuten und macht somit erstmals, nahezu in Echtzeit, die noch freie Restkapazität des Schienennetzes transparent.

Nach einem Überblick über bisherige Ansätze zur automatisierten Fahrplanerstellung aus der Literatur in Kapitel 2 werden im Kapitel 3 die Funktionsweise der Algorithmen für die automatisierte Fahrplanerstellung beschrieben. Kapitel 0 beschreibt dann die neu in Produktion gebrachte Anwendung Click&Ride. Abgerundet wird der Beitrag in Kapitel 0 mit einem Ausblick auf mögliche zukünftige Erweiterungen des Ansatzes und der Algorithmen.

2 Literatur

Die Transformation des Fahrplanprozesses sowie verschiedene Ansätze für eine automatische Erstellung von Schienengüterverkehrsfahrplänen wurden bereits in der Literatur breit diskutiert. Die optimierte Konstruktion von standardisierten Güterverkehrstrassen wurde zunächst für streng getaktete Fahrpläne mit Hilfe eines Periodic Event Scheduling Problems (PESP) von Nachtigall (1998) eingeführt und von Opitz (2014) erweitert. Großmann et al. (2012) zeigen, dass das PESP auch als SAT-Problem kodiert werden kann, was zu deutlich geringeren Rechenzeiten führt und die Größe der Beispielinstanzen stark vergrößern konnte. Für nicht periodische Fahrpläne des Schienengüterverkehrs haben Großmann et al. (2013) nachgewiesen, dass eine gemischte ganzzahlige Formulierung für praktische Problemgrößen geeignet ist. Die optimierte Belegung von standardisierten Güterverkehrstrassen als letzter notwendiger Schritt für die Trassenzuweisung wurde von Nachtigall und Opitz (2014) eingeführt und für die Fahrplanung mit unterschiedlichen Verkehrstagen der Güterzüge von Nachtigall (2015) erweitert. Zuletzt hat das Forschungsprogramm ATRANS der DFG alle Aspekte der automatischen Erstellung von Fahrplänen berücksichtigt (Streitzig et al., 2016; Li et al. 2017).

3 Automatische Fahrplanerstellung

Bei der Fahrplanerstellung müssen ausgehend von einer Anfrage eines EVU sowohl die räumliche als auch die zeitliche Lage einer Fahrplantrasse ermittelt werden. Der Ablauf der automatischen Fahrplanerstellung ist in Bild 1 zusammengefasst und wird in den folgenden Kapiteln ausführlich beschrieben.

Bild 1: Übersicht der automatischen Fahrplanerstellung

3.1 Anfrage stellen

Eine Anfrage repräsentiert den Wunsch eines EVUs eine Zugfahrt von einem bestimmten Ort zu einem Ort durchführen zu wollen. Dabei werden außer den räumlichen Fixpunkten auch noch die technischen Parameter der Zugcharakteristik und die zeitlichen Einschränkungen durch das EVU übermittelt (vgl. Kapitel 4). Diese Informationen bilden die Grundlage zur Erstellung einer Trasse durch die DB Netz AG.

3.2 Routensuche

Zur Reduktion der Problemgröße werden in einem ersten Schritt Routen gesucht, die grundsätzlich für ein Trassenanfrage geeignet sein könnten. Hier wird zunächst von einem leeren Netz ausgegangen - die tatsächlich eingeschränkte Verfügbarkeit der Infrastruktur aufgrund von bereits geplanten Trassen wird also zunächst nicht betrachtet.

Die Routensuche erfolgt auf dem Infrastrukturmodell der DB Netz AG („Spurplan“). Bild 2 zeigt davon exemplarisch eine Betriebsstelle. Zur Durchfahrt durch eine Betriebsstelle gibt es in der Regel mehrere sogenannte Betriebsstellenfahrwege (kurz: Fahrwege).

Bild 2: Betriebsstellenfahrweg (rot) von Betriebsstellengrenze zu Betriebsstellengrenze (eckige Klammer)

Bei der Routensuche kommt ein A*-Algorithmus (Hart et. al 1968), zum Einsatz, um den kürzesten Weg auf der Infrastruktur zu finden. Der Algorithmus verwendet Geokoordinaten zur Berechnung des Luftlinienabstands zwischen den Betriebsstellen als untere Grenze.

Das Routing erfolgt auf einem gerichteten Graphen von Fahrwegen mit Fahrzeiten als Basis für die Berechnung der Kantenkosten. Die reine Fahrzeit ist allerdings für ein sinnvolles Routing nicht ausreichend, da bestimmte Fahrwege aus Sicht der Eisenbahnbetriebspraxis zu vermeiden sind. Dazu gehören beispielsweise das Fahren im Gegengleis oder das Kreuzen von Hauptgleisen. Daher werden für die Kostenberechnung die Fahrzeiten dieser Fahrwege mit einem geeigneten Faktor ≥1 multipliziert.

Für jeden Fahrweg im Graphen muss zudem geprüft werden, ob er für die vom Kunden angefragte Zugcharakteristik zulässig ist. Hier müssen unter anderem die Elektrifizierung, Grenzlasten und Halteplatzlängen geprüft werden.

Die reine Kurzwegsuche ist an dieser Stelle nicht ausreichend, da die Sperrzeiten der sogenannten gesetzten Verkehre nicht berücksichtigt worden sind. So kann die Route beispielsweise über Betriebsstellen führen, die zur vom Kunden angefragten Zeit bereits vollständig ausgelastet sind. Daher wird die A*-Kurzwegsuche wiederholt durchgeführt, wobei jeweils die die Kosten für Kanten, die in bereits gefundenen Routen verwendet wurden, erhöht werden. Eine Route wird dabei nur dann als echte Alternative akzeptiert, wenn sie sich von allen bereits berechneten in mindestens einer Betriebsstelle unterscheidet. Ein maximaler Umwegfaktor beschränkt dabei die Anzahl der Ergebnisse. Das Ergebnis einer Mehrwegesuche von Hamburg nach Děčín an der tschechisch-deutschen Grenzen ist Bild 3 dargestellt.

Bild 3: Ergebnisse der Mehrwegsuche

3.3 Erstellung von Schnipseln

Für alle im vorherigen Schritt gefundenen Routen werden nun für Teilabschnitte sogenannte „Schnipsel“ erzeugt. Dies erfolgt zunächst entlang der in Bild 4 illustrierten Schritte und berücksichtigt keine kapazitativen Einschränkungen.

Bild 4: Räumliche Darstellung der Schnipselerstellung: 1. Zusätzliche Fahrwege innerhalb von Betriebsstellen; 2. Schnittpunkte; 3. Erzeugte Schnipsel 

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.

Bild 5 zeigt die Fahr- und Belegungszeiten zweier Schnipsel mit unterschiedlichen Höchstgeschwindigkeiten aber gleichem Fahrtverlauf. Beide Schnipsel bremsen aus der jeweiligen Startgeschwindigkeit bis zum Halt ab. Der rechte Schnipsel benötigt durch die reduzierte Höchstgeschwindigkeit etwas länger für die gleiche Strecke bis zum Halt. Auf dem Streckenabschnitt bis zum Abzweig ist gut erkennbar, dass die Schnipsel für zwei unterschiedliche Geschwindigkeitsprofile der Strecke passen würden und in der Trassenberechnung je nach Bedarf genutzt werden können.

Bild 5: Fahr- und Belegungszeiten eines Schnipsels (links mit maximaler, rechts mit reduzierter Geschwindigkeit)

Obwohl die Sperrzeitentreppen des linken Schnipsels insgesamt kleiner sind, kann der rechte Schnipsel mit der geringeren Geschwindigkeit zu einer besseren Kapazitätsausnutzung führen, wenn die jeweiligen Kapazitätslücken (beispielsweise zwischen den blauen Zügen in Bild 6) nur einen schnellen Zug (rot) aber zwei langsamere Züge (dunkelgelb) zulassen.

Bild 6: Kapazitätseffekt im Fahrplan durch Geschwindigkeitsharmonisierung der Schnipsel

3.4 Trassenberechnung

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 tplan der geplanten Fahrplantrasse durch die Fahrzeit tleer auf leerer Infrastruktur dividiert wird

BFQ = tplan/tleer

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

Dieses Paper ist im Rahmen des Projekts „Digitale Kapazitätssteigerung“ entstanden, das durch das Bundesministerium für Verkehr und digitale Infrastruktur (BMVI) finanziell unterstützt worden ist.

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.