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 ().