Routing trains through railway junctions: A new set-packing approach

Publication: Research - peer-reviewJournal article – Annual report year: 2011

View graph of relations

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. © 2011 INFORMS.
Original languageEnglish
JournalTransportation Science
Publication date2011
Volume45
Issue2
Pages228-245
ISSN0041-1655
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 3

Keywords

  • column generation, set-packing model, train routing
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 5850825