Premium
A MIP‐based local search method for the railway rescheduling problem
Author(s) -
AcunaAgost Rodrigo,
Michelon Philippe,
Feillet Dominique,
Gueye Serigne
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20384
Subject(s) - train , integer programming , solver , schedule , computer science , mathematical optimization , impossibility , limit (mathematics) , operations research , mathematics , mathematical analysis , cartography , political science , law , geography , operating system
For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact, but, in some cases, mainly in dense networks, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this article, we present the railway rescheduling problem as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect. We investigate the solution of this problem through a mixed‐integer programming (MIP) formulation. Because of the impossibility for solving it exactly just using a standard MIP solver, we propose to limit the search space around the original nondisrupted schedule by hard and soft fixing of integer variables with local‐branching‐type cuts. Different variations of the method are compared to a right‐shift rescheduling policy in two different networks located in France and Chile. The experimental results are also used to study the impact of different objectives on the total delay. © 2010 Wiley Periodicals, Inc. NETWORKS, 2011