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

Abstract 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 to generate initial feasible solutions to feed as ‘warm start’ solutions to a Mixed Integer Programming solver for further improvement. We apply this hybrid framework to a section of the Danish rail network and benchmark our results against both direct application of a Mixed Integer Programming solver and modelling the problem as a Constraint Optimisation Problem. Whereas the current practice of using a general purpose Mixed Integer Programming 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 Mixed Integer Programming solver to improve the initial solutions generated by Constraint Programming is shown to be significantly superior to addressing the problem as a Constraint Optimisation Problem.