ILP formulations for the railway rescheduling problem under large disruptions

AGUSTÍN MOSTEIRO; JUAN JOSÉ MIRANDA BRONT; FEDERICO POUSA

Ciudad Autonoma de Buenos Aires

Workshop; MIP@AR 2016; 2016

Departamento de Computación, FCEyN, UBA

Normal railway operations are often influenced by unexpected situations that affect, for example, the rolling stock and the infrastructure and may cause delays and disruptions in the network. Under these scenarios, one of the key issues is to construct a new disposition timetable to recover from the disruption and to inform the passengers as fast as possible, usually within a few minutes. Due to its complexity, the overall problem is usually divided into three phases which are solved sequentially, namely timetable rescheduling, rolling stock rescheduling and crew rescheduling.There has been a trend in the literature in the last few years to consider MILP as prototypes for automated decision systems to tackle this kind of situations. To the best of our knowledge, most of the research regarding timetable rescheduling is devoted to incorporate new modeling characteristics, but there is limited research focusing on alternative exact algorithms for the problem.In this paper we focus on the timetable rescheduling phase and propose two new MILP formulations. A tailored Branch and Cut algorithm is considered for each formulation, for which preliminary computational results are presenting evaluating the quality of the LP relaxations as well as the overall computing times requried, aiming to evaluate the potential to be applied in practice.