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

Shahrzad M. Pour*, John H. Drake, Lena Secher Ejlertsen, Kourosh Marjani Rasmussen, Edmund K. Burke

*Corresponding author for this work

    Research output: Contribution to journalJournal articleResearchpeer-review

    319 Downloads (Pure)


    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.
    Original languageEnglish
    JournalEuropean Journal of Operational Research
    Issue number1
    Pages (from-to)341-352
    Number of pages12
    Publication statusPublished - 2018

    Bibliographical note

    This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)


    • Transportation
    • Scheduling
    • Constraint programming
    • Mixed Integer Programming
    • Hybrid approaches

    Cite this