TY - JOUR
T1 - A Branch-and-Price algorithm for railway rolling stock rescheduling
AU - Lusby, Richard Martin
AU - Haahr, Jørgen Thorlund
AU - Larsen, Jesper
AU - Pisinger, David
PY - 2017
Y1 - 2017
N2 - How to best reschedule their fleet of rolling stock units during a disruption is an optimization problem regularly faced by railway operators. Despite the problem’s high complexity, it is still usually solved manually. In this paper we propose a path based mathematical formulation and solve it using a Branch-and-Price algorithm. We demonstrate that, unlike flow based approaches, our formulation is more easily extended to handle certain families of constraints, such as train unit maintenance restrictions. The proposed algorithm is benchmarked on several real-life instances provided by the suburban railway operator in Copenhagen, DSB S-tog. When used in combination with a lower bound method taken from the literature we show that near-optimal solutions to this rescheduling problem can be found within a few seconds. Furthermore, we show that the proposed methodology can be used, with minor modification, on a tactical planning level, where it produces near-optimal rolling stock schedules in minutes of CPU time.
AB - How to best reschedule their fleet of rolling stock units during a disruption is an optimization problem regularly faced by railway operators. Despite the problem’s high complexity, it is still usually solved manually. In this paper we propose a path based mathematical formulation and solve it using a Branch-and-Price algorithm. We demonstrate that, unlike flow based approaches, our formulation is more easily extended to handle certain families of constraints, such as train unit maintenance restrictions. The proposed algorithm is benchmarked on several real-life instances provided by the suburban railway operator in Copenhagen, DSB S-tog. When used in combination with a lower bound method taken from the literature we show that near-optimal solutions to this rescheduling problem can be found within a few seconds. Furthermore, we show that the proposed methodology can be used, with minor modification, on a tactical planning level, where it produces near-optimal rolling stock schedules in minutes of CPU time.
U2 - 10.1016/j.trb.2017.03.003
DO - 10.1016/j.trb.2017.03.003
M3 - Journal article
VL - 99
SP - 228
EP - 250
JO - Transportation Research. Part B: Methodological
JF - Transportation Research. Part B: Methodological
SN - 0191-2615
ER -