A conditional time-intervals formulation of the real-time Railway Traffic Management Problem

In this session, we will tackle the real-time Railway Traffic Management Problem (rtRTMP) by viewing it as a scheduling, but also a routing problem. RtRTMP is the problem of finding optimal choices for train schedules and routes to minimize delays due to conflicts. The authors present a new Constraint Programming (CP) algorithm for the rtRTMP. The new formulation at the basis of this algorithm exploits the concept of conditional time-interval variables provided in the CP Optimizer library.

The algorithm performance is compared to one of the state-of-the-art algorithms RECIFE-MILP based on a mixed-integer linear programming (MILP) formulation. Moreover, a hybridization of RECIFE-MILP and the proposed algorithm is proposed. It often outperforms the two individual approaches, while the opposite never happens.

Briefly, in the end, I will also identify the differences between the problem that is tackled here and the Shunt Routing Problem at NS, the main topic of my thesis.

Relevant papers

A conditional time-intervals formulation of the real-time Railway Traffic Management Problem

Grégory Marlière, Sonia Sobieraj Richard, Paola Pellegrini, and 1 more author

Control Engineering Practice, Jul 2023

Abs HTML

This paper tackles the real-time Railway Traffic Management Problem (rtRTMP). It is the problem of finding optimal choices for train schedules and routes to minimize delays due to conflicts. We present a new Constraint Programming (CP) algorithm for the rtRTMP. The new formulation at the basis of this algorithm exploits the concept of conditional time-interval variables provided in the CP Optimizer library. A time-interval variable assumes a value representing either the time interval in which an activity is executed, or a quantity “⊥” indicating that the activity is non-executed. The new formulation exploits this new kind of variables, and specific constraint propagation techniques contribute to the efficiency of the algorithm. This efficiency is assessed in a wide experimental analysis based on five railway control areas. The algorithm performance is compared to the one of the state-of-the-art algorithm RECIFE-MILP based on a mixed-integer linear programming (MILP) formulation. Moreover, an hybridization of RECIFE-MILP and the proposed algorithm is proposed. It often outperforms the two individual approaches, while the opposite never happens.