Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation

Mohammed Saddoune (), Guy Desaulniers (), Issmail Elhallaoui () and François Soumis ()
Additional contact information
Mohammed Saddoune: École Polytechnique de Montréal and GERAD, Department of Mathematics and Industrial Engineering, C.P. 6079, Succ. Centre-Ville, Montréal, Québec H3C 3A7, Canada
Guy Desaulniers: École Polytechnique de Montréal and GERAD, Department of Mathematics and Industrial Engineering, C.P. 6079, Succ. Centre-Ville, Montréal, Québec H3C 3A7, Canada
Issmail Elhallaoui: École Polytechnique de Montréal and GERAD, Department of Mathematics and Industrial Engineering, C.P. 6079, Succ. Centre-Ville, Montréal, Québec H3C 3A7, Canada
François Soumis: École Polytechnique de Montréal and GERAD, Department of Mathematics and Industrial Engineering, C.P. 6079, Succ. Centre-Ville, Montréal, Québec H3C 3A7, Canada

Transportation Science, 2012, vol. 46, issue 1, 39-55

Abstract: Traditionally, the airline crew scheduling problem has been decomposed into a crew pairing problem and a crew assignment problem, both of which are solved sequentially. The first consists of generating a set of least-cost crew pairings (sequences of flights starting and ending at the same crew base) that cover all flights. The second aims at finding monthly schedules (sequences of pairings) for crew members that cover all pairings previously built. Pairing and schedule construction must respect all safety and collective agreement rules. In this paper, we focus on the pilot crew scheduling problem in a bidline context where anonymous schedules must be built for pilots and high fixed costs are considered to minimize the number of scheduled pilots. We propose a model that completely integrates the crew pairing and crew assignment problems, and we develop a combined column generation/dynamic constraint aggregation method for solving them. Computational results on real-life data show that integrating crew pairing and crew assignment can yield significant savings---on average, 3.37% on the total cost and 5.54% on the number of schedules for the 7 tested instances. The integrated approach, however, requires much higher computational times than the sequential approach.

Keywords: airline crew scheduling; integrated crew pairing and crew assignment; column generation; dynamic constraint aggregation (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1110.0379 (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:ortrsc:v:46:y:2012:i:1:p:39-55

Access Statistics for this article

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