Deadhead selection for the long-haul crew pairing problem

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 favrouably 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.