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.

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 sub-space 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. (C) 2019 Elsevier Ltd. All rights reserved.

Efficient train re-routing and rescheduling: valid inequalities and reformulation of RECIFE-MILP

Raffaele Pesenti;
2019

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.
File in questo prodotto:
File Dimensione Formato  
PellegriniPesentiRodriguez.pdf

non disponibili

Descrizione: bozza finale post-referaggio
Tipologia: Documento in Post-print
Licenza: Accesso chiuso-personale
Dimensione 746.43 kB
Formato Adobe PDF
746.43 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/3708789
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
social impact