Branch and Price for Railway Crew Scheduling: Benchmark Instances and Computational Study
Abstract
Railway crew scheduling consists of assigning a set of tasks to crew members in the form of feasible duties so as to minimise costs, and is one of the key planning problems faced by railway operators. While column generation is the dominant solution method, literature on exact branch-and-price approaches is scarce. Moreover, few publicly available benchmark instances exist. We conduct a systematic computational study of branch and price for railway crew scheduling, evaluating the contribution of branching rules, primal heuristics, and reduced cost fixing. To this end, we introduce a novel library of 100 benchmark instances, ranging in size from 90 to 3,016 tasks, each provided in a single-depot and a multi-depot variant. The instances are generated by mimicking the railway planning process, validated against data from Netherlands Railways, and publicly available with best known solutions and a solution checker. We report average optimality gaps below 1% across all instance sizes, driven primarily by the strong performance of primal heuristics, whereas branching and reduced cost fixing contribute little to closing the gap. Branch and price also outperforms a multi-commodity flow formulation, which fails to find a feasible solution on many of the smallest instances. Our findings provide support for the popularity of column generation-based primal heuristics, and show that improving the dual bound remains the main challenge for exact methods in railway crew scheduling.
Related
- Improved upper bounds for five IHTC-2024 benchmark instances via exact reoptimization of the nurse-to-room layer
- Why the Kellogg Mesh Is Radial: A Mathematical Explanation of a Classical Computational Benchmark
- Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
- Some instances of modularity for residually reducible representations in the mixed case
- Hard Instances on Demand
BibTeX
@misc{rossum2026branch,
title = {{Branch and Price for Railway Crew Scheduling: Benchmark Instances and Computational Study}},
author = {Bart van Rossum},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.10081},
eprint = {2606.10081},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.10081},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Branch and Price for Railway Crew Scheduling: Benchmark Instances and Computational Study
AU - Bart van Rossum
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2606.10081
UR - https://arxiv.org/abs/2606.10081
AB - Railway crew scheduling consists of assigning a set of tasks to crew members in the form of feasible duties so as to minimise costs, and is one of the key planning problems faced by railway operators. While column generation is the dominant solution method, literature on exact branch-and-price approaches is scarce. Moreover, few publicly available benchmark instances exist. We conduct a systematic computational study of branch and price for railway crew scheduling, evaluating the contribution of branching rules, primal heuristics, and reduced cost fixing. To this end, we introduce a novel library of 100 benchmark instances, ranging in size from 90 to 3,016 tasks, each provided in a single-depot and a multi-depot variant. The instances are generated by mimicking the railway planning process, validated against data from Netherlands Railways, and publicly available with best known solutions and a solution checker. We report average optimality gaps below 1% across all instance sizes, driven primarily by the strong performance of primal heuristics, whereas branching and reduced cost fixing contribute little to closing the gap. Branch and price also outperforms a multi-commodity flow formulation, which fails to find a feasible solution on many of the smallest instances. Our findings provide support for the popularity of column generation-based primal heuristics, and show that improving the dual bound remains the main challenge for exact methods in railway crew scheduling.
ER -