Efficient train re-routing and rescheduling: Valid inequalities and reformulation of RECIFE-MILP. (February 2019)

• Record Type: Journal Article
• Authors: Pellegrini, Paola; Pesenti, Raffaele; Rodriguez, Joaquin
• Is Part Of: Transportation research. Volume 120(2019)
• Page Start: 33
• Page End: 48
• Publication Date: 2019-02
• Subjects: Transportation -- Real-time railway traffic management problem -- Train re-routing and rescheduling -- Mixed-integer linear programming -- Valid inequalities; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2018.12.008
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: We propose valid inequalities for a MILP model for the rtRTMP. They allow a reformulation and a reduction of the number of binary variables. They may represent all facets of the convex hull in the subspace of binary variables. Experiments show that the reformulation improves significantly the performance. Abstract: The real-time Railway Traffic Management problem consists in finding suitable train routes and schedules to minimize delay propagation due to traffic perturbations. RECIFE-MILP is a mixed integer linear programming based heuristic for this problem which has proven to be effective in various contexts. However, when instances are very large or difficult, the performance of the algorithm may worsen. In this paper, we propose valid inequalities to boost the performance of RECIFE-MILP. These valid inequalities link the routing and scheduling binary variables. We also provide an instance in which they are able to represent all the facets of the projection of the convex hull of the problem in the subspace of the binary variables. Moreover, they allow reformulating the model based on a reduced number of scheduling binary variables. In an experimental analysis based on realistic instances representing traffic in four French infrastructures, we observe that the merit of addition of valid inequalities depends on the specific case-study at hand, and that the reduction of the number of binary variables in general boosts the performance of RECIFE-MILP significantly.