ILP formulations for the railway rescheduling problem under large disruptions

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

Salerno

Simposio; International Symposium on Combinatorial Optimization 2016; 2016

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. One of the major issues involves the feasibility of the solution obtained in one phase regarding the constraints imposed by the following one. Therefore, the models try to include, at least in a relaxed fashion, some of the constraints involved in successive phases in order to provide a more robust solution. 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. This research builds mainly upon the works by Louwerse and Huisman (2014) and Veelenturf et al. (2015). Louwerse and Huisman (2014) consider the timetable rescheduling problem on a railway line, including also some general aspects of the rolling stock rescheduling in the timetabling phase. Veelenturf et al. (2015) extend this research by considering networks with a general structure, not necessarily a line, and include as well the possibility of re-routing a train and therefore modifying its original route. In both cases, the results show that the approach produces good quality solutions in reasonable computing times. In both cases, despite the differences regarding the particular characteristics modeled, the timetable rescheduling problem is formulated by means of an event-activity network which is later translated into an MILP formulation, aiming to obtain the disposition timetable. 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 (see Cacchiani et al. (2015) for an updated review). Improvements in the algorithms could allow to consider larger railway networks as well as to consider certain scenarios where computing times exceed the available time. Our contribution aims to that direction and we propose two alternative MILP formulations. One of them is based on the so-called Time-Index Formulation considered in Dash et al. (2012) for the Traveling Salesman Problem with Time Windows. This connection between the two problems allows to adapt and extend some of the results previoulsy obtained to the context of railway rescheduling. We further present preliminary computational results, including a comparison regarding the overall computing times and quality of the LP relaxations, and discuss future research directions.