MILP Reformulations for Train Timetabling and Dispatching: Recent Advancements
by Professor Carlo Mannino, SINTEF Digital, Oslo; University of Oslo, Norway
Abstract: Train timetabling and train dispatching are two very related and central problems in the railways industry. They share a common core problem, that is routing and scheduling trains through a rail network, respecting business rules, while ensuring all safety rules. Mixed integer linear programming (MILP) models for such core problem have been studied and developed for at least a half a century. Nevertheless, you could count the actual real-life implementations on the fingers of one hand. The main reason for this gap between theory and application is simply that the standard models are extremely hard to solve for the size and complexity of real-life instances of some practical interest. Luckily, recent decomposition approaches have proven to be very effective in shortening computational times and reducing this gap. In this keynote we present some recent developments in Benders’ decomposition and reformulation for train timetabling and dispatching. The main idea of this approach is to drop many variables and complicating constraints and replace them with suitable (and hopefully few) constraints in the remaining variables. The new constraints are in correspondence with the directed cycles and trees of a certain graph associated with the instance of train routing and scheduling. In a few recent articles, it is shown how this decomposition approach (or its derivations) can lead to significant speed-ups in the solution process. Successful real-life applications are also presented.
About presenter: Carlo Mannino is senior scientist in the department of mathematics and cybernetics at SINTEF DIGITAL, Oslo, and part-time full professor at the University. He has over 70 publications, including several top journals in mathematical optimization and operations research. His scientific research was focused on mathematical programming approaches for scheduling and network optimization. He has also been interested in practical applications of operations research. He received the EURO Excellence in Practice Award 2009 and the AIRO Best Application Paper award in 2014 for his work on railways optimization, and the INFORMS Best Telecommunication Paper Award 2014. He is associate editor of Operations Research.
