BI-OBJECTIVE GOAL PROGRAMMING FOR AIRLINE CREW PAIRING

Year 2022, , 126 - 136, 30.03.2022

İlkay Orhan

https://doi.org/10.18038/estubtda.979777

Abstract

The crew cost constitutes 20% of the direct operating cost in airline operations after the aircraft fuel cost. Effective crew scheduling can save tens of millions of dollars to the airlines and result in low-cost flight tickets for the passengers and improved quality of life for the crew. The crew pairing requires addressing union expectations, company rules, regulations of countries' civil aviation authorities. In this study, bi-objective goal programming is proposed to minimize the number of crew to perform flights and minimize the flight pairings cost while addressing the challenging issues mentioned above. The integer set-covering goal programming model is formulated and solved using GAMS mathematical programming software. The results showed that the bi-objective model could provide significant cost advantages to airlines. The computational experiments have been performed over a set of real data.

Keywords

Airline crew scheduling, Airline crew pairing, Air Transportation, Integer linear programming

References

• [1] Orhan I, Kapanoğlu M, Karakoc, TH. Planning and Scheduling of Airline Operations. Pamukkale University Journal of Engineering Sciences, 2010; 16(2), 181-191.
• [2] Cadarso L, Vaze V, Barnhart C, Marín A. Integrated airline scheduling: Considering competition effects and the entry of the high speed rail. Transportation Science, 2017; 51 (1), 132–154.
• [3] Qi X, Yang J, Yu G. Scheduling Problems in The Airline Industry, Handbook of Scheduling: Algorithms, Models and Performance Analysis, (Ed: Joseph, Y. and Leung, T), Chapman&Hall/CRC, 50. Chapter, New York, 2004.
• [4] Koh N, Larsen A, Larsen J, Ross A, Tiourine S. Airline disruption management-Perspectives, experiences, and Outlook. Journal of Air Transport Management, 2007; (13), 149-162.
• [5] Grosche T. Airline Scheduling Process. In Computational Intelligence in Integrated Airline Scheduling (pp. 7-46). Springer, Berlin, Heidelberg, 2009.
• [6] Kohl N, Karisch SE. Airline Crew Rostering: Problems Types, Modeling, and Optimization. Annals of Operations Research 2004; 127, 223-257.
• [7] Barnhart C, Belobaba P, Odoni AR. Applications of operations research in the air transport industry. Transportation Science, 2003; 37(4), 368-391.
• [8] Lettovsky L. Airline Operations Recovery: An Optimization Approach, Ph.D. Georgia Institute of Technology, USA. 1997
• [9] Kasirzadeh A, Saddoune M, Soumis F. Airline crew scheduling: models, algorithms, and data sets. EURO Journal on Transportation and Logistics, 2017; 6(2), 111-137.
• [10] Bazargan M. Airline Operations and Scheduling, Ashgate Publishing, Hampshire, 2004.
• [11] Andersson E, Housos E, Kohl N, Wedelin, D. Crew pairing optimization. In Operations research in the airline industry (pp. 228-258). Springer, Boston, 1998.
• [12] Yu G, Thengvall G, Airline Optimization, Handbook of Applied Optimization, ( Ed: Resende P.) Oxford University Press, New York, 2002.
• [13] Yan SY, Tu YP. A Network Model for Airline Cabin Crew Scheduling, European Journal of Operational Research, 2002; 140 (3), 531- 540.
• [14] Emden-Weinert T, Proksch M. Best Practice Simulated Annealing for The Airline Crew Scheduling Problem. Journal of Heuristics, 1999; 5 (4), 419-436.
• [15] Cavique I, Rego C, Themido I. Subgraph Ejection Chains and Tabu Search for The Crew Scheduling Problem. Journal of The Operational Research Society, 1999; 50 (6), 608-616.
• [16] Vance PH, Barnhart C, Johnson, EL. Airline Crew Scheduling: A New Formulation and Decomposition Algorithm. Operations Research, 1997; 45 (2), 188-200.
• [17] Desaulniers G, Desrosiers J, Dumas Y. Solomon MM, Soumis F. Daily Aircraft Routing and Scheduling. Management Science, 1997; 43(6), 841-855.
• [18] Klabjan D, Johnson EL, Nemhauser GL. Airline Crew Scheduling with Regularity. Transportation Science, 2001; 35 (4), 359-374.
• [19] Yan S, Chang J. Airline Cockpit Crew Scheduling. European Journal of Operational Research, 2002; 136, 501-511.
• [20] Cordeau JF., Stojkovic, G., Soumis, F., Et Al. Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling, Transportation Science, 2001; 35 (4), 375-388.
• [21] Yildiz BC, Gzara F, Elhedhli S. Airline crew pairing with fatigue: Modeling and analysis. Transportation Research Part C: Emerging Technologies, 2017; 74, 99-112.
• [22] Deveci M, Demirel NC. A survey of the literature on airline crew scheduling. Engineering Applications of Artificial Intelligence, 2018; 74, 54–69.
• [23] Quesnel F, Desaulniers, G, Soumis F. A branch-and-price heuristic for the crew pairing problem with language constraints. European Journal of Operational Research, 2020; 283(3), 1040-1054.
• [24] Wen X, Ma HL, Chung SH, Khan WA. Robust airline crew scheduling with flight flying time variability. Transportation Research Part E: Logistics and Transportation Review 2020; 144, 102132.
• [25] Parmentier A, Meunier F. Aircraft routing and crew pairing: Updated algorithms at Air France. Omega, 2020; 93, 102073.
• [26] Medard CP, Sawhney N. Airline crew scheduling from planning to operations. European Journal of Operational Research, 2007; 183(3), 1013-1027.
• [27] Ozdemir HT, Mohan CK. Flight graph based genetic algorithm for crew scheduling in airlines. Information Sciences 2001; 133(3-4), 165-173.
• [28] Soykan B, Serpil E. A branch-and-price algorithm for the robust airline crew pairing problem. The Journal of Defense Sciences, 2014; 13(1), 37-74.
• [29] Gopalakrishnan B, Johnson EL. Airline Crew Scheduling: State-of-The-Art, Annals of Operations Research, 2005; 140 (1), 305-337.
• [30] Aydemir-Karadag A, Dengiz B, Bolat A. Crew pairing optimization based on hybrid approaches. Computers & Industrial Engineering, 2013; 65(1), 87-96.
• [31] Barnhart C, Cohn AM, Johnson EL, Klabjan, D, Nemhauser GL, Vance P.H. Airline Crew Scheduling, Handbook of Transportation Science (Ed: Randolph W.Hall), Kluwer Academic Publishers Massachusetts, 2003.
• [32] Anbil R, Gelman E, Patty B, Tanga,R. Recent advances in crew-pairing optimization at American Airlines. Interfaces, 1991; 21(1), 62-74.
• [33] Souai N, Teghem J. Genetic algorithm-based approach for the integrated airline crew-pairing and rostering problem. European Journal of Operational Research, 2009; 199(3), 674-683.
• [34] SHT-6A.50 Uçucu Ekip Uçuş Görev ve Dinlenme Süreleri ile Uygulama Esasları Talimatı, Sivil Havacılık Genel Müdürlüğü, http://web.shgm.gov.tr/doc5/sht6arev06.pdf (last accessed: 27.05.2021).