Optimization methods for routing trains through railway junctions

Show simple item record

dc.contributor.advisor Ryan, David en
dc.contributor.advisor Ehrgott, Matthias en
dc.contributor.author Lusby, Richard M en
dc.date.accessioned 2014-02-20T23:12:12Z en
dc.date.available 2014-02-20T23:12:12Z en
dc.date.issued 2008 en
dc.identifier.citation Thesis (PhD--Engineering Science)--University of Auckland, 2008 en
dc.identifier.uri http://hdl.handle.net/2292/21687 en
dc.description Full text is available to authenticated members of The University of Auckland only. en
dc.description.abstract Efficiently coordinating the often large number of interdependent, timetabled train movements within a railway junction, while satisfying a number of operational requirements, is one of the most important problems faced by a railway company. This problem, which is known as the problem of routing trains through railway junctions, and which is the focus of this thesis, arises at all levels in the planning process for a railway company and directly impacts the capacity of the entire railway network as well as the quality of the rail service provided. In this thesis we describe a generalized set packing formulation of the problem and develop a branch-and-price based solution approach. The formulation is characterized by a resource based constraint system that allows one to explicitly represent the movement of trains over time through a junction and is fundamentally different to all other previous approaches. The train movements are modelled using acyclic time-space networks. We show that our approach should provide a stronger formulation and demonstrate, through computational experiments, that the improvement in the bound obtained from the linear programming relaxation can be as high as 66.7%. The solution method uses ideas from column generation as well as the theory of duality and utilizes a concept that we term the dual representation of a basic feasible solution. The approach is tailored to circumvent the computational overhead in working with the large basis of the proposed model and equates an iteration of the standard revised simplex in the primal with the addition of the variable's constraint representation in the dual. We compare and contrast the proposed methodology with that of the more conventional conflict graph approach for this problem. We demonstrate that the structure of the resource based constraint system of our model is such that it can easily and dynamically include spatial and/or temporal changes to train movements. By showing that the methodology can be used in a real-time setting as a disruption tool, we highlight its superiority over the conflict graph methodology. A real life test instance arising in Germany and supplied by the major German railway company, Deutsche Bahn, indicates the efficiency of the proposed approach by confirming that practical problems can be solved to within a few percent of optimality in reasonable time. en
dc.publisher ResearchSpace@Auckland en
dc.relation.ispartof PhD Thesis - University of Auckland en
dc.relation.isreferencedby UoA99187558214002091 en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. en
dc.rights Restricted Item. Available to authenticated members of The University of Auckland. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.title Optimization methods for routing trains through railway junctions en
dc.type Thesis en
thesis.degree.discipline Engineering Science en
thesis.degree.grantor The University of Auckland en
thesis.degree.level Doctoral en
thesis.degree.name PhD en
dc.date.updated 2014-02-19T00:04:49Z en
dc.rights.holder Copyright: The author en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace