Routing Trains Through Railway Junctions: A New Set-Packing Approach

Richard Lusby (), Jesper Larsen (), David Ryan () and Matthias Ehrgott ()
Additional contact information
Richard Lusby: Department of Management Engineering, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
Jesper Larsen: Department of Management Engineering, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
David Ryan: Department of Engineering Science, The University of Auckland, Auckland 1142, New Zealand
Matthias Ehrgott: Department of Engineering Science, The University of Auckland, Auckland 1142, New Zealand

Transportation Science, 2011, vol. 45, issue 2, 228-245

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 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.

Keywords: train routing; set-packing model; column generation (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0362 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:45:y:2011:i:2:p:228-245

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().