Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1120.90324
Caprara, Alberto; Monaci, Michele; Toth, Paolo; Guida, Pier Luigi
A Lagrangian heuristic algorithm for a real-world train timetabling problem. (English)
[J] Discrete Appl. Math. 154, No. 5, 738-753 (2006). ISSN 0166-218X

Summary: 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: $\bullet$ Manual block signaling for managing a train on a track segment between two consecutive stations. $\bullet$ Station capacities, i.e., maximum number of trains that can be present in a station at the same time. $\bullet$ 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. $\bullet$ 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.

MSC 2000:: *90B35 Scheduling theory
90C59 Approximation methods and heuristics

Keywords: Train scheduling; Path allocation; Lagrangian relaxation; Lagrangian heuristic; Computational results

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]