Routing Trains Through Railway Junctions: A New Set Packing Approach

Routing Trains Through Railway Junctions: A New Set Packing Approach
Richard Lusby, Jesper Larsen, David Ryan, Matthias Ehrgott
Abstract	The problem of routing trains through railway junctions is an integral part of railway operations. Large junctions are highly interconnected networks of track where multiple railway lines meet, intersect, and split. The number of possible routings makes this a very complicated problem. Here we show how the problem can be formulated as a set packing model. To exploit the structure of the problem we present a solution procedure which entails solving the dual of this formulation through the dynamic addition of violated cuts (primal variables). A discussion of the variable (train path) generation phase, as well as an efficient pricing routine in which these variables are represented by tree structures is also included. We illustrate the proposed methodology on an example junction with encouraging results. The decision support system currently being developed will enable planners to solve strategic, tactical, and operational level variants of the problem.
Type	Technical report
Year	2006
Publisher	Informatics and Mathematical Modelling, Technical University of Denmark, DTU
Address	Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby
Series	IMM-Technical Report-2006-21
Electronic version(s)	[pdf]
BibTeX data	[bibtex]
IMM Group(s)	Operations Research