Airline Crew Scheduling: A New Formulation and Decomposition Algorithm

Pamela H. Vance, Cynthia Barnhart, Ellis L. Johnson and George L. Nemhauser
Additional contact information
Pamela H. Vance: Auburn University, Auburn, Alabama
Cynthia Barnhart: Massachusetts Institute of Technology, Cambridge, Massachusetts
Ellis L. Johnson: Georgia Institute of Technology, Atlanta, Georgia
George L. Nemhauser: Georgia Institute of Technology, Atlanta, Georgia

Operations Research, 1997, vol. 45, issue 2, 188-200

Abstract: Airline crew scheduling is concerned with finding a minimum cost assignment of flight crews to a given flight schedule while satisfying restrictions dictated by collective bargaining agreements and the Federal Aviation Administration. Traditionally, the problem has been modeled as a set partitioning problem. In this paper, we present a new model based on breaking the decision process into two stages. In the first stage we select a set of duty periods that cover the flights in the schedule. Then, in the second stage, we attempt to build pairings using those duty periods. We suggest a decomposition approach for solving the model and present computational results for test problems provided by a major carrier. Our formulation provides a tighter linear programming bound than that of the conventional set partitioning formulation but is more difficult to solve.

Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (49)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.2.188 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:2:p:188-200

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().