Computing Highly Reliable Train Journeys

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