Lower and upper bound algorithms for the real-time train scheduling and routing problem in a railway network

M. Samà, A. D'Ariano, D Pacciarelli, F. Corman

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

4 Citations (Scopus)

Abstract

This paper focuses on the development of new algorithms for the real-time train scheduling and routing problem in a complex and busy railway network. Since this is a strongly NP-hard problem and practical size instances are complex, simple heuristics are typically adopted in practice to compute feasible but low quality schedules in a short computation time. In order to compute good quality solutions, we consider a mixed-integer linear programming formulation of the problem and solve it with a commercial solver. However, the resolution of this formulation by a commercial solver often takes a too long computation time. Therefore, a new methodology based on the relaxation of some train routing constraints in the formulation is proposed for the quick computation of a good quality lower bound. The lower bound solution is then transformed via a constructive metaheuristic into a feasible schedule, representing a good quality upper bound to the problem. Computational experiments are performed on several disturbed traffic situations for two practical case studies from the Dutch and British railways. The results show that the new lower and upper bounds are computed in a few seconds and are often of similar quality to the ones computed by the commercial solver in hours of computation.

Original languageEnglish
Title of host publicationIFAC-PapersOnLine - 14th IFAC Symposium on Control in Transportation Systems (CTS 2016)
EditorsTankut Acarman
PublisherElsevier
Pages215-220
DOIs
Publication statusPublished - 2016
Event14th IFAC Symposium on Control in Transportation Systems - ITU Faculty of Architecture, Istanbul, Turkey
Duration: 18 May 201620 May 2016
http://www.cts2016.org/en/

Publication series

NameIFAC-PapersOnLine
Number3
Volume49
ISSN (Print)2405-8963

Conference

Conference14th IFAC Symposium on Control in Transportation Systems
Abbreviated titleCTS 2016
CountryTurkey
CityIstanbul
Period18/05/1620/05/16
Internet address

Keywords

  • Disjunctive Programming
  • Metaheuristics
  • Real-Time Railway Traffic Management

Fingerprint Dive into the research topics of 'Lower and upper bound algorithms for the real-time train scheduling and routing problem in a railway network'. Together they form a unique fingerprint.

  • Cite this

    Samà, M., D'Ariano, A., Pacciarelli, D., & Corman, F. (2016). Lower and upper bound algorithms for the real-time train scheduling and routing problem in a railway network. In T. Acarman (Ed.), IFAC-PapersOnLine - 14th IFAC Symposium on Control in Transportation Systems (CTS 2016) (pp. 215-220). (IFAC-PapersOnLine; Vol. 49, No. 3). Elsevier. https://doi.org/10.1016/j.ifacol.2016.07.036