Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Routing Trains Through Railway Junctions: A New Set-Packing Approach
AU - Lusby, Richard M.
AU - Larsen, Jesper
AU - Ryan, David
AU - Ehrgott, Matthias
PY - 2011/5/1
Y1 - 2011/5/1
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 merge, intersect, and split. The number of possible routings makes this a very complicated problem. We show how the problem can be formulated as a set-packing model with a resource-based constraint system. We prove that this formulation is tighter than the conventional node-packing model, and develop a branch-and-price algorithm that exploits the structure of the set-packing model. A discussion of the variable generation phase, as well as a pricing routine in which these variables are represented by tree structures, is also described. Computational experiments on 25 random timetables show this to be an efficient approach.
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 merge, intersect, and split. The number of possible routings makes this a very complicated problem. We show how the problem can be formulated as a set-packing model with a resource-based constraint system. We prove that this formulation is tighter than the conventional node-packing model, and develop a branch-and-price algorithm that exploits the structure of the set-packing model. A discussion of the variable generation phase, as well as a pricing routine in which these variables are represented by tree structures, is also described. Computational experiments on 25 random timetables show this to be an efficient approach.
KW - train routing
KW - set-packing model
KW - column generation
U2 - 10.1287/trsc.1100.0362
DO - 10.1287/trsc.1100.0362
M3 - Journal article
VL - 45
SP - 228
EP - 245
JO - Transportation Science
JF - Transportation Science
SN - 0041-1655
IS - 2
ER -