The Train Timetabling Problem (TTP) aims at determining an optimal timetable for a set of trains which does not violate track capacities and satisfies some operational constraints. In this paper, we describe the design of a train timetabling system that takes into account several additional constraints that arise in real-world applications. In particular, we address the following issues: - Manual block signaling for managing a train on a track segment between two consecutive stations. - Station capacities, i.e., maximum number of trains that can be present in a station at the same time. - Prescribed timetable for a subset of the trains, which is imposed when some of the trains are already scheduled on the railway line and additional trains are to be inserted. - Maintenance operations that keep a track segment occupied for a given period. We show how to incorporate these additional constraints into a mathematical model for a basic version of the problem, and into the resulting Lagrangian heuristic. Computational results on real-world instances from Rete Ferroviaria Italiana (RFI), the Italian railway infrastructure management company, are presented.

A Lagrangian Heuristic Algorithm for a Real-World Train Timetabling Problem

CAPRARA, ALBERTO;MONACI, MICHELE;TOTH, PAOLO;
2006

Abstract

The Train Timetabling Problem (TTP) aims at determining an optimal timetable for a set of trains which does not violate track capacities and satisfies some operational constraints. In this paper, we describe the design of a train timetabling system that takes into account several additional constraints that arise in real-world applications. In particular, we address the following issues: - Manual block signaling for managing a train on a track segment between two consecutive stations. - Station capacities, i.e., maximum number of trains that can be present in a station at the same time. - Prescribed timetable for a subset of the trains, which is imposed when some of the trains are already scheduled on the railway line and additional trains are to be inserted. - Maintenance operations that keep a track segment occupied for a given period. We show how to incorporate these additional constraints into a mathematical model for a basic version of the problem, and into the resulting Lagrangian heuristic. Computational results on real-world instances from Rete Ferroviaria Italiana (RFI), the Italian railway infrastructure management company, are presented.
DISCRETE APPLIED MATHEMATICS
A. Caprara; M. Monaci; P. Toth; P.L. Guida
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/25920
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 162
  • ???jsp.display-item.citation.isi??? 141
social impact