A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem. (June 2023)

• Record Type: Journal Article
• Authors: Breugem, Thomas; Schlechte, Thomas; Schulz, Christof; Borndörfer, Ralf
• Is Part Of: Computers & operations research. Volume 154(2023)
• Publication Date: 2023-06
• Subjects: Crew planning -- Fairness -- Column generation -- Variable-depth neighborhood search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2023.106186
• Languages: English
• ISSNs: 0305-0548

Abstract

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. Highlights: We present a three-phase heuristic for the Fairness-Oriented Crew Rostering Problem (FCRP). The heuristic combines column generation with variable depth neighborhood search. We apply our methodology to practical instances from Netherlands Railways (NS). We show the heuristic finds good solutions and outperforms a commercial solver.