Constraint Programming and Mixed Integer Linear Programming for Rescheduling Trains under Disrupted Operations A Comparative Analysis of Models, Solution Methods, and Their Integration

摘要

The problem of rescheduling trains under disrupted operations has received more attention in the last years because of the increasing demand in railway transportation. Railway networks are more and more saturated and the probability that delayed trains affect others is large. Therefore, it is very important to react after incidents by recalculating new arrival/departure times and reassigning tracks/platforms with the aim of minimizing the effect of propagation of incidents.rnIt is possible to define the rescheduling railway problem as follows: given a set of trains, a railway network, an original schedule (i.e., arrival/departure times of every train as well as the complete assignment of tracks and platforms), and known delays of one or several trains; the problem is to create a new provisional schedule by minimizing the difference with the original plan respecting several operational and commercial constraints. We propose to use an objective function that penalizes delays, changes of tracks/platforms, and unplanned stops; all of them referred to the original (unperturbed) schedule.rnWe present two different approaches: MIP (Mixed Integer Linear Programming) and CP (Constraint Programming). The solutions of both are comparable because they use the same objective function. Nevertheless, the definition of decision variables and constraints differs significantly.rnOn the one hand, the MIP uses an extension of a formulation originally presented in [5]. The more interested reader will find a full description of the model in our previous work [3]. This model includes many practical rules and constraints, which explains its relative complexity compared to other models presented in the literature. It supports allocation of tracks and platforms, connection of trains, bidirectional multi-track lines, and extra time for accelerating and braking.