An Exact Decomposition Approach for the Real-Time Train Dispatching Problem

Leonardo Lamorgese () and Carlo Mannino ()
Additional contact information
Leonardo Lamorgese: Department of Applied Mathematics, SINTEF ICT, Oslo, Norway 0314
Carlo Mannino: Department of Applied Mathematics, SINTEF ICT, Oslo, Norway 0314

Operations Research, 2015, vol. 63, issue 1, 48-64

Abstract: Trains’ movements on a railway network are regulated by official timetables. Deviations and delays occur quite often in practice, demanding fast rescheduling and rerouting decisions in order to avoid conflicts and minimize overall delay. This is the real-time train dispatching problem. In contrast with the classic “holistic” approach, we show how to decompose the problem into smaller subproblems associated with the line and the stations. This decomposition is the basis for a master-slave solution algorithm, in which the master problem is associated with the line and the slave problem is associated with the stations. The two subproblems are modeled as mixed integer linear programs, with specific sets of variables and constraints. Similarly to the classical Benders’ decomposition approach, slave and master communicate through suitable feasibility cuts in the variables of the master. Extensive tests on real-life instances from single and double-track lines in Italy showed significant improvements over current dispatching performances. A decision support system based on this exact approach has been in operation in Norway since February 2014 and represents one of the first operative applications of mathematical optimization to train dispatching.

Keywords: train dispatching; railway optimization; discrete mathematics (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2014.1327 (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:oropre:v:63:y:2015:i:1:p:48-64

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().