Automated search methodologies for integrated railway scheduling
The problem of integrated railway scheduling is a very complex problem comprising assignment, selection and scheduling sub-problems. The problem has a large number of complex constraints, many of which contain a large number of non-linear decision boundaries. It is a NP-hard problem that is rarely a...
| Main Author: | |
|---|---|
| Format: | Dissertation (University of Nottingham only) |
| Language: | English |
| Published: |
2014
|
| Online Access: | https://eprints.nottingham.ac.uk/30746/ |
| Summary: | The problem of integrated railway scheduling is a very complex problem comprising assignment, selection and scheduling sub-problems. The problem has a large number of complex constraints, many of which contain a large number of non-linear decision boundaries. It is a NP-hard problem that is rarely addressed in its full form. The model put forth by SNCF railway body in France encompasses a very realistic form of the problem from a business, environmental, and efficiency perspective.
A hyper-heuristic approach was taken to tackle the problem, and a solver was designed and implemented using a multi-Stage hyper-heuristic. The developed solver was tested on real-life data obtained from the SNCF. The problem and instances mimic railway networks in large train stations in France and Europe.
The solver produced a good number of feasible solutions using a small set of low-level-heuristics. The results were compared to those of other solvers competing in the ROADEF 2014 challenge organized by SNCF. A variant of the solver was submitted to the SNCF for the ROADEF Challenge 2014 which obtained third place in the junior category. The performance of the solver and its resulting solutions were analysed and the faults and merits identified with the various possible |
|---|