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.
|
PDF
1MB |
| 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: | https://purl.utwente.nl/essays/77267 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page