A perturbative clustering hyper-heuristic framework for the Danish railway system

A new signaling system in Denmark aims to ensure fast and reliable train operation, imposing very strict time limits on recovery plans. This makes it necessary to rethink the whole maintenance scheduling process. In the largest region of Denmark, the Jutland peninsula, there is a decentralized structure for maintenance planning, where the crew start their duties from different locations rather than starting from a single depot. In this paper, we partition the Jutland problem into subregions before the scheduling phase, according to the tasks and crew locations. To undertake this region splitting, we propose a perturbative clustering hyper-heuristic framework. The framework improves an initial solution by reassigning outliers (those tasks that are far away) to a better cluster choice at each iteration while taking balanced crews workloads into account. The framework introduces five lowlevel heuristics and employs an adaptive choice function as a robust learning mechanism. The results of adaptive clustering hyper-heuristic are compared with two exact and heuristic assignment algorithms from the literature and with the random hyper-heuristic framework on 12 datasets. In comparison with the exact formulation, the proposed framework could obtain promising results and solved the data instances up to 5000 number of tasks. In comparison with heuristic assignment and the random hyper-heuristic, the framework yielded approximately 11%, 27% and 10%,13% mprovement on total distance and the maximum distance availability, respectively. Finally, to assess the closeness of the tasks within each cluster the compactness measure was compared across the three different solutions.