A constructive framework for the preventive signalling maintenance crew scheduling problem in the Danish railway system

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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

62 Downloads (Pure)


In this article, we consider the problem of planning preventive maintenance of railway signals in Denmark. This case is particularly relevant as the entire railway signalling system is currently being upgraded to the new European Railway Traffic Management System (ERTMS) standard. This upgrade has significant implications for signal maintenance scheduling in the system. We formulate the problem as a multi-depot vehicle routing and scheduling problem with time windows and synchronisation constraints, in a multi-day time schedule. The requirement that some tasks require the simultaneous presence of more than one engineer means that task synchronisation must be considered. A multi-stage constructive framework is proposed, which first distributes maintenance tasks using a clustering formulation. Following this, a Constraint Programming (CP) based approach is used to generate feasible monthly plans for large instances of practical interest. Experimental results indicate that the proposed framework can generate feasible solutions and schedule a monthly plan of up to 1000 tasks for eight crew members, in a reasonable amount of computational time.
Original languageEnglish
JournalJournal of the Operational Research Society
Issue number11
Pages (from-to)1965-1982
Publication statusPublished - 2019

Cite this