Passenger-oriented train timetable rescheduling in case of severe disruptions

Abstract

Delays are one of the major reasons for passenger dissatisfaction in the railway industry. Depending on the gravity of the delay, timetables, crew schedules or rolling stock may be affected. In this research, we address the issue of timetable recovery in case of a severe disruption (e.g., the unavailability of a track between two stations for several hours). Once an initial delay has occurred, the original timetable needs to be updated to a so‐called disposition timetable. This new timetable has to be conflict‐free in terms of operational constraints (i.e., no two trains can be scheduled on the same resource at the same time) and as convenient as possible for the passengers. The current practice in the field still heavily relies on predetermined scenarios and personal experience of train traffic controllers. However, due to the high utilization rate of modern railway networks, a decision made at one location in the network can have domino effects in the whole network. Furthermore, as railway companies in heavily disrupted situations are mainly concerned with operational questions in order to provide a feasible disposition timetable, passenger considerations are pushed into the background.

The problem of finding a conflict‐free disposition timetable has received a large attention in the scientific literature in recent years, especially in case of minor disturbances in railway networks. On the other hand, the literature on timetable adjustment during large disruptions is very limited (see Cacchiani et al., 2014 for an overview). The literature focusing on minimizing the negative effects of delays for passengers has also been developing but remains sparse. These observations are the motivation for introducing a hybrid methodology that takes into account both parties' satisfaction when generating a disposition timetable for highly disrupted situations. In our formulation, the problem is addressed by a realistic simulation‐ optimization model that integrates both operational rescheduling and passenger routing.

We first present an exact formulation of the passenger‐oriented timetable rescheduling problem that is adapted from the minimum cost flow problem. The objective function minimizes passenger dissatisfaction as well as operational costs. Passengers' travel choices are represented by a path disutility function encompassing travel time, waiting time and penalties for departure time shift and transfers for every possible path between origin and destination. Operational constraints ensure the conflict‐free running of trains. Computational experiments on a sample railway network inspired from real‐world data validate the model.

The number of passengers the exact model can handle is limited. We therefore also describe an iterative framework to solve the problem. An adaptive large neighborhood search meta‐heuristic (inspired from Barrena et al., 2014) generates operationally feasible disposition timetables. Based on real‐word

operational recovery strategies as well as demand‐driven assumptions, various operators that remove or add trains to the timetable are implemented. At every iteration, the total passenger disutility of the timetable is evaluated by a capacitated passenger assignment model. Passengers are first assigned deterministically on their time‐dependent shortest path (in terms of their disutility function). Train capacities are taken into account in a second step: if the capacity of a train is exceeded during the first phase, surplus passengers are removed from the saturated train according to passenger priority rules. They are subsequently re‐assigned on a reduced network, in which the saturated train is forbidden.

The framework is applied on a network inspired from real‐world data, with about 200 trains and 40,000 passengers. Results are obtained within reasonable computational time and show substantial improvements in terms of passenger satisfaction indicators. To address the multi‐objectiveness of the problem, the Pareto front of operational costs and passenger disutility is presented. The results of the exact and heuristic approaches are also compared on the sample network.

This work proposes a novel framework to generate disposition timetables for severe disruptions in railway networks with a passenger‐oriented focus. It takes train capacity considerations into account explicitly and offers a very flexible tool, in the sense that any operational recovery strategy (e.g., train cancellation, partial train cancellation, global train re‐routing, additional services such as buses, etc.) can be evaluated. This model will thus assist train operating companies when evaluating the trade‐off between economic and infrastructural feasibility of recovery schemes on the one hand side and passenger satisfaction on the other. Further research will focus on the definition of smarter and more realistic operators to address the supply side of the simulation‐optimization model.

Key references

Cacchiani, V., Huisman, D., Kidd, M., Kroon, L., Toth, P., Veelenturf, L., & Wagenaar, J. (2014). An overview of recovery models and algorithms for real‐time railway rescheduling. Transportation Research Part B: Methodological, 63, 15–37.

Barrena, E., Canca, D., Coelho, L. C., & Laporte, G. (2014). Single‐line rail rapid transit timetabling under dynamic passenger demand. Transportation Research Part B: Methodological, 70, 134–150. doi:10.1016/j.trb.2014.08.013