Metaheuristics for Real-Time Near-Optimal Train Scheduling and Routing

This paper focuses on metaheuristic algorithms for the real-time traffic management problem of scheduling and routing trains in a complex and busy railway network. Since the problem is strongly NP-hard, heuristic algorithms are developed to compute good quality solutions in a short computation time. In this work, a number of algorithmic improvements are implemented in the AGLIBRARY optimization solver, that manages trains at the microscopic level of block sections and block signals and at a precision of seconds. The solver outcome is a detailed conflict-free train schedule, being able to avoid deadlocks and to minimize train delays. The proposed algorithmic framework starts from a good initial solution for the train scheduling problem with fixed routes, obtained via a truncated branch-and-bound algorithm. Variable neighbourhood search and tabu search metaheuristics are then applied to improve the solution by re-routing some trains. Computational experiments are performed on a UK railway network with dense traffic in order to compare the two types of studied metaheuristics.


  • English

Media Info

  • Media Type: Web
  • Features: References;
  • Pagination: pp 1678-1683
  • Monograph Title: 18th International IEEE Conference on Intelligent Transportation Systems (ITSC 2015)

Subject/Index Terms

Filing Info

  • Accession Number: 01602376
  • Record Type: Publication
  • ISBN: 9781467365956
  • Files: TRIS
  • Created Date: May 2 2016 3:24PM