Paper Info
Title
Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods
Abstract
The integrated crew scheduling (ICS) problem consists of determining, for a set of available crew members, least-cost schedules that cover all flights and respect various safety and collective agreement rules. A schedule is a sequence of pairings interspersed by rest periods that may contain days off. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. Given its high complexity, the ICS problem has been traditionally tackled using a sequential two-stage approach, where a crew pairing problem is solved in the first stage and a crew assignment problem in the second stage. Recently, Saddoune et al. (2010b) developed a model and a column generation/dynamic constraint aggregation method for solving the ICS problem in one stage. Their computational results showed that the integrated approach can yield significant savings in total cost and number of schedules, but requires much higher computational times than the sequential approach. In this paper, we enhance this method to obtain lower computational times. In fact, we develop a bi-dynamic constraint aggregation method that exploits a neighborhood structure when generating columns (schedules) in the column generation method. On a set of seven instances derived from real-world flight schedules, this method allows to reduce the computational times by an average factor of 2.3, while improving the quality of the computed solutions.
Year
DOI
Venue
2011
10.1016/j.ejor.2011.02.009
European Journal of Operational Research
Keywords
DocType
Volume
OR in airlines,Crew scheduling,Integrated crew pairing and crew assignment,Column generation,Bi-dynamic constraint aggregation
Journal
212
Issue
ISSN
Citations 
3
0377-2217
13
PageRank 
References 
Authors
0.53
12
4
Name
Order
Citations
PageRank
Mohammed Saddoune1493.74
Guy Desaulniers287462.90
Issmail Elhallaoui31337.89
François Soumis482197.64