Article ID: | iaor20082682 |
Country: | United States |
Volume: | 55 |
Issue: | 3 |
Start Page Number: | 439 |
End Page Number: | 456 |
Publication Date: | May 2007 |
Journal: | Operations Research |
Authors: | Klabjan Diego, Sandhu Rivi |
Keywords: | timetabling, vehicle routing & scheduling |
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.