TY - RPRT
T1 - Routing Trains Through Railway Junctions: A New Set Packing Approach
AU - Lusby, Richard
AU - Larsen, Jesper
AU - Ryan, David
AU - Ehrgott, Matthias
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
M3 - Report
BT - Routing Trains Through Railway Junctions: A New Set Packing Approach
PB - Informatics and Mathematical Modelling, Technical University of Denmark, DTU
ER -