Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time

Tsubasa Doi, Tatsushi Nishi, Stefan Voß

Research output: Contribution to journalArticlepeer-review

39 Citations (Scopus)


We propose a two-level decomposition-based matheuristic algorithm to solve a practical airline crew rostering problem with fair working time. The goal is to find an optimal assignment of pairings to individual crew members that satisfies hard constraints reflecting, for instance, international flights, rest days and regulatory requirements. The objective is to achieve a fair working time of crew members. We propose a two-level decomposition algorithm applying partial optimization under special intensification conditions (POPMUSIC). The method decomposes the original problem into a master problem and a subproblem. The master problem determines an assignment of pairings and rest days. The subproblem checks the feasibility of the original problem when the solution of the master problem is fixed. These problems are iteratively solved by embedding cuts into the master problem. A new method for solving the master problem by a generalized set partitioning reformulation is proposed. The effectiveness of the proposed method for real-world data is shown via computational experiments.

Original languageEnglish
Pages (from-to)428-438
Number of pages11
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - Jun 1 2018
Externally publishedYes


  • Airline scheduling
  • Crew rostering
  • Cut generation
  • 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-based matheuristic for airline crew rostering problems with fair working time'. Together they form a unique fingerprint.

Cite this