A Column Generation Approach for Large-Scale Aircrew Rostering Problems

Michel Gamache, François Soumis, Gérald Marquis and Jacques Desrosiers
Additional contact information
Michel Gamache: GERAD and École Polytechnique, Montréal, Canada
François Soumis: GERAD and École Polytechnique, Montréal, Canada
Gérald Marquis: GERAD and École Polytechnique, Montréal, Canada
Jacques Desrosiers: GERAD and École des Hautes Études Commerciales, Montréal, Canada

Operations Research, 1999, vol. 47, issue 2, 247-263

Abstract: This article describes a method for solving the crew rostering problem in air transportation. This problem consists of constructing personalized schedules that assign pairings, days off, and other activities to airline crew members. A generalized set partitioning model and a method using column generation have been used. This method has been adapted in a number of ways to take advantage of the nature of the problem and to accelerate solution. Numerical tests on problems from Air France have demonstrated that this method is capable of solving very large scale problems with thousands of constraints and hundreds of subproblems. The tests have also shown that these adaptations are capable of reducing solution time by a factor of about a thousand. Finally, results from this method are compared with those obtained with the method currently used at Air France.

Keywords: programming; integer; large-scale systems; column generation; transportation; airline application; rostering; scheduling; personnel; airline crew members (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (61)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.2.247 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:2:p:247-263

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().