Flight Scheduling, Fleet Assignment, and Aircraft Routing Problems: Comparison
View Latest Version
Please note this is a comparison between Version 2 by Rita Xu and Version 1 by Kübra KIZILOĞLU.

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. 

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][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][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][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][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.

References

  1. Kalafatoğlu, Y. Effects of Pricing and Fleet Structure on the Airline Fleet Assignmen Problem. Master’s Thesis, The Graduate School of Engineering and Science of Boğaziçi University, İstanbul, Türkiye, 2014.
  2. Lohatepanont, M.; Barnhart, C. Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment. Transp. Sci. 2004, 38, 19–32.
  3. Abdelghany, A.; Abdelghany, K. Modeling Applications in the Airline Industry; Asghate: Burlington, VT, USA, 2009; pp. 53–129.
  4. Yimga, J. Code-Sharing Agreements and Path Quality in the US Airline Industry. Transp. Policy 2022, 116, 369–385.
  5. Zou, L.; Chen, X. The Effect of Code-Sharing Alliances on Airline Profitability. J. Air Transp. Manag. 2017, 58, 50–57.
  6. Kenan, N.; Diabat, A.; Jebali, A. Codeshare agreements in the integrated aircraft routing problem. Transp. Res. Part B Methodol. 2018, 117, 272–295.
  7. Sarsenov, B. Fleet Assignment Problem and a Case Study for Turkish Airlines. Master’s Thesis, Yıldız Technical University, İstanbul, Türkiye, 2011.
  8. Abara, J. Applying integer linear programming to the fleet assignment problem. Interfaces 1989, 19, 20–28.
  9. Hane, C.A.; Barnhart, C.; Johnson, E.L.; Marsten, R.E.; Nemhauser, G.L.; Sigismondi, G. The fleet assignment problem: Solving a large-scale integer program. Math. Program. 1995, 70, 211–232.
  10. Clarke, L.W.; Hane, C.A.; Johnson, E.L.; Nemhauser, G.L. Maintenance and crew considerations in fleet assignment. Transp. Sci. 1996, 30, 249–260.
  11. Berge, M.E.; Hopperstad, C.A. Demand driven dispatch: A method for dynamic aircraft capacity assignment, models and algorithms. Oper. Res. 1993, 41, 153–168.
  12. Talluri, K.T. Swapping applications in a daily airline fleet assignment. Transp. Sci. 1996, 30, 237–248.
  13. Levin, A. Scheduling and fleet routing models for transportation systems. Transp. Sci. 1971, 5, 232–255.
  14. Rexing, B.; Barnhart, C.; Kniker, T.; Jarrah, A.; Krishnamurthy, N. Airline fleet assignment with time windows. Transp. Sci. 2000, 34, 1–130.
  15. Belanger, N.; Desaulniers, G.; Soumis, F.; Desrosiers, J. Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues. Eur. J. Oper. Res. 2006, 175, 1754–1766.
  16. Zeghal, F.M.; Haouari, M.; Sherali, H.D.; Aissaoui, N. Flexible aircraft fleeting and routing at Tunis Air. J. Oper. Res. Soc. 2011, 62, 368–380.
  17. Barnhart, C.; Kniker, T.S.; Lohatepanont, M. Itinerary-based airline fleet assignment. Transp. Sci. 2002, 36, 199–217.
  18. Rosenberger, J.M.; Johnson, E.L.; Nemhauser, G.L. A robust fleet-assignment model with hub isolation and short cycles. Transp. Sci. 2004, 38, 357–368.
  19. Cadarso, L.; Marín, Á. Robust passenger-oriented timetable and fleet assignment integration in airline planning. J. Air Transp. Manag. 2013, 26, 44–49.
  20. Smith, B.C.; Johnson, E.L. Robust airline fleet assignment: Imposing station purity using station decomposition. Transp. Sci. 2006, 40, 497–516.
  21. Sherali, H.D.; Bish, E.K.; Zhu, X. Polyhedral analysis and algorithms for a demand-driven re-fleeting model for aircraft assignment. Transp. Sci. 2005, 39, 349–366.
  22. Jacobs, T.L.; Smith, B.C.; Johnson, E.L. Incorporating network flow effects into the airline fleet assignment process. Transp. Sci. 2008, 42, 514–529.
  23. Dumas, J.; Aithnard, F.; Soumis, F. Improving the objective function of the fleet assignment problem. Transp. Res. Part B Methodol. 2009, 43, 466–475.
  24. Pilla, V.L.; Rosenberger, J.M.; Chen, V.; Engsuwan, N.; Siddappa, S. A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model. Eur. J. Oper. Res. 2012, 216, 162–171.
  25. Sherali, H.D.; Zhu, X. Two-stage fleet assignment model considering stochastic passenger demands. Oper. Res. 2008, 56, 383–399.
  26. Pilla, V.L.; Rosenberger, J.M.; Chen, V.C.; Smith, B. A statistical computer experiments approach to airline fleet assignment. IIE Trans. 2008, 40, 524–537.
  27. Naumann, M.; Suhl, L.; Friedemann, M. A stochastic programming model for integrated planning of re-fleeting and financial hedging under fuel price and demand uncertainty. Procedia-Soc. Behav. Sci. 2012, 54, 47–55.
  28. Cadarso, L.; Celis, R. Integrated airline planning: Robust update of scheduling and fleet balancing under demand uncertainty. Transp. Res. Part C Emerg. Technol. 2017, 81, 227–245.
  29. Atasoy, B.; Salani, M.; Bierlaire, M. An integrated airline scheduling, fleeting, and pricing model for a monopolized market. Comput.-Aided Civ. Infrastruct. Eng. 2014, 29, 76–90.
  30. Pita, J.P.; Barnhart, C.; Antunes, A.P. Integrated flight scheduling and fleet assignment under airport congestion. Transp. Sci. 2013, 47, 477–492.
  31. Kenan, N.; Jebali, A.; Diabat, A. An integrated flight scheduling and fleet assignment problem under uncertainty. Comput. Oper. Res. 2018, 100, 333–342.
  32. Sherali, H.D.; Bish, E.K.; Zhu, X. Airline fleet assignment concepts, models, and algorithms. Eur. J. Oper. Res. 2006, 172, 1–30.
  33. Sherali, H.D.; Bae, K.H.; Haouari, M. A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture. Ann. Oper. Res. 2013, 210, 213–244.
  34. Gürkan, H.; Gürel, S.; Aktürk, M.S. An integrated approach for airline scheduling, aircraft fleeting and routing with cruise speed control. Transp. Res. Part C Emerg. Technol. 2016, 68, 38–57.
  35. Jamili, A. A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem. J. Air Transp. Manag. 2017, 58, 21–30.
  36. Şafak, Ö.; Gürel, S.; Aktürk, M.S. Integrated aircraft-path assignment and robust schedule design with cruise speed control. Comput. Oper. Res. 2017, 84, 127–145.
  37. Şafak, Ö.; Çavuş, Ö.; Aktürk, M.S. Multi-stage airline scheduling problem with stochastic passenger demand and non-cruise times. Transp. Res. Part B Methodol. 2018, 114, 39–67.
  38. Cacchiani, V.; Salazar-González, J.J. Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier. Omega 2020, 91, 102028.
  39. Xu, Y.; Wandelt, S.; Sun, X. Airline integrated robust scheduling with a variable neighborhood search based heuristic. Transp. Res. Part B Methodol. 2021, 149, 181–203.
  40. Şafak, Ö.; Atamtürk, A.; Aktürk, M.S. Accommodating new flights into an existing airline flight schedule. Transp. Res. Part C Emerg. Technol. 2019, 104, 265–286.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
ScholarVision Creations
Feedback