Deadhead Selection for the Long-Haul Crew Pairing Problem

Cynthia Barnhart, Levent Hatay and Ellis L. Johnson
Additional contact information
Cynthia Barnhart: Massachusetts Institute of Technology, Cambridge, Massachusetts
Levent Hatay: American Airlines Decision Technologies, Dallas/Fort Worth Airport, Texas
Ellis L. Johnson: Georgia Institute of Technology, Atlanta, Georgia

Operations Research, 1995, vol. 43, issue 3, 491-499

Abstract: The long-haul crew pairing problem involves the assignment of crews to scheduled flights such that overall costs are minimized and crew availability and work rule restrictions are satisfied. These problems are characterized by international flights that typically do not operate on a daily schedule, resulting in a sparsity of flights and extended periods of inactivity for crews at some stations. To eliminate these extended rest periods and reduce overall costs, it is advantageous in some cases to deadhead crews, that is, to assign crews to flights as passengers for repositioning and better utilization. In this paper, a heuristic methodology is developed to improve crew pairing solutions through the efficient selection and utilization of deadhead flights. The methodology uses the dual solutions determined in solving the linear programming relaxation of the crew pairing problem to build arrival and departure profiles at each station. These profiles provide a mechanism to price-out potential deadhead flights. Flights that price-out favorably may be used to build improved solutions to the crew pairing problem. The Deadhead Selection Procedure is tested using data provided by a long-haul airline and is shown to achieve significant improvement in crew costs by reducing the total number of deadhead hours flown and by reducing the total duration of rest periods.

Keywords: networks/graphs; multicommodity; programming; applications; large-scale systems; transportation; network models; personnel scheduling; airline (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.3.491 (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:43:y:1995:i:3:p:491-499

Access Statistics for this article

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