Florez

A Mathematical Programming Approach to Airline Crew Pairing Optimization
Diana C. Flórez, Jose L. Walteros, Miguel A. Vargas, Andrés L. Medaglia, Nubia Velasco Centro para la Optimización y Probabilidad Aplicada (COPA) Departamento de Ingeniería Industrial Universidad de los Andes

Abstract. In the ever increasing competitive environment of the airline industry, efficient personnel’s planning isamong the most challenging tasks and solely responsible for the largest impact on an airline’s cost structure. The problem is theoretically appealing because it is computationally difficult due to the huge number of possibilities, and the amount of rules that determine crew planning. This work proposes a methodology to determine the most efficient and least costly way to serve the flights in anairline schedule during a weekly planning horizon considering layovers and deadheads. The strategy is composed of three optimization models: a binary programming model, a model based on the set partitioning problem, and a third model based on the set covering problem, the two latter solved via column generation. Computational results for the three models are presented using test instances built froma mid-sized Colombian airline. Keywords: Airline Crew Pairing, Column Generation, Set Covering Problem, Set Partitioning Problem

1. Introduction
Personnel planning and scheduling is one of the most challenging tasks faced by an airline. Its importance derives from the economical impact that an efficient planning has on business profitability. On the other hand, its difficulty arises from itscombinatorial structure, closely tied to the number of flights in the schedule and the fleet size, among other factors. The set of activities geared towards planning and scheduling staff is known in the literature as the Airline Crew Scheduling Problem (ACSP). ACSP is one of the practical combinatorial problems that is well known as a hard problem from a computational point of view (Guo et al.,2006). The objective is to define crew tasks such that all flights from a flight schedule are served in the most efficient way considering rules that determine their feasibility (e.g., maximum flying time) and crew preferences (e.g., maximum number of consecutive work days). In the last years, the problem has become even more complex due to the rapid airline industry growth, increase in passengerdemand (especially business trips), and the ever increasing competition in the low-fare market. This has led researchers and software companies to invest a great amount of resources in developing highly technical decision support tools based on optimization (Guo et al., 2006). Airline operation planning can be divided in four hierarchical phases, where the products of one phase are input for the next(Barnhart, 2003). These phases are: Schedule Planning: Based on the passenger demand forecasts, the output of this phase is what is known as the flight schedule. This flight offer is determined by the flight’s time, day, and frequency. Fleet Assignment: This phase matches the flights in the schedule with a specific type of aircraft, considering plane capacity and flight characteristics (i.e.,domestic, international, overseas).

Aircraft Routing: This phase deals with scheduling aircraft maintenance operations so that the fleet meets the best working conditions and strict regulations and is timely available to meet flight demand. Crew Scheduling: The flight schedule and assignment are used in this phase to determine which tasks are allocated to each crew member such that all flights areserved meeting labor, operational, and government regulations. Within the crew scheduling phase two sequential and interconnected subproblems are the Airline Crew Pairing Problem (ACPP) and the Airline Crew Rostering Problem (ACRP). The ACPP determines the minimum number of (anonymous) crews required to serve all flights in a planning horizon, considering labor, operational, and government...