OPTSM
Optimization in Public Transport and Shared Mobility IV

Invited Session

Time Slot: Wednesday Morning

Room: AUD_A

Chair: Joaquin Rodriguez

Practical deployment of real-time railway traffic management algorithms: impact of process meta-parameters

Time: 11:30

Federico Naldini (COSYS-ESTAS Université Gustave Eiffel), Pellegrini Paola, Rodriguez Joaquin

Railway traffic is often afflicted by unforeseen perturbations causing so-called primary delays. As a result, impacted trains utilize some track sections later than planned. This may impact neighboring trains in that may not be allowed to proceed at their planned speed due to the onset of conflicts triggering restrictive signals. The consequent unplanned slow-downs or stops may cause delay propagation, as secondary delay. Dispatchers can counteract this by quick and effective train re-timing, re-routing and re-ordering decisions. In the literature, this is known as the real-time Railway Traffic Management Problem (rtRTMP). RECIFE-MILP is an optimization algorithm for the rtRTMP that may be used as a decision support tool for dispatchers. In the literature, the impact of rtRTMP algorithms on traffic is seldom assessed considering an actual possible deployment framework. This can be done considering a railway simulator to replace reality and using an optimization algorithm for making traffic management decisions. To further increase the realism of the assessment, a closed-loop framework can be set up, in which optimization is repeated periodically to take into account the actual traffic state as time evolves. In this work, we assess the performance of RECIFE-MILP when used in closed-loop with a state-of-the-art railway simulator named OpenTrack. We consider various infrastructures modeled microscopically, real timetables and realistic traffic perturbations. In particular, we perform a sensitivity analysis on the most relevant closed-loop meta-parameters, to understand their impact on the quality of the traffic management decisions implemented over time. For example, we vary the time horizon concerning the decisions to be taken and the frequency at which a new rtRTMP solution is to be computed. The results show how the best meta-parameter configuration depends on the characteristics of the case study considered.

Large-scale real-time dispatching in the Greater Oslo area

Time: 11:50

Giorgio Sartor (SINTEF), Kloster Oddvar, Luteberget Bjørnar, Mannino Carlo, Schulz Christian

We present the results of a 4 year project aimed at developing a prototype for large-scale real-time dispatching in the Greater Oslo area, which includes all lines incident to Oslo central station up to a 100 km radius. The prototype was developed in collaboration with Bane NOR, the Norwegian railway infrastructure manager, which also provided us with real-time information about train positions and timetables. The underlying algorithm is based on a MILP approach introduced in Lamorgese and Mannino (2015), then extended in Bach et al. (2019), and here extensively updated to support the additional complexity of the Greater Oslo area. It combines an exact micro-macro decomposition approach with a sophisticated column-and-row-generation scheme. The model is able to consider almost every action a human dispatcher is able to perform, such as rerouting in stations, overtakes, and slow-downs. And it takes into consideration almost all operational constraints, including safety margins, platform lengths, slopes, train weight, etc.The prototype consists of a decision support tool available via web GUI to train dispatchers seated at Oslo. The tool receives real-time information about the current traffic situation and displays the optimal future schedules for all trains for the next 6 hours through an interactive train graph. Dispatchers are allowed to interact with the tool by providing specific constraints or preferences, and therefore test what-if scenarios. For example, if a platform in a station is not available for the rest of the day due to a signal failure, the algorithm is able to adapt and recompute all future schedules in a matter of seconds.

Coordinated perturbation management in railway traffic

Time: 12:10

Xiajie Yi (IRT Railenium), Marlière Grégory, Pellegrini Paola, Rodriguez Joaquin, Pesenti Raffaele

Due to perturbations (i.e., an unexpected, degraded operation, technical failures, etc), a common problem faced by traffic controllers is that timetables for trains are not necessarily operated as they were initially planned. This paper deals with a coordinated train rerouting and rescheduling problem to minimise the impact of such a perturbation, e.g., to minimise delay propagation. This problem is often faced by traffic controllers at regional railway control centres. The problem of efficiently rerouting and rescheduling trains is known in the literature as real-time Railway Traffic Management Problem (rtRTMP).Typically, the railway network is divided into non-overlapping control areas. Regional control centres coordinate several control areas, and a coordinator manages each control centre. In this contribution, we call a track connecting between two control areas a border section. If a multiple track line connects two control areas, we represent them as multiple border sections. Besides, a border section can be traversed in either one or two directions.In many control centres, the real-time railway traffic management is organised into two decision levels. At a higher level, a coordinator makes decisions on the overall network making abstraction of operational details. At the lower level, a dispatcher manages train schedules and routes in his own control area to fit with coordinator decisions. Indeed, to optimise the overall system performance and ensure decision coherence, the coordinator may impose constraints to dispatchers. We hereby refer to the problems tackled at the lower and higher levels as dispatching and coordination problems, respectively. As far as we are aware, only few papers focus on the coordination of traffic management across different control areas. In this study, we propose an iterative algorithm to solve the coordinated traffic management problem in networks including multiple control areas.

Train-based instance reformulation in real-time Railway Traffic Management

Time: 12:30

Joaquin Rodriguez (Université Gustave Eiffel), Ferrari Alessandro, Sobieraj Richard Sonia, Pellegrini Paola

Railway timetables are designed to allow smooth traffic operations. Nonetheless, when unexpected events occur delays may arise, and timetables may have to be modified to limit their propagation: trains may be rerouted or may have to respect specific passing orders in critical parts of the network. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of minimizing the impact of unexpected events through rerouting and rescheduling. In the literature, several optimization algorithms have been proposed for tackling the rtRTMP (Cacchiani et al., 2012). In its classic representation, an instance of this problem includes information on the network topology, the timetable, and the expected traffic perturbation. Depending on network topology and train characteristics, a large number of alternative routes may be available for each train, and this typically has a negative impact on the performance of rtRTMP algorithms. In this work, we propose and assess a novel way for modeling instances aiming to allow algorithms to better deal with large numbers of rerouting possibilities. The novel modeling is based on a train-based instance reformulation.The motivation for this decomposition is the observation that train alternative routes often partially overlap. In the novel modeling, we split single trains with several partially overlapping routes into multiple trains with shorter and non-overlapping routes. The multiple trains deriving from
a single split one are modeled as different trains performed by the same rolling-stock. Hence, algorithms will impose the route of each train to depart where the route of the previous train arrives, and departure and arrival times to be coherent. For example, consider a network including three stations with four platforms each, and a single track connecting stations. A train allowed to stop at any of these platforms will have 64 alternative routes. Of these routes, 16 will overlap in the first part as they will be passing through the first platform at the first station. Three disjoint sets of overlapping routes can also be defined for the other three platforms at the first station. In the novel modeling, we split this train into four new ones: the first goes from the origin to the first station, the second from the first to the second station, and so on. The first train will have four alternative routes, one reaching each platform. The second train will have 16, to connect each platform of the first station to each platform of the second. The third and the fourth trains will have 16 and 4 routes respectively.In a thorough experimental analysis based on French case studies with different network and timetable characteristics, we assess the impact of the train-based instance reformulation when solving instances through RECIFE-MILP (Pellegrini et al., 2015), a state-of-the-art rtRTMP algorithm. We show that the novel modeling never worsens the algorithm performance and strongly improves them in instances with specific characteristics.

[1] V. Cacchiani, D. Huisman, M. Kidd, L. Kroon, P. Toth, L. Veelenturf and J. Wagenaar, 2014. An overview of recovery models and algorithms for real-time railwayrescheduling. Transp. Res. Part B Methodol. 63, 15–37.
[2] P. Pellegrini, G. Marlière, R. Pesenti, and J. Rodriguez, 2015. RECIFE-MILP: an effective MILP-based heuristic for the real-time railway traffic management problem. Intelligent Transportation Systems, IEEE Transactions on, 16(5):2609–2619.