Pith. sign in

REVIEW 2 major objections 2 minor 28 references

Branch and Price for Railway Crew Scheduling: Benchmark Instances and Computational Study

T0 review · 2 major / 2 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A branch-and-price algorithm solves railway crew scheduling instances to average optimality gaps below 1 percent, driven by primal heuristics.

desk verdict New public benchmarks for railway crew scheduling plus evidence that primal heuristics close most gaps in their branch-and-price runs, though instance representativeness lacks quantitative backing. read the letter →

arxiv 2606.10081 v1 pith:KUNGZLQT submitted 2026-06-08 math.OC

Bart van Rossum This is my paper · ORCID
classification math.OC
keywords railwaycrewschedulingbranchandpricecolumngenerationbenchmarkinstancesprimalheuristicsoptimalitygapsreducedcostfixing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper presents a branch-and-price algorithm for assigning tasks to crew duties at minimum cost and tests it on a new set of 75 benchmark instances that range from 450 to 3,016 tasks. These instances are generated to reproduce the full railway planning pipeline and are validated against data from Netherlands Railways before being released publicly with known solutions. Computational experiments show that the method routinely reaches gaps well below 1 percent across all sizes, with the largest contribution coming from column-generation-based primal heuristics; branching rules and reduced-cost fixing close little additional gap. The results therefore reinforce the practical value of heuristic column generation while identifying the dual bound as the main remaining obstacle to exact solutions.

What carries the argument

Branch-and-price algorithm that generates duties via column generation, augmented by primal heuristics, on a library of 75 publicly released benchmark instances that mimic full railway planning.

What would settle it

Running the same algorithm on proprietary instances from an actual operator and obtaining average gaps substantially larger than 1 percent would falsify the performance claim.

Watch

Extended reading notes

Core claim

The branch-and-price procedure, built around column generation for feasible duties, produces average optimality gaps well below 1 percent on all 75 instances. Primal heuristics account for most of the progress toward optimality, whereas branching and reduced-cost fixing contribute little to closing the remaining gap. The instances themselves are constructed by simulating the entire planning process and are made available with a solution checker so that future methods can be compared directly against the reported bounds.

Load-bearing premise

The 75 generated instances accurately represent the structure and difficulty of real railway crew scheduling problems.

Editorial extensions

If this is right

  • Column-generation heuristics are sufficient to produce near-optimal crew schedules for problems of this scale.
  • Exact branch-and-price methods will require stronger dual bounds before they can routinely close the final gap.
  • The released instance library and checker provide a standard testbed for comparing future crew-scheduling algorithms.
  • Operators can adopt similar heuristic column-generation procedures for day-to-day planning with high confidence in solution quality.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Similar benchmark-generation techniques could be applied to other transportation crew problems such as bus or airline scheduling.
  • The limited contribution of branching suggests that pure heuristic column generation may be the method of choice for operational use.
  • Public release of both instances and best-known solutions lowers the barrier for testing new dual-bound improvements.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper presents a branch-and-price algorithm for railway crew scheduling and introduces a publicly available library of 75 benchmark instances (450–3,016 tasks) generated by mimicking the full planning process and validated against Netherlands Railways data. It reports a computational study of algorithmic components (branching rules, primal heuristics, reduced-cost fixing) on these instances, claiming average optimality gaps well below 1% driven primarily by the primal heuristics, with branching and reduced-cost fixing contributing little, and concludes that improving the dual bound remains the main challenge for exact methods.

Significance. If the instances are representative of real railway crew scheduling difficulty, the work supplies a much-needed public benchmark set with best-known solutions and a solution checker, together with empirical evidence that column-generation primal heuristics are effective while dual-bound improvement is the bottleneck. These contributions would be useful for the operations research community working on crew scheduling and column generation.

major comments (2)
  1. [Instance generation section] Instance generation section: The statement that the 75 instances are 'validated against data from Netherlands Railways' is presented without quantitative metrics (e.g., comparisons of duty-network density, task-clustering statistics, or dual-bound tightness distributions between generated and real instances). Because the headline performance claims (gaps <1 %, attribution to primal heuristics, and the conclusion that dual bounds are the main challenge) rest on the assumption that the synthetic instances exhibit the same structure and hardness as real NS problems, the absence of such statistics is load-bearing.
  2. [Computational results section] Computational results section (tables reporting gaps and component contributions): The attribution that 'branching and reduced cost fixing contribute little' is based on aggregate averages; without per-instance or per-size-class breakdowns showing the marginal effect of each component (or ablation runs), it is difficult to confirm that the observed gaps are not simply an artifact of the instance set being easier for the primal heuristics than for the dual-side techniques.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'well below 1%' should be replaced by the precise average gap value (or range) once the tables are finalized.
  2. The paper states that instances and a solution checker are publicly available; the repository URL and exact license should be given in the main text (not only in a footnote) to facilitate immediate use by readers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments and the recommendation for major revision. We address each major comment point by point below, providing clarifications and indicating where revisions will be made to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Instance generation section] Instance generation section: The statement that the 75 instances are 'validated against data from Netherlands Railways' is presented without quantitative metrics (e.g., comparisons of duty-network density, task-clustering statistics, or dual-bound tightness distributions between generated and real instances). Because the headline performance claims (gaps <1 %, attribution to primal heuristics, and the conclusion that dual bounds are the main challenge) rest on the assumption that the synthetic instances exhibit the same structure and hardness as real NS problems, the absence of such statistics is load-bearing.

    Authors: We agree that providing quantitative validation metrics would better support the representativeness of the instances. In the revised version, we will expand the instance generation section to include comparisons of key structural statistics, such as duty-network density and task-clustering measures, between the generated instances and real data from Netherlands Railways. This will address the concern regarding the assumption of similar structure and hardness. revision: yes

  2. Referee: [Computational results section] Computational results section (tables reporting gaps and component contributions): The attribution that 'branching and reduced cost fixing contribute little' is based on aggregate averages; without per-instance or per-size-class breakdowns showing the marginal effect of each component (or ablation runs), it is difficult to confirm that the observed gaps are not simply an artifact of the instance set being easier for the primal heuristics than for the dual-side techniques.

    Authors: We acknowledge that aggregate averages alone may not fully demonstrate the marginal contributions. In the revision, we will include per-size-class breakdowns of the results, showing the impact of each algorithmic component (branching, primal heuristics, reduced-cost fixing) on the optimality gaps. This will provide clearer evidence that the gaps are indeed driven primarily by the primal heuristics across different instance sizes. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper is a computational study introducing 75 benchmark instances generated by mimicking the railway planning process and validated against NS data, then reporting empirical performance of a branch-and-price algorithm (average gaps <1% driven by primal heuristics). No derivation chain, equations, or predictions exist that reduce to self-definition, fitted inputs renamed as predictions, or self-citation loops. The main claims are direct outputs of running the solver on the instances; representativeness is an external assumption, not a circular reduction. No load-bearing self-citations or ansatzes are invoked for the results.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The central claims rest on the assumption that the generated instances faithfully capture real problem structure and that the implemented branch-and-price components behave as described; no free parameters, new entities, or non-standard axioms are introduced.

assumptions (1)
  • standard math Standard integer-programming and column-generation theory applies to the set-partitioning formulation of crew scheduling.
    Branch-and-price is presented as an established exact method whose correctness follows from prior theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Branch and Price for Railway Crew Scheduling: Benchmark Instances and Computational Study." pith.science (2026). https://pith.science/paper/KUNGZLQT

@misc{pith2026260610081,
  author       = {Pith},
  title        = {Pith review of: Branch and Price for Railway Crew Scheduling: Benchmark Instances and Computational Study},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KUNGZLQT}},
  note         = {Machine review of arXiv:2606.10081}
}
read the original 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 present a state-of-the-art branch-and-price algorithm and conduct a systematic computational study of its components, including branching rules, primal heuristics, and reduced cost fixing techniques. To this end, we introduce a novel library of 75 benchmark instances, ranging in size from 450 to 3,016 tasks. The instances are generated by mimicking the full 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 well 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. 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.

Figures

Figures reproduced from arXiv: 2606.10081 by the authors.

Figure 1
Figure 1. illustrates the generation pipeline. Infrastructure network Passenger demand Line plan Timetable Rolling stock schedule Tasks & connections [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Synthetic infrastructure networks. Small stations are shown as grey circles, large stations as white circles, and the crew base as a white square. Instances are named sS tT, where S denotes the number of large stations and T the number of tasks. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Validation of synthetic instances against NS instances. Every marker corre￾sponds to a single instance. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references

  1. [1]

    INFORMS Journal on Computing , volume=

    Primal heuristics for branch and price: The assets of diving methods , author=. INFORMS Journal on Computing , volume=. 2019 , publisher=

    2019

  2. [2]

    Operations Research Letters , volume=

    Branching rules revisited , author=. Operations Research Letters , volume=. 2005 , publisher=

    2005

  3. [3]

    INFORMS Journal on Computing , volume=

    Automation and combination of linear-programming based stabilization techniques in column generation , author=. INFORMS Journal on Computing , volume=. 2018 , publisher=

    2018

  4. [4]

    Optimizing railway crew scheduling at

    J. Optimizing railway crew scheduling at. Interfaces , volume=. 2011 , publisher=

    2011

  5. [5]

    Annual Report 2025 , year =

    2025

  6. [6]

    Statistica Neerlandica , volume=

    Operations research in passenger railway transportation , author=. Statistica Neerlandica , volume=. 2005 , publisher=

    2005

  7. [7]

    European Journal of Operational Research , volume=

    New benchmark instances for the capacitated vehicle routing problem , author=. European Journal of Operational Research , volume=. 2017 , publisher=

    2017

  8. [8]

    Management Science , volume=

    A polyhedral approach to simplified crew scheduling and vehicle scheduling problems , author=. Management Science , volume=. 2001 , publisher=

    2001

Show all 28 references
  1. [9]

    Reinventing crew scheduling at

    Abbink, Erwin and Fischetti, Matteo and Kroon, Leo and Timmer, Gerrit and Vromans, Michiel , journal=. Reinventing crew scheduling at. 2005 , publisher=

    2005

  2. [10]

    Mathematical Programming , volume=

    Algorithms for railway crew management , author=. Mathematical Programming , volume=. 1997 , publisher=

    1997

  3. [11]

    European Journal of Operational Research , volume=

    An efficient column generation approach for practical railway crew scheduling with attendance rates , author=. European Journal of Operational Research , volume=. 2021 , publisher=

    2021

  4. [12]

    OR Spectrum , volume=

    Line planning in public transportation: models and methods , author=. OR Spectrum , volume=. 2012 , publisher=

    2012

  5. [13]

    2018 , publisher=

    Handbook of optimization in the railway industry , author=. 2018 , publisher=

    2018

  6. [14]

    The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables --- and Beyond

    Liebchen, Christian and M \"o hring, Rolf H. The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables --- and Beyond. Algorithmic Methods for Railway Optimization. 2007

    2007

  7. [15]

    Operations Research , volume=

    Solving large-scale zero-one linear programming problems , author=. Operations Research , volume=. 1983 , publisher=

    1983

  8. [16]

    Transportation Science , volume=

    Exact branch-price-and-cut algorithms for vehicle routing , author=. Transportation Science , volume=. 2019 , publisher=

    2019

  9. [17]

    Omega , volume=

    A column generation approach for the integrated crew re-planning problem , author=. Omega , volume=. 2022 , publisher=

    2022

  10. [18]

    European Journal of Operational Research , volume=

    A column generation approach for the rail crew re-scheduling problem , author=. European Journal of Operational Research , volume=. 2007 , publisher=

    2007

  11. [19]

    Discrete Optimization , volume=

    Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints , author=. Discrete Optimization , volume=. 2006 , publisher=

    2006

  12. [20]

    European Journal of Operational Research , volume=

    Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster , author=. European Journal of Operational Research , volume=. 2017 , publisher=

    2017

  13. [21]

    2024 , publisher=

    Branch-and-price , author=. 2024 , publisher=

    2024

  14. [22]

    Operations Research at

    Huisman, Dennis and Mar. Operations Research at. Operations Research Forum , volume=

  15. [23]

    Computers & Industrial Engineering , volume=

    Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates , author=. Computers & Industrial Engineering , volume=. 2019 , publisher=

    2019

  16. [24]

    Annals of Operations Research , volume=

    An exact algorithm for the simplified multiple depot crew scheduling problem , author=. Annals of Operations Research , volume=. 2004 , publisher=

    2004

  17. [25]

    Public Transport , volume=

    Solving large scale crew scheduling problems in practice , author=. Public Transport , volume=. 2011 , publisher=

    2011

  18. [26]

    A fast exact pricing algorithm for the railway crew scheduling problem , journal=

    van Rossum, B T C , volume=. A fast exact pricing algorithm for the railway crew scheduling problem , journal=. 2022 , publisher=

    2022

  19. [27]

    European Journal of Operational Research , volume=

    Railway crew scheduling: Models, methods and applications , author=. European Journal of Operational Research , volume=

  20. [28]

    Column Generation and

    Dollevoet, Twan and Huisman, Dennis , booktitle=. Column Generation and. 2024 , publisher=

    2024

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.