Optimal Train Dispatching by Benders’-Like Reformulation
Leonardo Lamorgese (),
Carlo Mannino () and
Mauro Piacentini ()
Additional contact information
Leonardo Lamorgese: SINTEF ICT, Oslo 0316, Norway
Carlo Mannino: SINTEF ICT, Oslo 0316, Norway
Mauro Piacentini: OptRail, Rome 00131, Italy
Transportation Science, 2016, vol. 50, issue 3, 910-925
Abstract:
Train movements on railway lines are generally controlled by human dispatchers. Because disruptions often occur, dispatchers make real-time scheduling and routing decisions in an attempt to minimize deviations from the official timetable. This optimization problem is called train dispatching. We represent it as a mixed integer linear programming model, and solve it with a Benders’-like decomposition within a suitable master/slave scheme. Interestingly, the master and the slave problems correspond to a macroscopic and microscopic representation of the railway, recently exploited in heuristic approaches to the problem. The decomposition, along with some new modeling ideas, allowed us to solve real-life instances of practical interest to optimality. Automatic dispatching systems based on our macro/micro decomposition—in which both master and slave are solved heuristically—have been in operation in several Italian lines since 2011. The exact approach described in this paper outperforms such systems on our test bed of real-life instances. Furthermore, a system based on another version of the exact decomposition approach has been in operation since February 2014 on a line in Norway.
Keywords: logic Benders’ decomposition; integer programming; railway optimization (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)
Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2015.0605 (application/pdf)
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:inm:ortrsc:v:50:y:2016:i:3:p:910-925
Access Statistics for this article
More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().