A three-phase heuristic for the fairness-oriented crew rostering Problem

Thomas Breugem, Thomas Schlechte, Christof Schulz, Ralf Borndoerfer

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The Fairness-Oriented Crew Rostering Problem (FCRP) considers the joint optimization of attractiveness and fairness in cyclic crew rostering. Like many problems in scheduling and logistics, the combinatorial complexity of cyclic rostering causes exact methods to fail for large-scale practical instances. In case of the FCRP, this is accentuated by the additionally imposed fairness requirements. Hence, heuristic methods are necessary. We present a three-phase heuristic for the FCRP combining column generation techniques with variable-depth neighborhood search. The heuristic exploits different mathematical formulations to find feasible solutions and to search for improvements. We apply our methodology to practical instances from Netherlands Railways (NS), the main passenger railway operator in the Netherlands Our results show the three-phase heuristic finds good solutions for most instances and outperforms a state-of-the-art commercial solver.
Original languageEnglish
Article number106186
Number of pages12
JournalComputers & Operations Research
Volume154
DOIs
Publication statusPublished - Jun 2023

Keywords

  • Column generation
  • Crew planning
  • Fairness
  • Variable-depth neighborhood search

Fingerprint

Dive into the research topics of 'A three-phase heuristic for the fairness-oriented crew rostering Problem'. Together they form a unique fingerprint.

Cite this