Airline Crew Augmentation: Decades of Improvements from Sabre

The objectives of the airline crew-planning process are to allocate crews to flights and create work schedules for crew members. Most airlines solve their crew-planning problem in two steps. The first step, crew pairing, is to generate optimized, anonymous pairings that cover given flight schedules. In the second step, the resulting pairings are assigned to crew members. The general pairing problem is complex because flights may require an augmented crew for safety reasons. A flight’s crew-augmentation requirement varies, depending on the characteristics of the pairings that cover it. Furthermore, airlines often impose rules to govern the coverage of a flight by different pairings. Common approaches to the problem either fix the crew-augmentation requirement a priori, or add restrictions on how the augmentation requirement is satisfied. Crew augmentation is often overlooked from an optimization perspective because of the complexities involved. The Sabre ® long-haul pairing optimizer explicitly models many types of crew-augmentation processes and simultaneously considers the relevant ranks of all members within the cockpit crew. It uses state-of-the-art large-scale optimization techniques, such as branch and price, to solve the problem. In this article, we introduce the long-haul pairing optimizer that Sabre developed in the mid-1990s, and share the evolution of the models and solution algorithms for the general crew-pairing problem with augmentation. We also compare our approach with four conventional approaches to show that we can effectively solve the general crew-augmentation problem and provide significant crew cost savings to airlines.