Branch and Price for Railway Crew Scheduling: Benchmark Instances and Computational Study
math.OC
Submitted: 2026-06-08
Updated: 2026-10-28
Code: https://github.com/BartvanRossum/rcsp-benchmark
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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 papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise