Paper Info
Title
Combining Benders’ Decomposition and Column Generation for Integrated Crew Pairing and Personalized Crew Assignment Problems
Abstract
AbstractThe 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.
Year
DOI
Venue
2019
10.1287/trsc.2019.0892
Periodicals
Keywords
Field
DocType
airline crew scheduling,Benders' decomposition,column generation
Mathematical optimization,Column generation,Crew,Crew scheduling,Pairing,Assignment problem,Mathematics,Benders' decomposition
Journal
Volume
Issue
ISSN
53
5
1526-5447
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Vahid Zeighami100.34
François Soumis282197.64