Routing Trains Through Railway Junctions: A New Set Packing Approach

Richard Lusby, Jesper Larsen, David Ryan, Matthias Ehrgott

    Research output: Book/ReportReportResearchpeer-review

    331 Downloads (Pure)


    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.
    Original languageEnglish
    PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
    Publication statusPublished - 2006


    Dive into the research topics of 'Routing Trains Through Railway Junctions: A New Set Packing Approach'. Together they form a unique fingerprint.

    Cite this