A choice function hyper-heuristic framework for the allocation of maintenance tasks in Danish railways. (May 2018)

• Record Type: Journal Article
• Authors: M. Pour, Shahrzad; Drake, John H.; Burke, Edmund K.
• Is Part Of: Computers & operations research. Volume 93(2018)
• Page Start: 15
• Page End: 26
• Publication Date: 2018-05
• Subjects: Hyper-heuristics -- Maintenance scheduling -- Combinatorial optimisation -- European rail traffic management system; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.09.011
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A real-world maintenance problem from the Danish railway system is introduced. Three methods are used to generate an initial set of task allocations for each crew. Tasks that are distant from the other tasks of a crew member are identified as outliers. A choice function-based selection hyper-heuristic is used to reassign outlying tasks. Results of two hyper-heuristics are presented over 12 benchmark problem instances. Abstract: A new signalling system in Denmark aims at ensuring fast and reliable train operations. However, it imposes very strict time limits on recovery plans in the event of failure. As a result, it is necessary to develop a new approach to the entire maintenance scheduling process. In the largest region of Denmark, the Jutland peninsula, there is a decentralised structure for maintenance planning where the crew start their duties from their home locations rather than starting from a single depot. In this paper, we allocate a set of maintenance tasks in Jutland to a set of maintenance crew members, defining the sub-region that each crew member is responsible for. Two key considerations must be made when allocating tasks to crew members. Firstly a fair balance of workload must exist between crew members. Secondly, the distance between two tasks in the same sub-region must be minimised in order to facilitate a quick response in the case of unexpected failure. We propose a perturbative selection hyper-heuristic framework to improve initial solutions by reassigning outliers (those tasks that are far away) to another crew member at each iteration, using one of five low-level heuristics. The results from two hyper-heuristics, using a number of different initial solution construction methods are presented over a set of 12 benchmark problem instances.