A hybrid Constraint Programming/Mixed Integer Programming framework for the preventive signaling maintenance crew scheduling problem

A railway signaling system is a complex and interdependent system which should ensure the safe operation of trains. We introduce and address a mixed integer optimisation model for the preventive signal maintenance crew scheduling problem in the Danish railway system. The problem contains many practical constraints, such as temporal dependencies between crew schedules, the splitting of tasks across multiple days, crew competency requirements and several other managerial constraints. We propose a novel hybrid framework using Constraint Programming (CP) to generate initial feasible solutions to feed as ‘warm start’ solutions to a Mixed Integer Programming (MIP) solver for further optimisation. We apply the CP/MIP framework to a section of the Danish rail network and benchmark our results against both direct application of a MIP solver and modelling the problem as a Constraint Optimisation Problem (COP). Whereas the current practice of using a general purpose MIP solver is only able to solve instances over a two-week planning horizon, the hybrid framework generates good results for problem instances over an eight-week period. In addition, the use of a MIP solver to improve the initial solutions generated by CP is shown to be vastly superior to solving the problem as a COP.