Using SCIP as a branch-and-price framework to solve the train timetable rescheduling problem
Channel: The SCIP Optimization Suite
Date: 06/07/2020

Edwin Reynolds
Lancaster University, United Kingdom

Abstract:
By rerouting and retiming trains in real-time, the propagation of reactionary delay in complex station areas can be reduced. In this study, we propose a new optimisation model and solution algorithm that can be used to determine the best combination of route and schedule changes to make. Whilst several models have been proposed to tackle this problem, existing models either lack sufficient detail, or cannot be solved to optimality within the stringent time limits asociated with a real-time environment. We formulate the problem as a multicommodity flow problem on a time-space graph with a novel representation of the track capacity constraints and a new objective function based on utility maximisation. We present a tailored branch-and-price solution algorithm and test it on a set of new instances based on real data. Our experiments show that most of these instances can be solved to optimality within 20 seconds, and provably near-optimal solutions can be found for the remainder.