Two-level decomposition algorithm for crew rostering problems with fair working condition

Tatsushi Nishi, Taichi Sugiyama, Masahiro Inuiguchi

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)


A typical railway crew scheduling problem consists of two phases: a crew pairing problem to determine a set of crew duties and a crew rostering problem. The crew rostering problem aims to find a set of rosters that forms workforce assignment of crew duties and rest periods satisfying several working regulations. In this paper, we present a two-level decomposition approach to solve railway crew rostering problem with the objective of fair working condition. To reduce computational efforts, the original problem is decomposed into the upper-level master problem and the lower-level subproblem. The subproblem can be further decomposed into several subproblems for each roster. These problems are iteratively solved by incorporating cuts into the master problem. We show that the relaxed problem of the master problem can be formulated as a uniform parallel machine scheduling problem to minimize makespan, which is NP-hard. An efficient branch-and-bound algorithm is applied to solve the master problem. Effective valid cuts are developed to reduce feasible search space to tighten the duality gap. Using data provided by the railway company, we demonstrate the effectiveness of the proposed method compared with that of constraint programming techniques for large-scale problems through computational experiments.

Original languageEnglish
Pages (from-to)465-473
Number of pages9
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - Sept 1 2014
Externally publishedYes


  • Crew rostering
  • Cut generation
  • Railway scheduling
  • Two-level decomposition algorithm

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Two-level decomposition algorithm for crew rostering problems with fair working condition'. Together they form a unique fingerprint.

Cite this