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.