Airlines’ Crew Pairing Optimization: a Brief Review

Airlines’ Crew Pairing Optimization: A Brief Review

Xugang Ye Applied Mathematics and Statistics, the Johns Hopkins University Abstract In most airlines, crew costs are the second largest direct operation cost next to the fuel costs. But unlike the fuel costs, a considerable portion of the crew costs can be saved through optimized utilization of the internal resources of an airline company. And the saving is largely realized through solving the crew pairing problem. This paper aims to give a brief review of the fundamental crew pairing problem: its concepts, its models, and its algorithms. Keywords: Airlines; Crew pairing; Optimization

1. Introduction

As an important issue of airlines’ operational planning, crew pairing immediately follows fleet assignment phase and right precedes crew rostering phase. A pairing is a sequence of connectable flight legs, within the same fleet, that starts from and ends at the same crew base, where the crew actually lives. A pairing is sometimes called an itinerary for the crew assigned to this journey. It typically spans from one to five days. To create tasks for crew members, the planners of an airline must generate a set of pairings to cover as many flight legs in a planning horizon as possible, with a cost as small as possible. For a large airline, the number of the flight legs in a planning horizon can be very many, hence the planning of pairings can be highly computationally intensive. Although it is possible to model the crew pairing problem as a binary linear programming (BLP) problem if we consider all the subsets of the set of the flight legs in a planning horizon, the number of the decision variables could easily exceed the capability of the current computing technology. Therefore, people rely on more practical methods. The most popular method seems to solve the problem sequentially with two phases. The first phase is to generate as many legal pairings as possible. The second phase is to select a best subset in the...