Havayolu Operasyonlarında Dayanıklı Ekip Eşleme İçin Eniyileme Yaklaşımı: Bir Havayolu Şirketi Uygulaması

Havayolu operasyonlarında, pahalı olan kaynakların etkin ve verimli bir şekilde kullanılabilmesi için, günümüz rekabet ortamında, çizelgelerin proaktif bir yaklaşım ile oluşturulması gerekmektedir. Olası aksaklık ve belirsizlik durumlarının planlama aşamasında hesaba katılması ve düzensizliklere karşı daha dayanıklı çizelgelerin oluşturulması sağlanmalıdır. Bu çalışmada, ekip çizelgeleme probleminin ilk adımı olan ekip eşleme problemi iki aşamalı olarak ele alınmıştır. İlk aşamada; ekip sayısının minimize edildiği ve etkinliğin maksimize edildiği farklı iki senaryo için küme bölüntüleme formülasyonu ile problem çözülmüş ve karar verici açısından farklı çözüm alternatifleri sunulmuştur. Problem modellenmeden önce karmaşık olan kısıt yapısından arındırılmış ve uçuş ayaklarını içeren bütün olası eşlemeler oluşturulmuştur. İkinci aşamada gecikmelerden daha az etkilenen bir eşleme kümesinin oluşturulması amaçlanmıştır. Türkiye’deki bir havayolu şirketine ait gerçek veriler kullanılarak yürütülen çalışmada, geçmiş gecikme değerleri analiz edilmiş ve her bir uçuş ayağı için ortalama bir gecikme değeri hesaplanmıştır. Hesaplanan bu gecikme değerleri ile yayılan gecikmeler modellenmiştir. Bütün uçuş ayaklarını kapsayan en iyi eşleme kümesinin seçimi için kurulan model, iki amaçlı optimizasyon tabanlı bir yaklaşım ile çözülmüştür. Ağırlıklı toplam yöntemi ile amaçlar birleştirilmiş ve hem yayılan gecikmesi en az olan hem de en iyi maliyete sahip olan eşlemeler farklı ağırlık değerleri için elde edilmiştir. Önerilen metodoloji ile kabul edilebilir bir işlem zamanında problemin çözümüne ulaşılabildiği gösterilmiştir.

Anahtar Kelimeler:

Havayolu ekip çizelgeleme, ekip eşleme problemi, gecikme yayılımı, dayanıklı ekip çizelgeleme, küme bölüntüleme formülasyonu

An Optimization Approach for Robust Crew Pairing in Airline Operations: An Airline Company Application

In order to use the pricy resources effectively and efficiently in airline operations, in the present competitive environment, schedules must be formed with a proactive approach. Possible delays and uncertainties must be taken into consideration during the planning phase and more robust schedules must be organized for uncertainties. In this study, crew pairing problem that is first step of the crew scheduling problem is handled at two stages. At the first stage, the problem is solved with a set partitioning formulation for two different scenarios where the crew number is minimized, and efficiency is maximized, and different solution alternatives are proposed for the decision maker. Before the problem is modelled, it is purified from the complicated constraint structure and all the possible pairings containing flight legs are created. At the second stage, it is aimed at forming a pairing set which is less affected by delays. In the study based on real data collected from an airline company in Turkey, the past delay values are analyzed, and an average delay value is calculated for each flight leg. With these calculated delay values, propagated delays are modelled. The model, which is formed to choose the best pairing set including all the flight legs, is analyzed with an approach based on bi-criteria optimization. The objectives are combined with the weighted sum method and pairings with optimal cost and less propagated delay are obtained for different weight values. With the proposed methodology, it is observed that the problem can be solved in reasonable operation time.

Keywords:

Airline crew scheduling, crew pairing problem, delay propagation, robust crew scheduling, set partitioning formulation,

PDF

___

Arabeyre J. P., Fearnley J., Steiger F. C. and Theather W., “Airline Crew Scheduling Problem: A Survey”, Transportation Science, 3(2): 140-163, (1969).
Rubin J. A., “Technique for the Solution of Massive Set Covering Problems with Applications to Airline Crew Scheduling”, Transportation Science, 7(1): 34-48, (1973).
Etschmaier M. M., Mathaisel D. F. X., “Airline Scheduling: An Overwiev”, Transportation Science, 19(2): 127-138, (1985).
Gershkoff I., “Optimizing Flight Crew Schedules”, Interfaces, 19(4): 29-43, (1989).
Graves G. W., McBride R. D., Gershkoff I., Anderson D. and Mahidhara D., “Flight Crew Scheduling”, Management Science, 39(6): 736-745, (1993).
Teodorović D. and Stojković G., “Model to Reduce Airline Schedule Disturbances”, J. Transp. Eng., 121(4): 324-331, (1995).
Stojković M., Soumis F. and Desrosiers J., “The Operational Airline Crew Scheduling Problem”, Transportation Science, 32(3): 232-245, (1998).
Ernst A. T., Jiang H., Krishnamoorthy M. and Sier D., “Staff Scheduling and Rostering: A Review of Applications, Methods and Models”, European Journal of Operational Research, 153(1): 3-27, (2004).
Zeybekcan N., “Airline Crew Scheduling”, Master of Science Thesis, Dokuz Eylül University Graduate School of Natural and Applied Sciences, (2005).
Çankaya G., “Havayolu Ekip Çizelgeleme Problemi için Bir Sütun Oluşturma Yaklaşımı ve Uygulaması”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, (2008).
AhmadBeygi S., Cohn A. and Weir M., “An Integer Programming Approach to Generating Airline Crew Pairings”, Computers & Operations Research, 36(4): 1284-1298, (2009).
Aydemir-Karadağ, A. and Dengiz, B., “A Hybrid Approach of Heuristic and Exact Method for Crew Pairing Problem”, 40th IEEE International Conference on Computers & Industrial Engineering (CIE), Awaji City, Japan, 1-6, (2010).
Deng G. F. and Lin W. T., “Ant Colony Optimization-Based Algorithm for Airline Crew Scheduling Problem”, Expert Systems with Applications, 38(5): 5787-5793, (2011).
Lijima, Y., Nishi, T., Inuiguchi, M., Takahashi, S., Ueda, K. and Ojima, K., “Modeling and Solution of Practical Airline Crew Scheduling Problems”, 2013 IEEE International Conference on Industrial Engineering and Engineering Management, Bangkok, 116-120, (2013).
Aydemir-Karadağ A., Dengiz B. and Bolat A., “Crew Pairing Optimization Based on Hybrid Approaches”. Computers & Industrial Engineering, 65(1): 87-96, (2013).
Chen C. H., Liu T. K. and Chou J. H., “Integrated Short-Haul Airline Crew Scheduling Using Multiobjective Optimization Genetic Algorithms”, IEEE Transactions on Systems, Man and Cybernetics: Systems, 43(5): 1077-1090, (2013).
Korkmaz, G., “Sivil Havacılıkta Uçucu Ekip Çizelgelemesi”, Yüksek Lisans Tezi, Hava Harp Okulu Havacılık ve Uzay Teknolojileri Enstitüsü, (2013).
Saddoune M., Desaulniers G. and Soumis F., “Aircrew Pairings with Possible Repetitions of the Same Flight Number”, Computers & Operations Research, 40(3): 805-814, (2013).
Cacchiani V. and Salazar-González, J. J. A., “Heuristic Approach for an Integrated Fleet-Assignment, Aircraft-Routing and Crew-Pairing Problem”, Electronic Notes in Discrete Mathematics, 41: 391-398, (2013).
Dunbar M., Froyland G. and Wu C. L., “An Integrated Scenario-Based Approach for Robust Aircraft Routing, Crew Pairing and Re-Timing”, Computers & Operations Research, 45: 68-86, (2014).
Ezzinbi O., Sarhani M., El Afia A. and Benedada Y., “Particle Swarm Optimization Algorithm for Solving Airline Crew Scheduling Problem”, 2014 IEEE International Conference on Logistics and Operations Management (GOL), Rabat, Morocco, 52-56, 2014.
Salazar-González J. J., “Approaches to Solve the Fleet-Assignment, Aircraft-Routing, Crew-Pairing and Crew-Rostering Problems of a Regional Carrier”, Omega, 43: 71-82, (2014).
Díaz-Ramírez J., Huertas J. I. and Trigos F., “Aircraft Maintenance, Routing and Crew Scheduling Planning for Airlines with a Single Fleet and a Single Maintenance and Crew Base”, Computers & Industrial Engineering, 75: 68-78, (2014).
Erdoğan G., Haouari M., Örmeci-Matoglu M. and Özener O. Ö., “Solving a Large Scale Crew Pairing Problem”, Journal of the Operational Research Society, 66(10): 1742-1754, (2015).
İpekçi-Çetin E., “Genetik Algoritmalarin Kullanımıyla Küme Bölme Modelinin Çözülmesi: Ekip Eşleştirme Uygulaması”, Havacılık ve Uzay Teknolojileri Dergisi, 5(1): 89-96, (2008).
Zeren B. and Özkol İ., “A novel column generation strategy for large scale airline crew pairing problems”, Expert Systems With Applications, 55: 133-144, (2016).
Quesnel F., Desaulniers G., Soumis F., “A new heuristic branching scheme for the crew pairing problem with base constraints”, Computers and Operations Research, 80: 159-172, (2017).
Yildiz B. C., Gzara F., Elhedhli S., “Airline crew pairing with fatigue: Modeling and analysis”, Transportation Research Part C, 74: 99-112, (2017).
Agustin A., Juan A., Pardo E. G., “A variable neighborhood search approach for the crew pairing problem”, Electronic Notes in Discrete Mathematics, 58: 87–94, (2017).
Doi T., Nishi T., Voß S., “Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time”, European Journal of Operational Research, 267: 428–438, (2018).
Deveci M., Çetin Demirel, N., “Evolutionary algorithms for solving the airline crew pairing problem”, Computers & Industrial Engineering, 115: 389–406, (2018).
Parmentier A., Meunier F., “Aircraft routing and crew pairing: Updated algorithms at Air France”, Omega, (Article in Press).
Cacchiani V., Salazar-González J.-J., “Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier”, Omega, (Article in Press).
Yen J. W. and Birge J. R. A., “Stochastic Programming Approach to the Airline Crew Scheduling Problem”, Transportation Science, 40: 3–14, (2006).
Shebalov S. and Klabjan D., “Robust Airline Crew Pairing: Move-up Crews”, Transportation Science, 40(3): 300-312, (2006).
Gao C., Johnson E. and Smith B., “Integrated Airline Fleet and Crew Robust Planning”, Transportation Science, 43(1): 2-16, (2009).
Tam B., Ehrgott M., Ryan D. and Zakeri G. A., “Comparison of Stochastic Programming and Bi-Objective Optimization Approaches to Robust Airline Crew Scheduling”, Operations Research Spectrum, 33(1): 49-75, (2011).
Ionescu L. and Kliewer N., “Increasing Flexibility of Airline Crew Schedules”, Procedia-Social and Behavioral Sciences, 20: 1019-1028, (2011).
Arikan, M., “The Impact of Airline Flight Schedules on Flight Delays: An Analysis of Block-Time, Delay Propagation and Schedule Optimization Using Stochastic Models”, Ph. D. Thesis, Purdue University Krannert School of Management, (2011).
Dück V., Ionescu L., Kliewer N. and Suhl L., “Increasing Stability of Crew and Aircraft Schedules”, Transportation Research Part C: Emerging Technologies, 20(1): 47-61, (2012).
Mou D. and Zhang Y., “Multi-Objective Integer Programing Model and Algorithm of the Crew Pairing Problem in a Stochastic Environment”, World Scientific and Engineering Academy and Society Transactions on Mathematics, 12(8): 809-818, (2013).
Muter İ., Birbil Ş. İ., Bülbül K., Şahin G., Yenigün H., Taş D. and Tüzün D., “Solving a Robust Airline Crew Pairing Problem with Column Generation”, Computers & Operations Research, 40(3): 815-830, (2013).
Aoun, O. and El Afia, A., “A Robust Crew Pairing Based on Multi-Agent Markov Decision Processes”, 2014 IEEE Second World Conference on Complex Systems, WCCS, Agadir, Morocco, 762-768, (2014).
Karacaoğlu, N., “An Application of Stochastic Programming on Robust Airline Scheduling”, Master of Science Thesis, Bilkent University Graduate School of Engineering and Science, (2014).
Gürkan, H., “An Integrated Approach for Robust Airline Scheduling, Aircraft Fleeting and Routing with Cruise Speed Control”, Master of Science Thesis, Bilkent University Graduate School of Engineering and Science, (2014).
Soykan, B., “Aksaklıklara Karşı Dayanıklı Havayolu Ekip Eşleme Problemi için Çözüm Algoritmaları ve Karar Destek Çerçeve Önerisi”, Yayımlanmamış Doktora Tezi, Kara Harp Okulu Savunma Bilimleri Enstitüsü, (2015).
Zhang D., Henry Lau H. Y. K. and Yu C., “A Two Stage Heuristic Algorithm for the Integrated Aircraft and Crew Schedule Recovery Problems”, Computers & Industrial Engineering, 87:436-453, (2015).
Bouarfa S., Müller J., Blom H., “Evaluation of a Multi-Agent System approach to airline disruption management”, Journal of Air Transport Management, 71: 108–118, (2018).
Ahmed M. B., Mansour F. Z., Haouari, M. “Robust integrated maintenance aircraft routing and crew pairing”, Journal of Air Transport Management, 73: 15–31, (2018).
BTS, Birleşmiş Milletler Ulaşım Departmanı Ulaştırma İstatistikleri Bürosu, https://www.transtats.bts.gov/OT_Delay/OT_DelayCause1.asp?pn=1, Erişim tarihi Mayıs 18, (2016).
Petersen, J. D., “Large-Scale Mixed Integer Optimization Approaches for Scheduling Airline Operations Under Irregularity”, Ph. D. Thesis, H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology, (2012).
Transportation Research Board, “Defining and Measuring Aircraft Delay and Capacity Thresholds”, Cooperative Research Program Report 104, Washington, 7, (2014).
Eurocontrol, “Planning for Delay: Influence of Flight Scheduling on Airline Punctuality, Trends in Air Traffic”, 22, (2011).
Chiraphadhanakul V. and Barnhart C., “Robust Flight Schedules Through Slack Re-Allocation”, Euro Journal on Transportation and Logistics, 2(4): 277-306, (2013).
Ozkan Aksu E. “Havayolu Operasyonlarında Dayanıklı Ekip Eşleme için Eniyileme Yaklaşımı: Bir Havayolu Şirketi Uygulaması”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, (2016).