Traditionally, the airline crew scheduling problem has been decomposed into a crew pairing and a crew assignment problem that are solved sequentially. The first problem 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 problem aims at finding monthly schedules (sequences of pairings) for the 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 the crew assignment problem, and develop a combined column generation/dynamic constraint aggregation method for solving it. 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 seven tested instances. The integrated approach requires, however, much higher computational times than the sequential approach.
Published February 2010 , 22 pages