Applications of Combinatorial Optimization, 2nd Edition

Chapter 1

Airline Crew Pairing Optimization

1.1. Introduction

In the airline industry, optimizing and automating the building of crew pairings is a major financial and organizational issue. The problem consists of covering all the company’s flights, programmed in a given time window, with teams made up of cockpit personnel (pilots, copilots) and of cabin personnel (stewardesses, stewards) at a minimum cost. With a frequency of several days (in the order of a week), each crew leaves from the base to which it is assigned, carries out a certain number of flights, and comes back to the base. This sequence of flights with a return to the base is called a rotation, or pairing. Drawing up the pairings of an airline company is highly constrained by international, national and internal work regulations, and by the limited availability of resources. These constraints make the problem particularly hard to solve. Besides the gains in terms of organization, security and calculation time, the use of optimization programs and models for this problem allows big companies to make substantial financial gains. It is not unusual for a reduction of 1% in the total cost of the rosters to result in savings of several tens of millions of dollars for big companies [DES 97], which is one reason for the abundant fundamental and applied research on this subject. The general crew pairing problem with resource constraints problem (CPP-RC) can be formulated as a minimum cost multicommodity flow problem with ...