Airline planning and scheduling: Models and solution methodologies

Abstract

The airline industry is a representative industry with high cost and low profitability. Therefore, airlines should carefully plan their schedules to ensure that overall profit is maximized. We review the literature on airline planning and scheduling and focus on mathematical formulations and solution methodologies. Our research framework is anchored on three major problems in the airline scheduling, namely, fleet assignment, aircraft routing, and crew scheduling. General formulation, widely used solution approaches, and important extensions are presented for each problem and integrated problems. We conclude the review by identifying promising areas for further research.

Graphical abstract

Keywords

airline planning / fleet assignment problem / aircraft routing problem / crew pairing problem / crew rostering problem / crew scheduling problem / integrated planning

References

[1] Abara J (1989). Applying integer linear programming to the fleet assignment problem. Interfaces, 19(4): 20–28

[2] AEINFO (2016). Aircraft maintenance checks.

[3] Ageeva Y (2000). Approaches to Incorporating Robustness into Airline Scheduling. Dissertation for the Master’s Degree. Cambridge: Massachusetts Institute of Technology

[4] AGIFORS (2019). Delivering operations research and analytics innovation.

[5] AhmadBeygi S, Cohn A, Weir M (2009). An integer programming approach to generating airline crew pairings. Computers & Operations Research, 36(4): 1284–1298

[6] AINonline (2017). Chinese airlines need 5000 pilots per year in next 20 years.

[7] Airbus (2018). Airbus 2018 price list press release.

[8] Antunes D, Vaze V, Antunes A P (2019). A robust pairing model for airline crew scheduling. Transportation Science, 53(6): 1751–1771

[9] Arabeyre J P, Fearnley J, Steiger F C, Teather W (1969). The airline crew scheduling problem: A survey. Transportation Science, 3(2): 140–163

[10] Aviation Enthusiasts (2019a). Aircraft maintenance A check.

[11] Aviation Enthusiasts (2019b). Aircraft maintenance B check.

[12] Barnhart C, Belobaba P, Odoni A R (2003a). Applications of operations research in the air transport industry. Transportation Science, 37(4): 368–391

[13] Barnhart C, Boland N L, Clarke L W, Johnson E L, Nemhauser G L, Shenoi R G (1998). Flight string models for aircraft fleeting and routing. Transportation Science, 32(3): 208–220

[14] Barnhart C, Cohn A (2004). Airline schedule planning: Accomplishments and opportunities. Manufacturing & Service Operations Management, 6(1): 3–22

[15] Barnhart C, Cohn A M, Johnson E L, Klabjan D, Nemhauser G L, Vance P H (2003b). Airline crew scheduling. In: Handbook of Transportation Science. Boston, MA: Springer, 517–560

[16] Barnhart C, Farahat A, Lohatepanont M (2009). Airline fleet assignment with enhanced revenue modeling. Operations Research, 57(1): 231–244

[17] Barnhart C, Hatay L, Johnson E L (1995). Deadhead selection for the long-haul crew pairing problem. Operations Research, 43(3): 491–499

[18] Barnhart C, Kniker T S, Lohatepanont M (2002). Itinerary-based airline fleet assignment. Transportation Science, 36(2): 199–217

[19] Barnhart C, Shenoi R G (1998). An approximate model and solution approach for the long-haul crew pairing problem. Transportation Science, 32(3): 221–231

[20] Barnhart C, Smith B (2012). Quantitative Problem Solving Methods in the Airline Industry: A Modeling Methodology Handbook. Boston, MA: Springer

[21] Başdere M, Bilge Ü (2014). Operational aircraft maintenance routing problem with remaining time consideration. European Journal of Operational Research, 235(1): 315–328

[22] Bélanger N, Desaulniers G, Soumis F, Desrosiers J (2006a). Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues. European Journal of Operational Research, 175(3): 1754–1766

[23] Bélanger N, Desaulniers G, Soumis F, Desrosiers J, Lavigne J (2006b). Weekly airline fleet assignment with homogeneity. Transportation Research Part B: Methodological, 40(4): 306–318

[24] Belobaba P, Odoni A, Barnhart C (2009). The Global Airline Industry. West Sussex: John Wiley & Sons

[25] Berge M E, Hopperstad C A (1993). Demand driven dispatch: A method for dynamic aircraft capacity assignment, models and algorithms. Operations Research, 41(1): 153–168

[26] Boeing (2019a). Commercial market outlook 2019–2038.

[27] Boeing (2019b). Pilot & technician outlook 2019–2038.

[28] Burke E K, de Causmaecker P, de Maere G, Mulder J, Paelinck M, Vanden Berghe G (2010). A multi-objective approach for robust airline scheduling. Computers & Operations Research, 37(5): 822–832

[29] Cacchiani V, Salazar-González J J (2017). Optimal solutions to a real-world integrated airline scheduling problem. Transportation Science, 51(1): 250–268

[30] Cacchiani V, Salazar-González J J (2020). Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier. Omega, 91: 102028

[31] Cadarso L, de Celis R (2017). Integrated airline planning: Robust update of scheduling and fleet balancing under demand uncertainty. Transportation Research Part C: Emerging Technologies, 81: 227–245

[32] Cappanera P, Gallo G (2004). A multicommodity flow approach to the crew rostering problem. Operations Research, 52(4): 583–596

[33] Clarke L, Hane C, Johnson E, Nemhauser G (1996). Maintenance and crew considerations in fleet assignment. Transportation Science, 30(3): 249–260

[34] Clarke L, Johnson E, Nemhauser G, Zhu Z (1997). The aircraft rotation problem. Annals of Operations Research, 69: 33–46

[35] Cohn A M, Barnhart C (2003). Improving crew scheduling by incorporating key maintenance routing decisions. Operations Research, 51(3): 387–396

[36] Cordeau J F, Stojković G, Soumis F, Desrosiers J (2001). Benders’ decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science, 35(4): 375–388

[37] Daskin M S, Panayotopoulos N D (1989). An Llagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks. Transportation Science, 23(2): 91–99

[38] Dawid H, König J, Strauss C (2001). An enhanced rostering model for airline crews. Computers & Operations Research, 28(7): 671–688

[39] Deveci M, Demirel N C (2015). Airline crew pairing problem: A literature review. In: 11th International Scientific Conference on Economic and Social Development—Building Resilient Society. Zagreb, Croatia: Varazdin Development and Entrepreneurship Agency (VADEA), 103–111

[40] Doi T, Nishi T, Voß S (2018). Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time. European Journal of Operational Research, 267(2): 428–438

[41] Dunbar M, Froyland G, Wu C L (2012). Robust airline schedule planning: Minimizing propagated delay in an integrated routing and crewing framework. Transportation Science, 46(2): 204–216

[42] Dunbar M, Froyland G, Wu C L (2014). An integrated scenario-based approach for robust aircraft routing, crew pairing and re-timing. Computers & Operations Research, 45: 68–86

[43] Eltoukhy A E E, Chan F T S, Chung S H (2017). Airline schedule planning: A review and future directions. Industrial Management & Data Systems, 117(6): 1201–1243

[44] Farkas A (1996). The Influence of Network Effects and Yield Management on Airline Fleet Assignment Decisions. Dissertation for the Doctoral Degree. Cambridge: Massachusetts Institute of Technology

[45] Federal Aviation Administration (2019). Emergency equipment: Extended overwater operations.

[46] Feo T A, Bard J F (1989). Flight scheduling and maintenance base planning. Management Science, 35(12): 1415–1432

[47] Froyland G, Maher S J, Wu C L (2014). The recoverable robust tail assignment problem. Transportation Science, 48(3): 351–372

[48] Gall P (2018). The US is facing a serious shortage of airline pilots. The Conversation. CNN Travel

[49] Gamache M, Soumis F, Marquis G, Desrosiers J (1999). A column generation approach for large-scale aircrew rostering problems. Operations Research, 47(2): 247–263

[50] Gao C, Johnson E, Smith B (2009). Integrated airline fleet and crew robust planning. Transportation Science, 43(1): 2–16

[51] Goldman D (2019). Airlines are on pace for their worst year since 2014. CNN Business

[52] Gopalakrishnan B, Johnson E L (2005). Airline crew scheduling: State-of-the-art . Annals of Operations Research, 140(1): 305–337

[53] Gopalan R, Talluri K T (1998). The aircraft maintenance routing problem. Operations Research, 46(2): 260–271

[54] Guo Y, Mellouli T, Suhl L, Thiel M P (2006). A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases. European Journal of Operational Research, 171(3): 1169–1181

[55] Hane C A, Barnhart C, Johnson E L, Marsten R E, Nemhauser G L, Sigismondi G (1995). The fleet assignment problem: Solving a large-scale integer program. Mathematical Programming, 70(1–3): 211–232

[56] Haouari M, Aissaoui N, Zeghal Mansour F (2009). Network flow-based approaches for integrated aircraft fleeting and routing. European Journal of Operational Research, 193(2): 591–599

[57] Haouari M, Shao S, Sherali H D (2013). A lifted compact formulation for the daily aircraft maintenance routing problem. Transportation Science, 47(4): 508–525

[58] Haouari M, Sherali H D, Zeghal Mansour F, Aissaoui N (2011). Exact approaches for integrated aircraft fleeting and routing at TunisAir. Computational Optimization and Applications, 49(2): 213–239

[59] Haouari M, Zeghal Mansour F, Sherali H D (2019). A new compact formulation for the daily crew pairing problem. Transportation Science, 53(3): 811–828

[60] Hessburg J (2000). What’s this ‘A’ check, ‘C’ check stuff?

[61] Hoffman K L, Padberg M (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science, 39(6): 657–682

[62] IATA (2018). Economic performance of the airline industry. IATA Economics Report

[63] IATA (2019). Air passenger demand 2018—infographic.

[64] ICAO (2019). Fatigue management.

[65] ICAO (2018). Long-term traffic forecasts—passenger and cargo.

[66] INFORMS (2019). About the aviation applications section.

[67] Ioachim I, Desrosiers J, Soumis F, Bélanger N (1999). Fleet assignment and routing with schedule synchronization constraints. European Journal of Operational Research, 119(1): 75–90

[68] Irnich S, Desaulniers G (2005). Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M M, eds. Column Generation. Boston, MA: Springer, 33–65

[69] Jacobs T L, Smith B C, Johnson E L (2008). Incorporating network flow effects into the airline fleet assignment process. Transportation Science, 42(4): 514–529

[70] Kasirzadeh A, Saddoune M, Soumis F (2017). Airline crew scheduling: Models, algorithms, and data sets. EURO Journal on Transportation and Logistics, 6(2): 111–137

[71] Kenan N, Jebali A, Diabat A (2018). The integrated aircraft routing problem with optional flights and delay considerations. Transportation Research Part E: Logistics and Transportation Review, 118: 355–375

[72] Keysan G, Nemhauser G L, Savelsbergh M W P (2010). Tactical and operational planning of scheduled maintenance for per-seat, on-demand air transportation. Transportation Science, 44(3): 291–306

[73] Khaled O, Minoux M, Mousseau V, Michel S, Ceugniet X (2018). A compact optimization model for the tail assignment problem. European Journal of Operational Research, 264(2): 548–557

[74] Klabjan D, Johnson E L, Nemhauser G L, Gelman E, Ramaswamy S (2001). Airline crew scheduling with regularity. Transportation Science, 35(4): 359–374

[75] Klabjan D, Johnson E L, Nemhauser G L, Gelman E, Ramaswamy S (2002). Airline crew scheduling with time windows and plane-count constraints. Transportation Science, 36(3): 337–348

[76] Kohl N, Karisch S E (2004). Airline crew rostering: Problem types, modeling, and optimization. Annals of Operations Research, 127(1–4): 223–257

[77] Lan S, Clarke J P, Barnhart C (2006). Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions. Transportation Science, 40(1): 15–28

[78] Liang Z, Chaovalitwongse W A (2013). A network-based model for the integrated weekly aircraft maintenance routing and fleet assignment problem. Transportation Science, 47(4): 493–507

[79] Liang Z, Chaovalitwongse W A, Huang H C, Johnson E L (2011). On a new rotation tour network model for aircraft maintenance routing problem. Transportation Science, 45(1): 109–120

[80] Liang Z, Feng Y, Zhang X, Wu T, Chaovalitwongse W A (2015). Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem. Transportation Research Part B: Methodological, 78: 238–259

[81] Liang Z, Xiao F, Qian X, Zhou L, Jin X, Lu X, Karichery S (2018). A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility. Transportation Research Part B: Methodological, 113: 70–90

[82] Lohatepanont M, Barnhart C (2004). Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment. Transportation Science, 38(1): 19–32

[83] Maenhout B, Vanhoucke M (2010). A hybrid scatter search heuristic for personalized crew rostering in the airline industry. European Journal of Operational Research, 206(1): 155–167

[84] Maher S J, Desaulniers G, Soumis F (2018). The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints. European Journal of Operational Research, 264(2): 534–547

[85] Mazareanu E (2019). Air transportation—statistics & facts.

[86] Mercier A, Cordeau J F, Soumis F (2005). A computational study of Benders’ decomposition for the integrated aircraft routing and crew scheduling problem. Computers & Operations Research, 32(6): 1451–1476

[87] Papadakos N (2009). Integrated airline scheduling. Computers & Operations Research, 36(1): 176–195

[88] PEA (2019). What do airline pilots earn?

[89] Pilla V L, Rosenberger J M, Chen V, Engsuwan N, Siddappa S (2012). A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model. European Journal of Operational Research, 216(1): 162–171

[90] Pilla V L, Rosenberger J M, Chen V C P, Smith B (2008). A statistical computer experiments approach to airline fleet assignment. IIE Transactions, 40(5): 524–537

[91] Pita J P, Adler N, Antunes A P (2014). Socially-oriented flight scheduling and fleet assignment model with an application to Norway. Transportation Research Part B: Methodological, 61: 17–32

[92] Pita J P, Barnhart C, Antunes A P (2013). Integrated flight scheduling and fleet assignment under airport congestion. Transportation Science, 47(4): 477–492

[93] Qantas (2016). The A, C and D of aircraft maintenance.

[94] Rexing B, Barnhart C, Kniker T, Jarrah A, Krishnamurthy N (2000). Airline fleet assignment with time windows. Transportation Science, 34(1): 1–20

[95] Rosenberger J M, Johnson E L, Nemhauser G L (2004). A robust fleet-assignment model with hub isolation and short cycles. Transportation Science, 38(3): 357–368

[96] Rushmeier R A, Kontogiorgis S A (1997). Advances in the optimization of airline fleet assignment. Transportation Science, 31(2): 159–169

[97] Ruther S, Boland N, Engineer F G, Evans I (2017). Integrated aircraft routing, crew pairing, and tail assignment: Branch-and-price with many pricing problems. Transportation Science, 51(1): 177–195

[98] Saddoune M, Desaulniers G, Elhallaoui I, Soumis F (2012). Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Transportation Science, 46(1): 39–55

[99] Saddoune M, Desaulniers G, Soumis F (2013). Aircrew pairings with possible repetitions of the same flight number. Computers & Operations Research, 40(3): 805–814

[100] Safaei N, Jardine A K S (2018). Aircraft routing with generalized maintenance constraints. Omega, 80: 111–122

[101] Salazar-González J J (2014). Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier. Omega, 43: 71–82

[102] Sandhu R, Klabjan D (2007). Integrated airline fleeting and crew-pairing decisions. Operations Research, 55(3): 439–456

[103] Sarac A, Batta R, Rump C M (2006). A branch-and-price approach for operational aircraft maintenance routing. European Journal of Operational Research, 175(3): 1850–1869

[104] Seidenman P, Spanovich D J (2018). Airlines reevaluate phased A checks: The changing dynamics of the $13 billion a year line maintenance segment.

[105] Shao S, Sherali H D, Haouari M (2017). A novel model and decomposition approach for the integrated airline fleet assignment, aircraft routing, and crew pairing problem. Transportation Science, 51(1): 233–249

[106] Shebalov S, Klabjan D (2006). Robust airline crew pairing: Move-up crews. Transportation Science, 40(3): 300–312

[107] Sherali H D, Bae K H, Haouari M (2010). Integrated airline schedule design and fleet assignment: Polyhedral analysis and Benders’ decomposition approach. INFORMS Journal on Computing, 22(4): 500–513

[108] Sherali H D, Bae K H, Haouari M (2013a). An integrated approach for airline flight selection and timing, fleet assignment, and aircraft routing. Transportation Science, 47(4): 455–476

[109] Sherali H D, Bae K H, Haouari M (2013b). A Benders’ decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture. Annals of Operations Research, 210(1): 213–244

[110] Sherali H D, Bish E K, Zhu X (2006). Airline fleet assignment concepts, models, and algorithms. European Journal of Operational Research, 172(1): 1–30

[111] Smith B C, Johnson E L (2006). Robust airline fleet assignment: Imposing station purity using station decomposition. Transportation Science, 40(4): 497–516

[112] Souai N, Teghem J (2009). Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem. European Journal of Operational Research, 199(3): 674–683

[113] Sriram C, Haghani A (2003). An optimization model for aircraft maintenance scheduling and re-assignment. Transportation Research Part A: Policy and Practice, 37(1): 29–48

[114] Stojković M, Soumis F (2001). An optimization model for the simultaneous operational flight and pilot scheduling problem. Management Science, 47(9): 1290–1305

[115] Subramanian R, Scheff R P, Quillinan J D, Wiper D S, Marsten R E (1994). Coldstart: Fleet assignment at Delta air lines. Interfaces, 24(1): 104–120

[116] Talluri K T (1998). The four-day aircraft maintenance routing problem. Transportation Science, 32(1): 43–53

[117] Vance P H, Barnhart C, Johnson E L, Nemhauser G L (1997). Airline crew scheduling: A new formulation and decomposition algorithm. Operations Research, 45(2): 188–200

[118] Wei K, Vaze V (2018). Modeling crew itineraries and delays in the national air transportation system. Transportation Science, 52(5): 1276–1296

[119] Weide O, Ryan D, Ehrgott M (2010). An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers & Operations Research, 37(5): 833–844

[120] Yan C, Kung J (2018). Robust aircraft routing. Transportation Science, 52(1): 118–133

[121] Yan S, Tseng C H (2002). A passenger demand model for airline flight scheduling and fleet routing. Computers & Operations Research, 29(11): 1559–1581

[122] Yen J W, Birge J R (2006). A stochastic programming approach to the airline crew scheduling problem. Transportation Science, 40(1): 3–14

[123] Zeghal Mansour F, Haouari M, Sherali H D, Aissaoui N (2011). Flexible aircraft fleeting and routing at TunisAir. Journal of the Operational Research Society, 62(2): 368–380

[124] Zeighami V, Soumis F (2019). Combining Benders’ decomposition and column generation for integrated crew pairing and personalized crew assignment problems. Transportation Science, 53(5): 1479–1499

RIGHTS & PERMISSIONS

2020 Higher Education Press