This paper focuses on the development of metaheuristic algorithms for the realtime 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 NPhard, 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 conflictfree 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 branchandbound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by rerouting some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be rerouted 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 stateoftheart tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays. © 2016 Elsevier Ltd.
This paper focuses on the development of metaheuristic algorithms for the realtime 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 NPhard, 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 conflictfree 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 branchandbound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by rerouting some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be rerouted 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 stateoftheart tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays.
Sama', M., D'Ariano, A., Pacciarelli, D., Corman, F. (2017). A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations. COMPUTERS & OPERATIONS RESEARCH, 78, 480499 [10.1016/j.cor.2016.02.008].
A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations
SAMA', MARCELLA;D'ARIANO, Andrea;PACCIARELLI, Dario;CORMAN, FRANCESCO
20170101
Abstract
This paper focuses on the development of metaheuristic algorithms for the realtime 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 NPhard, 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 conflictfree 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 branchandbound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by rerouting some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be rerouted 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 stateoftheart tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays.File  Dimensione  Formato  

Samà_submitted.pdf
accesso aperto
Tipologia:
Documento in Preprint
Licenza:
Creative commons
Dimensione
912.91 kB
Formato
Adobe PDF

912.91 kB  Adobe PDF  Visualizza/Apri 
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.