An Approximate Model and Solution Approach for the Long-Haul Crew Pairing Problem

Cynthia Barnhart and Rajesh G. Shenoi
Additional contact information
Cynthia Barnhart: Massachusetts Institute of Technology, Cambridge
Rajesh G. Shenoi: McKinsey Company, Houston

Transportation Science, 1998, vol. 32, issue 3, 221-231

Abstract: The crew pairing problem requires the coverage of a set of long-haul flights by a minimum cost set of crew pairings. A crew pairing is a sequence of flights flown by one crew, starting and ending at the same location, and satisfying a variety of work regulations and collective bargaining agreements. We present a new solution approach that solves first an approximate model of the problem and then uses its solution as an advanced start solution for conventional approaches. Using data provided by a long-haul airline, we demonstrate that our new approach can be used with a deadhead selector to identify deadheads quickly that might improve significantly the quality of the crew pairing solution. Deadheads, flights to which crews are assigned as passengers, reposition crews for better utilization. We speed up the solution process by using our advanced start solution and by quickly providing good lower bounds on the optimal solution values. Our experiments show that the lower bounds are on average within 0.85% of the optimal solution value. Further, we show that compared to existing methods, we reduce solution costs and run times by an average of 20% and over 80%, respectively.

Date: 1998
References: View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.32.3.221 (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:ortrsc:v:32:y:1998:i:3:p:221-231

Access Statistics for this article

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