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

Paola Pellegrini, Raffaele Pesenti and Joaquin Rodriguez

Transportation Research Part B: Methodological, 2019, vol. 120, issue C, 33-48

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.

Keywords: Transportation; Real-time railway traffic management problem; Train re-routing and rescheduling; Mixed-integer linear programming; Valid inequalities (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261518307276
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:120:y:2019:i:c:p:33-48

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2018.12.008

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().