Combining Benders’ Decomposition and Column Generation for Integrated Crew Pairing and Personalized Crew Assignment Problems

Vahid Zeighami () and François Soumis ()
Additional contact information
Vahid Zeighami: Department of Mathematics and Industrial Engineering, Polytechnique Montréal and GERAD, Montreal, Quebec H3C 3A7, Canada
François Soumis: Department of Mathematics and Industrial Engineering, Polytechnique Montréal and GERAD, Montreal, Quebec H3C 3A7, Canada

Transportation Science, 2019, vol. 53, issue 5, 1479-1499

Abstract: The airline crew scheduling problem, because of its size and complexity, is usually solved in two phases: the crew pairing problem and the crew assignment problem. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. The crew pairing problem consists of determining a minimum-cost set of feasible pairings such that each flight is covered exactly once. In the crew assignment problem, the goal is to construct monthly schedules from these pairings for a given set of pilots and copilots independently, while respecting all the safety and collective agreement rules. However, this sequential approach may lead to significantly suboptimal solutions because it does not take into account the crew assignment constraints and objective during the building of the pairings. In this paper, first, we propose an extension of the crew pairing problem that incorporates pilot and copilot vacation requests at the crew pairing stage. Second, we introduce a model that completely integrates the crew pairing and crew assignment problems simultaneously for pilots and copilots. To solve this integrated problem, we develop a method that combines Benders’ decomposition and column generation. We conduct computational experiments with real-world data from a major U.S. carrier.

Keywords: airline crew scheduling; Benders’ decomposition; column generation (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0892 (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:53:y:2019:i:5:p:1479-1499

Access Statistics for this article

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