Flight Scheduling, Fleet Assignment, and Aircraft Routing Problems: History
Please note this is an old version of this entry, which may differ significantly from the current revision.

Airlines face the imperative of resource management to curtail costs, necessitating the solution of several optimization problems such as flight planning, fleet assignment, aircraft routing, and crew scheduling. These problems present some challenges. 

  • flight scheduling
  • fleet assignment
  • aircraft routing

1. Introduction

The airline industry is highly competitive, especially with the emergence of low-fare airlines. It is characterized by variable demand, high operating costs, heavy traffic, and strict regulations, all of which contribute to the tight competition in the market. Furthermore, an airline’s sole product is its aircraft seats, which are not sold until the flight takes off. Therefore, managing supply and demand fluctuations effectively is a significant challenge for airline companies. Accurate models and solution methodologies with narrow margins of error are necessary to address this issue [1].
Airline operation planning is a complex process of making decisions with many important decisions that directly affect a company’s profitability. The planning process is divided into sub-problems to manage these decisions [2]. The flight scheduling (FS) problem defines the frequency of flights to each destination and how the flights should be planned to meet this frequency. The fleet assignment (FA) problem assigns fleets to appropriate flights, while the aircraft routing (AR) problem creates flight route plans for each aircraft, considering that maintenance constraints. The crew scheduling (CS) problem involves determining the crew members for each flight [3].
Airline companies aim to expand their airline networks to provide passengers with a wider range of destinations, regional connections, and seamless travel experiences with minimal schedule disruptions. However, achieving these goals often involves large investments in purchasing or leasing new aircraft and hiring additional crew members. Alternatively, airline companies can establish codeshare agreements with each other to reduce costs and improve their network coverage.
A codeshare agreement (CA) is a business arrangement between two airlines. One of them can market a flight that is operated by another airline on or off its network, without using their own aircraft. This airline is called a marketing carrier. The other airline operating the flight is called the operating carrier [4,5]. These agreements are made as a result of alliances between two companies, and they allow airlines to expand their flight targets without incurring the huge costs associated with acquiring new aircraft. CAs provide more flight opportunities within an airline’s network, which benefits both customer satisfaction and reduces delays. Additionally, such agreements lead to increased mutual revenues and market shares for the companies [6].

2. Flight Scheduling, Fleet Assignment, and Aircraft Routing Problems

Airlines aim to maximize their profits by providing the optimum combination of fleet type and passengers’ demand. Assigning an aircraft that is smaller than the required passenger capacity to a flight leads to a direct loss of customers due to capacity insufficiency. Conversely, assigning an aircraft that is larger than the required passenger capacity to a flight can result in unsold seats. As a result of this, it causes an inability to sell the seats and reduce operating profits. Therefore, the FA problem is a crucial decision for an airline’s planning strategy [7].
There have been numerous studies on the FA problem in the literature since 1971. While the models of Abara [8] and Hane et al. [9] have contributed to the development of solutions to the problem, their applicability is limited due to certain assumptions such as fixed departure times for the same flight every day and deterministic passenger demand, which do not reflect real-life variability. Clarke et al. [10] developed a solution by incorporating the maintenance planning (MP) of aircraft at stations and crew issues into the FA model.
Berge and Hopperstad [11] suggested the re-flying concept to address demand fluctuations and used the demand-based dispatch approach to make capacity flexible allowing for fleet type assignments to occur closer to take-off. Talluri [12] extended their work in terms of opportunities and computation times. Levin [13] provided flexibility to the FA problem by allowing for variable take-off times and he was the first researcher to consider varying departure times with binary constraints by using integer programming. However, this model did not exclude the aircraft capacity and multiple fleet types. Rexing et al. [14] increased the flight connectivity possibilities by using a time window (TW) for departure times and optimizing time windows according to specific time zones. Belanger et al. [15] minimized the number of aircraft in the fleet by determining the fleet size (FSD). Thus, it aims for the utilization of the fleet (FU) optimally. ZEGHAL ET AL. [16] have addressed a flexible aircraft fleeting and routing problem, which is motivated by the Tunisian national carrier TunisAir. Flexible fleet (FF) is the ability to expand the fleet by renting an aircraft. Thus, more flights can be served.
Barnhart et al. [17] considered the passenger demand based on an itinerary (IFAP) and passenger spill and rescue costs and analyzed the profitability of the model by taking into account the effect of the flight network. In real-life scenarios, unexpected situations and disruptions can occur, so it is necessary to create robust models. Rosenberger et al. [18] developed a robust model using the hub-and-spoke network structure and produced short cycles sensitive to flight cancellations. The robustness of such an assignment and rotation has been demonstrated by using simulations of airline operations. Cadarso and Marín [19] proposed a robust model for the integrated FS and FA problem that takes into account the number of misconnected passengers. The model uses the exponential distribution of passenger connection times (PCTs) to calculate the probability of passengers missing their flight.
Smith and Johnson [20] proposed the concept of station purity (SP) by limiting the number of fleet type or crew-compatible families. Because each airport cannot serve each fleet type, Sherali et al. [21] developed a demand-driven re-flight model that dynamically reassigns the fleet type. Jacobs et al. [22], Dumas et al. [23], and Pilla et al. [24] relaxed the deterministic assumptions set by the basic FA problem. Sherali and Zhu [25] developed a two-stage stochastic programming model for the FA problem. Pilla et al. [26] explicitly evaluated the passenger demand by including direct demand scenarios in Sherali and Zhu’s [25] model. Naumann et al. [27] explained the uncertainty in demand as well as the uncertainty in fuel prices. Cadarso and Celis [28] developed a stochastic model that considers demand uncertainty (SD) and discrete passenger choice models for the FS and FA problem. The model aims to maximize the airline’s profits while minimizing the number of misconnected passengers. The passenger spill and rescue effects are also modeled and it focuses on the probability of passengers choosing a route. Atasoy et al. [29] proposed a similar integrated model based on discrete choice models.
Different to the common features used in the FA problem, Pita et al. [30] considered airports with the slot constrained (SC) in their study. The slot can be defined as the row/time allocation to an aircraft. The aim is to reduce large delays by controlling air traffic. Kenan et al. [31] assigned fleets to flights which have stochastic demand and stochastic fare (SF) based on fare classes. Sherali et al. [32,33] emphasized the importance of considering fuel consumption (FUEL) in airline optimization decisions. Gürkan et al. [34] integrated the cruise time controllability (CTC) of the aircraft using cruise speed adjustments into FA and AR problems. Jamili [35] integrated all three decisions into a single model, but also developed flight programs from the ground up and addressed the issue of fleet type route delays by introducing buffers. Safak et al. [36] took into account passenger connection times, fuel consumption, and CO2 emission costs associated with cruise speed settings by integrating the three decisions.
Kenan et al. [6] integrated CA into the FS, FA, and AR problems. It highlights that such agreements can significantly affect an airline’s profit by using fewer aircraft, fewer delays, and more flights. They also added optional flight legs (OF) to the model, which can be canceled according to demand changes. Şafak et al. [37] developed a three-stage stochastic programming model for the FS, FA, and AR problems. Cacchiani and Gonzalez [38] aggregated the FS, FA, AR, and CS problems. Xu et al. [39] proposed an integrated model for the FS, FA, and AR problems that allows for spreading delays, on-demand flights, and passenger spills. The spill passenger (SPP) is the number of passengers who cannot be served for any flight.
Kenan et al. [6] and Şafak et al. [36,37,40] have made significant contributions to solving the FA problem. However, Kenan’s study did not detail the costs related to passengers in the model, only considering the delay costs (DC) in the objective function. Şafak et al. [36,37] have discussed costs in detail, and CTC has been used to compensate for the uncertainty of non-cruise time (NCTU). However, different costs have been incurred by increasing the cruise time for new flights or leasing alternatives.

This entry is adapted from the peer-reviewed paper 10.3390/aerospace10121031

This entry is offline, you can click here to edit this entry!
Video Production Service