Routing Trains Through Railway Junctions: A New Set Packing Approach

Richard Lusby, Jesper Larsen, David Ryan, Matthias Ehrgott

AbstractThe 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.
TypeTechnical report
Year2006
PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
AddressRichard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby
SeriesIMM-Technical Report-2006-21
Electronic version(s)[pdf]
BibTeX data [bibtex]
IMM Group(s)Operations Research