TU Darmstadt / ULB / TUprints

Computing Highly Reliable Train Journeys

Keyhani, Mohammad Hossein (2017)
Computing Highly Reliable Train Journeys.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
Keyhani_Dissertation_Final.pdf - Accepted Version
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Computing Highly Reliable Train Journeys
Language: English
Referees: Weihe, Prof. Dr. Karsten ; Andreas, Prof. Dr. Oetting
Date: 2017
Place of Publication: Darmstadt
Date of oral examination: 25 April 2017
Abstract:

Millions of people travel daily by public transport in order to reach their destinations. Public transport is often an attractive alternative to traveling by other means such as cars. In daily operation, however, unfortunate delays frequently arise, disrupting the scheduled departure and arrival times of the trains. Even slight delays can result in connection breaks wherein passengers miss their connecting trains because they arrive too late for planned transfers. A considerable number of passengers are consequently faced by delays and their repercussions every day.

This work focuses on the computation of reliable journeys. First, we demonstrate an accurate method of assessing the reliability of train connections. For the assessment of a train connection, we compute the probability of passengers reaching their destinations when taking the train connection; in other words, the probability of the train connection not breaking because of delays. Our method considers the timetable, interdependencies between trains, current delays in the railway network, and stochastic prognoses for the travel times of the trains. Regarding the latter, we use probability distributions which are computed based on tangible historical delay data. The interdependencies between the trains are caused by delay managements; trains wait for the passengers of other delayed trains. Our computational study---which is based on real data---reveals that our reliability assessments are realistic and accurate.

We then address a fundamental problem in planning journeys: arrive in time by train at the destination with a high probability. In addition, to save time, passengers usually desire to commence a journey as late as possible. We present an efficient solution to the described problem. We compute highly reliable train journeys by which the destination can be reached with a high probability of being on time even in case of delays. Such a train journey includes a train connection along with alternative continuations to the destination. The latter are used in case of connection breaks caused by delays. Our optimal approach computes the best choice in enabling the continuance of the journey for each situation that may occur when traveling. Along all possible continuations, the best choice is the continuation with the highest probability of being on time at the destination. The evaluations presented illustrate that the train journeys computed are highly reliable and attractive to passengers even in terms of both travel time and convenience.

State-of-the-art routing systems provide the search for intermodal, door-to-door connections. Beside public transport, passengers use modes of transport such as taxis, car sharing, bike sharing, and individual cars. We extend our method of assessing the reliability of train connections to intermodal connections. Moreover, we discuss approaches to the computation of reliable intermodal connections.

Last, we address the problem of connection breaks late at night; such a situation is frustrating for passengers, particularly if the destination cannot be reached by public transport prior to the end of operations. In such situations, railway companies must offer compensation to ensure the rights of passengers are upheld. We propose a solution to the problem of finding connections to the destination by taking into account the options of taxi rides or overnight stays in hotels. The main objectives are the satisfaction of passengers and cost reductions for the railway company.

The methods and algorithms presented in this work are designed for real, large train networks such as in Germany with more than a million departure and arrival events per day. We use a fully realistic model that represents the timetable and relevant factors which influence train delays. Thus, we compute realistic train journeys which can be used by passengers in order to reach their destinations. Our computational studies are based on real data from the German railway company, Deutsche Bahn AG. The evaluations demonstrate that our approaches deliver promising results, are practicable, and can be integrated into timetable information systems in order to answer large amounts of passenger queries per day.

Alternative Abstract:
Alternative AbstractLanguage

Täglich nutzen Millionen Menschen öffentliche Verkehrsmittel, um ihre Reiseziele zu erreichen. Häufig sind öffentliche Verkehrsmittel attraktive Alternativen zu anderen Verkehrsmitteln wie Autos. Allerdings finden jeden Tag Ereignisse statt, die Verspätungen verursachen und die fahrplanmäßigen Abfahrts- und Ankunftszeiten der Züge beeinträchtigen. Bereits kleine Verspätungen können zu Verbindungsbrüchen führen, sodass Passagiere ihre Anschlüsse verpassen. Somit sind viele Menschen täglich mit Verspätungen und deren Folgen konfrontiert.

Diese Arbeit befasst sich mit dem Themengebiet Berechnung von zuverlässigen Bahnverbindungen. Zuerst zeigen wir eine genaue Methode zur Bewertung der Zuverlässigkeit von Bahnverbindungen. Für die Bewertung einer Bahnverbindung berechnen wir die Wahrscheinlichkeit, dass Passagiere mit der Verbindung ihr Ziel erreichen können und diese nicht aufgrund von Verspätungen bricht. Unsere Methode berücksichtigt den Fahrplan, Abhängigkeiten zwischen den Zügen, die aktuellen Verspätungen im Bahnnetz und stochastische Prognosen für Reisezeiten der Züge. Die Abhängigkeiten zwischen den Zügen entstehen durch Wartezeitregelungen: Züge warten auf Passagiere aus anderen verspäteten Zügen. Für die stochastischen Prognosen verwenden wir Wahrscheinlichkeitsverteilungen, die auf realen Verspätungsdaten aus der Vergangenheit basieren. Die Evaluation der Zuverlässigkeitsbewertungen anhand realer Daten zeigt, dass diese realistisch und akkurat sind.

Daraufhin befassen wir uns mit einem grundsätzlichen Problem bei Bahnreisen: der rechtzeitigen Ankunft am Ziel mit sehr hoher Wahrscheinlichkeit. Als sekundäres Kriterium möchten Passagiere ihre Reise so spät wie möglich antreten, um die Reisezeit zu minimieren. Wir präsentieren einen effizienten Algorithmus zur Lösung des beschriebenen Problems. Unser Ansatz berechnet hochzuverlässige Bahnreisen mit denen das Ziel mit sehr hoher Wahrscheinlichkeit auch im Falle von Verspätungen rechtzeitig erreicht werden kann. Eine solche Bahnreise besteht aus einer Bahnverbindung samt Alternativen zum Ziel, auf die Passagiere bei Verbindungsbrüchen im Verspätungsfall ausweichen können. Für jede Situation, die während der Reise auftreten könnte, berechnet unser Ansatz die beste Option, um die Reise fortzusetzen. Die beste Option maximiert die Wahrscheinlichkeit einer rechtzeitigen Ankunft am Ziel. Die Evaluation des Ansatzes weist nach, dass die berechneten Bahnreisen sowohl hochzuverlässig als auch komfortabel sind und attraktive Reisezeiten haben.

Moderne Auskunftssysteme ermöglichen Reisenden intermodale "Tür zu Tür" Verbindungen zu berechnen. Neben öffentlichen Verkehrsmitteln nutzen Passagiere bei solchen Verbindungen auch Verkehrsmittel wie Taxi, Carsharing, Bike-Sharing und privates Auto. Für dieses Szenario zeigen wir eine entsprechende Erweiterung unseres Ansatzes, die die Bewertung der Zuverlässigkeit solcher Verbindungen ermöglicht. Zudem beschreiben wir Ansätze zur Berechnung von zuverlässigen intermodalen Verbindungen.

Als letzten Punkt adressieren wir das Problem der Verbindungsbrüche an Tagesrandlagen. Eine solche Situation ist für Passagiere frustrierend, insbesondere wenn das Reiseziel mit öffentlichen Verkehrsmitteln vor Betriebsschluss nicht mehr erreicht werden kann. Dadurch entstehen auch für die Verkehrsunternehmen Kosten zur Sicherung der Fahrgastrechte. Wir schlagen eine Lösung vor, bei der intermodale Verbindungen zum Ziel genutzt werden, die unter anderem Taxifahrten oder Hotelaufenthalte enthalten. Die Optimierungskriterien unseres Ansatzes sind die Zufriedenheit der Passagiere und die Minimierung der für die Verkehrsunternehmen entstehenden Kosten.

Die präsentierten Methoden und Algorithmen sind für reale und große Bahnnetze entworfen. Ein Beispiel hierfür ist das Bahnnetz in Deutschland mit mehr als einer Million Abfahrts- und Ankunftsereignissen am Tag. Wir nutzen ein vollkommen realistisches Modell, das den Fahrplan und relevante Faktoren, die Einflüsse auf Verspätungen haben, repräsentiert. Somit berechnen wir realistische Verbindungen, die von Passagieren genutzt werden können, um ihre Reiseziele zu erreichen. Unsere Evaluationen basieren auf realen Daten der Deutschen Bahn AG. Diese zeigen, dass unsere Ansätze vielversprechende Ergebnisse liefern und praktikabel sind. Sie können in Fahrplanauskunftssysteme integriert werden, um täglich große Mengen an Passagieranfragen zu verarbeiten.

German
URN: urn:nbn:de:tuda-tuprints-62276
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Algorithmics
Date Deposited: 22 May 2017 09:55
Last Modified: 09 Jul 2020 01:38
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/6227
PPN: 403266556
Export:
Actions (login required)
View Item View Item