University of Twente Student Theses


Train routing at the Shunt Yard : a Disjoint Paths approach

Hove, E.M. van (2019) Train routing at the Shunt Yard : a Disjoint Paths approach.

[img] PDF
Abstract:This study considers the Shunt Routing Problem, which is to find routes through the topology of a shunt yard. We model this problem as a Disjoint Paths Problem (DPP) on a time-expanded network. A path through this network corresponds to a route through the infrastructure of the shunt yard in terms of time, location and direction. Additional constraints of a forbidden pair-form are needed to model the problem properly. Both, the DPP as well as the Impossible Pair constrained Path problem are NP-complete. We solve the problem using an ILP formulation and solver CPLEX. Results of experiments on twelve instances on stations Enschede and Eindhoven (the Netherlands) are promising, since the Disjoint Paths approach succeeds in finding schedules for significantly more train movements than the current algorithm does. Several heuristic methods are investigated to speed up the algorithm substantially, so that this new approach becomes applicable for practical implementation.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:30 exact sciences in general, 31 mathematics, 50 technical science in general, 55 traffic technology, transport technology
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page