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 Mercier, A. Search for Related Content

A Theoretical Comparison of Feasibility Cuts for the Integrated Aircraft-Routing and Crew-Pairing Problem

École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
anne.mercier{at}gerad.ca

The integrated aircraft-routing and crew-pairing problem consists in determining a minimum-cost set of aircraft routes and crew pairings such that each flight leg is covered by one aircraft and one crew, and some side constraints are satisfied. Linking constraints impose minimum connection times for crews that depend on aircraft connections. The main solution approach for this problem consists in solving a constrained crew-pairing problem iteratively, adding feasibility cuts until a solution is found where the connection set used by the crew pairings is feasible for the aircraft-routing problem. The feasibility cuts can be generated by a Benders decomposition approach in which aircraft routing is handled by the subproblem, or they can be selected from a predefined family. We perform a theoretical comparison of the different types of feasibility cuts. We also propose a simple procedure to strengthen these cuts. Computational experiments performed on test instances provided by two major airlines are presented to support the theoretical results.

Key Words: aircraft routing; crew pairing; integrated planning; Benders decomposition; extreme rays; feasibility cuts
History: Received: March 2006; revised: November 2006; accepted: February 2007.