A Partial Duty Formulation for Crew Scheduling

Abstract

We consider a crew scheduling problem with a break, working time, and duty length constraint. It is common to solve crew scheduling problems with a diving heuristic, using column generation to solve the LP relaxation of a set partitioning formulation where variables correspond with duties. We prove that computing the LP bound of this formulation is weakly NP-hard, and propose an alternative formulation based on partial duties, whose LP bound can be computed in polynomial time. We prove the same complexity results for the corresponding pricing problems. However, the partial duty formulation has a weaker LP bound. To overcome this issue, we introduce compatibility cuts which completely recover the loss in LP bound. While separation can be done efficiently, we prove that the corresponding pricing problem after separation is weakly NP-hard. Therefore, we also introduce two relaxed versions of the compatibility cuts. We demonstrate computational benefits by providing numerical experiments with a diving heuristic based on the partial duty formulation, in a case study on the metro network of the Rotterdam area, the Netherlands.

Branch and Price for Railway Crew Scheduling: Benchmark Instances and Computational Study
Bart van Rossum
arXiv28 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Online Packet Scheduling with Deadlines and Learning
Gianmarco Genalti, Achraf Azize, Vianney Perchet
HAL30 May 2026PreprintLicence not statedGeneral mathematicsHAL
Optimal Uniform-like Scheduling of Maintenance
Yakov Genis, Igor Ushakov
Reliability: Theory & Applications1 Sep 2026Peer-reviewedCC BY-NCFull textGeneral mathematicsDOAJ
Dropout Universality: Scaling Laws and Optimal Scheduling at the Edge-of-Chaos
Lucas Fernandez Sarmiento
arXiv29 Sep 2026PreprintCC BY 4.0Full textStatistics Condensed matterarXiv
DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf
arXiv12 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{dollevoet2026partial,
  title = {{A Partial Duty Formulation for Crew Scheduling}},
  author = {Twan Dollevoet and Bart van Rossum and Remy Spliet},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.24867},
  eprint = {2610.24867},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.24867},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A Partial Duty Formulation for Crew Scheduling
AU  - Twan Dollevoet
AU  - Bart van Rossum
AU  - Remy Spliet
PY  - 2026
DA  - 2026/10/17
PB  - arXiv
DO  - 10.48550/arxiv.2610.24867
UR  - https://arxiv.org/abs/2610.24867
AB  - We consider a crew scheduling problem with a break, working time, and duty length constraint. It is common to solve crew scheduling problems with a diving heuristic, using column generation to solve the LP relaxation of a set partitioning formulation where variables correspond with duties. We prove that computing the LP bound of this formulation is weakly NP-hard, and propose an alternative formulation based on partial duties, whose LP bound can be computed in polynomial time. We prove the same complexity results for the corresponding pricing problems. However, the partial duty formulation has a weaker LP bound. To overcome this issue, we introduce compatibility cuts which completely recover the loss in LP bound. While separation can be done efficiently, we prove that the corresponding pricing problem after separation is weakly NP-hard. Therefore, we also introduce two relaxed versions of the compatibility cuts. We demonstrate computational benefits by providing numerical experiments with a diving heuristic based on the partial duty formulation, in a case study on the metro network of the Rotterdam area, the Netherlands.
ER  -

Abstract

Related

Cite