Integrating Train Driver Scheduling into Local Search for the Train Unit Shunting Problem
K.E. Vaessen (TU Delft - Electrical Engineering, Mathematics and Computer Science)
M.M. de Weerdt – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A. Berger – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Sam Hesselmans – Mentor (Nederlandse Spoorwegen)
R.M.P. Goverde – Graduation committee member (TU Delft - Civil Engineering & Geosciences)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Automatic planning for railway shunting yards in the Netherlands is a challenging problem, as these yards form a critical link between rolling stock circulation and the timetable. Trains must be decoupled, coupled, serviced, and departed within tight time windows, while infrastructure and train drivers are limited. The resulting planning problem is large-scale, highly constrained, and characterized by strong interdependencies between operational and driver decisions. In the current state-of-the-art approach, driver scheduling is handled by a heuristic procedure embedded within a local search algorithm. While efficient, this restricts the decision space and may yield suboptimal plans.
This thesis investigates how integrating driver-scheduling decisions into the main local search affects solution quality and search performance. Several integration mechanisms are presented, with increasing levels of integration of driver scheduling decisions. Computational experiments on realistic instances show that integrating driver decisions into the local search consistently improves performance compared to the state-of-the-art approach. Under small time budgets, the greatest improvements are obtained when only part of the driver decision space is integrated, allowing the search to correct harmful heuristic decisions while keeping the search space manageable. With larger time budgets, more integrated methods catch up, indicating that the richer decision space can be exploited when sufficient time is available.
To manage the increase in search space complexity, a novel two-stage search scheme is introduced in which the algorithm first optimizes while keeping driver decisions heuristically decided, and subsequently activates explicit driver-related decision variables. Experiments show that dividing the available computation time between these two stages yields better results than allocating the entire time budget to either stage. This demonstrates that progressive enlargement of the decision space can effectively balance model expressiveness and computational tractability.