An Optimization-Based Decision Support Framework for Robust Airline Crew Pairing Process

Introduction

In order to be competitive in the market, airlines need to solve a large number of decision problems, both in airline schedule planning and operations (schedule execution) stages. Airline schedule planning stage for a scheduled passenger airline is too large and complex to be dealt with as a whole. It is usually divided into four sequential sub stages: flight schedule design, fleet assignment, aircraft routing, and crew scheduling. Due to the fact that crew costs are second only to fuel costs among all airline direct operating costs, crew scheduling constitutes a crucial part of the whole planning process. Above and beyond all other considerations, crew costs are manageable by airlines compared to fuel costs. Hence, it implies potential cost savings by establishing efficient crew schedule systems, and even small reductions in crew cost can lead to large savings. Moreover, crew schedules’ performance contributes to the flight safety, service quality and as a result airline's goodwill as well. Therefore, decision support tools associated with crew scheduling are indispensably and highly utilized by airlines.

Airline crew scheduling mainly deals with finding the minimum cost set of legal crew schedules that cover all the flight legs in a given flight schedule while considering a large number of restrictive rules, which is done at the tactical planning level. This problem is traditionally divided into two stages: crew pairing (tour-of-duty planning) and crew rostering, and solved with a sequential approach. Airline crew pairing, denoted as ACP, mainly deals with finding the minimum cost set of legal crew pairings that cover all the flight legs in a given flight schedule. On the other hand, airline crew rostering focuses on assigning individual crew members to the fixed pairings. The leave times, training periods etc. are considered in order to construct work schedules usually for a month. Most of the cost improvements can be achieved by optimizing pairings. For this reason ACP is generally accepted as the most important stage of crew scheduling, (Barnhart et al., 2003). In this chapter, only the crew pairing problem, which is the frequently encountered real-life decision problem, is taken into account.

The prominent traditional approach to overcome the combinatorial nature of the ACP problem is to formulate it as a set partitioning or set covering problem and to deal with all nonlinearities by using a network-based pairing generation scheme. The resulting integer program is inherently difficult to solve, because exact illustration of the feasibility set is either very time consuming or even impossible. In order to avoid this difficulty, first Linear Programming (LP) relaxation of the problem is solved and then a Branch-and-Bound (B & B) scheme is applied to obtain an integer solution.

Nevertheless, the solution obtained from traditional ACP problem assumes that the schedule will be carried out as planned with complete information and in a deterministic environment. However, in practice, airline operations are prone to suffer disruptions caused by inclement weather, airport congestion, equipment failure, crew sickness, late passengers, etc. In such cases optimal crew pairings easily become sub-optimal. Traditional approaches have proved to be not capable to address such disruptions adequately. Furthermore, tight schedules created by deterministic approaches lead to propagation of the delays across the network, because globally optimized deterministic solutions have short buffer times between flights and also smooth recovery is not taken into account during schedule planning (Soykan & Erol, 2014).

In operations stage, the effect of an individual delay may be negligible, but the ripple effect (also referred as snowball effect or knock-on effect), which is the propagation of delays over the whole network, may lead significant negative complications. Actually, in case of disruptions the quasi-optimal schedules generated in the planning stage become far from optimal in practice. Usually external factors, such as inclement weather or airport congestion, are held responsible for delays. However, certain delays especially propagated delays, are predictable and avoidable with incorporating robustness to the schedules at the planning stage.