This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Sandhu, R. Articles by Klabjan, D. Search for Related Content

Integrated Airline Fleeting and Crew-Pairing Decisions

United Airlines, Elk Grove Village, Illinois 60007
Department of Mechanical and Industrial Engineering, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801
rivi.sandhu{at}united.com
klabjan{at}uiuc.edu

The tactical planning process of an airline is typically decomposed into several stages among which fleeting, aircraft routing, and crew pairing form the core. In such a decomposed and sequential approach, the output of fleeting forms the input to aircraft routing and crew pairing. In turn, the output to aircraft routing is part of the input to crew pairing. Due to this decomposition, the resulting solution is often suboptimal. We propose a model that completely integrates the fleeting and crew-pairing stages and guarantees feasibility of plane-count feasible aircraft routings, but neglects aircraft maintenance constraints. We design two solution methodologies to solve the model. One is based on a combination of Lagrangian relaxation and column generation, while the other one is a Benders decomposition approach. We conduct computational experiments for a variety of instances obtained from a major carrier.

Subject classifications: crew scheduling; capacity planning; large-scale optimization.
History: Received June 2004; revision received November 2005; accepted February 2006.