A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations

M Sama, A D'Ariano, F Corman, D Pacciarelli

Research output: Contribution to journalArticleScientificpeer-review

77 Citations (Scopus)

Abstract

This paper focuses on the development of metaheuristic algorithms for the real-time traffic management problem of scheduling and routing trains in complex and busy railway networks. This key optimization problem can be formulated as a mixed integer linear program. However, since the problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY optimization solver in order to improve the possibility of finding good quality solutions quickly. The optimization solver manages trains at the microscopic level of block sections and at a precision of seconds. The solver outcome is a detailed conflict-free train schedule, being able to avoid deadlock situations 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 or tabu search algorithms are then applied to improve the solution by re-routing some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be re-routed and the available routes. Computational experiments are performed on railway networks from different countries and various sources of disturbance. The new algorithms often outperform a state-of-the-art tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays.
Original languageEnglish
Pages (from-to)480-499
JournalComputers & Operations Research
Volume78 (2017)
DOIs
Publication statusPublished - 2016

Fingerprint

Dive into the research topics of 'A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations'. Together they form a unique fingerprint.

Cite this