GENETIC ALGORITHM APPLICATION FOR CREW PAIR OPTIMIZATION IN AIRLINE CREW PLANNING

Öz

In this study, it is addressed the airline crew scheduling problem which is one of the biggest cost elements for airline companies and to develop a new method with genetic algorithms to generate crew pairings which is the first part of airline crew scheduling with better optimization. Crew scheduling topic is the biggest cost element for the airline companies after the fuel costs. Also this topic relates to worker effiency parameter,which is one of the most important parameters for airline companies,due to it’s constraints about worker usage which are written on civil aviation laws. In this study, previous works about crew pairing optimization examined and upgrades developed for the cost reduction with minimizing the number of deadhead flights. Genetic algorithm operators existing in the previous studies have been upgraded and better results provided with new improved operators. Methods and the results were compared with the previous work about the topic.

Anahtar Kelimeler

• Airline crew scheduling
• crew pairing
• genetic algorithms
• optimization
• heuristic methods

HAVAYOLU EKİP ROTASYON OPTİMİZASYONU İÇİN GENETİK ALGORİTMA KULLANIMI

Öz

Bu çalışmada, havayolu şirketlerinin en büyük gider kalemlerinden biri olan ekip planlama konusu ve bu sürecin ilk adımı olan ekip rotasyonlarının üretimi için genetik algoritmalar ile bir optimizasyon algoritmasının geliştirilmesi ele alınmıştır. Ekip planlama konusu havayolu şirketlerinin yakıt maliyetlerinden sonraki en büyük gider kalemidir. Ayrıca bu konu havacılık kanun ve yönetmeliklerinde yer alan kısıtlardan dolayı personellerin kullanım oranını da etkilediğinden şirketlerin bünyesinde yer alan personellerin verimli kullanımı da ekip planlaması yapılırken etkilenen önemli bir parametredir. Çalışmada ekip rotasyonu optimizasyonu konusunda literatürdeki çalışmalar incelenmiş ve pas uçuş sayısının azaltılmasıyla maliyetin minimize edilmesi konusunda geliştirilmeler yapılmıştır. Çalışmada literatürde var olan genetik algoritma operatörleri geliştirilerek daha optimize sonuçlar elde edilmiştir. Daha önce bu konuda hazırlanmış olan çözümlerin sonuçları ile karşılaştırmalar yapılmış ve değerlendirilmiştir.

Anahtar Kelimeler

• ekip rotasyonu
• genetik algoritmalar
• optimizasyon
• Havayolu ekip planlama
• sezgisel metodlar

Kaynakça

1. AhmadBeygi, S., Cohn, A., & Weir, M. (2009). An integer programming approach to generating airline crew pairings. Computers & Operations Research, 36(4), 1284-1298.
2. Aksu, E. Ö., & Temiz, İ. (2021). Havayolu operasyonlarında dayanıklı ekip eşleme için eniyileme yaklaşımı: bir havayolu şirketi uygulaması. Politeknik Dergisi, 24(2), 417-429.
3. Anbil, R., Tanga, R., & Johnson, E. L. (1992). A global approach to crew-pairing optimization. IBM Systems Journal, 31(1), 71-78.
4. Arabeyre, J. P., Fearnley, J., Steiger, F. C., & Teather, W. (1969). The airline crew scheduling problem: A survey. Transportation Science, 3(2), 140-163.
5. Aydemir, A. A. (2008). Havayolu ekip eşleme problemi: Genetik ve karma algoritmalar, Başkent Üniversitesi Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, 120, Ankara.
6. Beasley, J. E., & Chu, P. C. (1996). A genetic algorithm for the set covering problem. European journal of operational research, 94(2), 392-404.
7. Çankaya, G., & Arıkan, M. (2009). Sütun oluşturma yaklaşımı ile bir havayolu ekip çizelgeleme uygulaması. Journal of the Faculty of Engineering & Architecture of Gazi University, 24(1).
8. Elhabashy, A. E., Elwany, M. H., Fors, M. N., & Abouelseoud, Y. (2014, Ekim, 14-16). Solving the airlıne crew pairing problem using genetic algorithms. CIE44 & IMSS’14 Proceedings. Istanbul. 2167-2181

9. Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European journal of operational research, 153(1), 3-27.
10. Etschmaier, M. M., & Mathaisel, D. F. (1985). Airline scheduling: An overview. Transportation Science, 19(2), 127-138.
11. Graves, G. W., McBride, R. D., Gershkoff, I., Anderson, D., & Mahidhara, D. (1993). Flight crew scheduling. Management science, 39(6), 736-745.
12. Gopalakrishnan, B., & Johnson, E. (2005). Airline crew scheduling: State-of-the-art. Annals of Operations Research, 140(1), 305-337.
13. Holland, J. H., & Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan press.
14. Kornilakis, H., & Stamatopoulos, P. (2002, April). Crew pairing optimization with genetic algorithms. In Hellenic conference on artificial intelligence (pp. 109-120). Springer, Berlin, Heidelberg.
15. Medard, C. P., & Sawhney, N. (2007). Airline crew scheduling from planning to operations. European Journal of Operational Research, 183(3), 1013-1027.
16. Özdemir, U. (2009). Methodology for crew-pairing problem in airline crew scheduling, Boğaziçi Üniversitesi, Yüksek Lisans Tezi, 40, İstanbul.
17. Rubin, J. (1973). A technique for the solution of massive set covering problems, with application to airline crew scheduling. Transportation Science, 7(1), 34-48.
18. Rushmeier, R. A., Hoffman, K. L., & Padberg, M. (1995). Recent advances in exact optimization of airline scheduling problems. Dept. of Operations Research and Operations Engineering, George Mason University, Working Paper.
19. 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.
20. Teodorović, D., & Stojković, G. (1990). Model for operational daily airline scheduling. Transportation Planning and Technology, 14(4), 273-285.
21. Zeren, B. (2007). Genetik Algoritmalar ile Havayolu Ekip Planlamada Ekip Rotasyon Optimizasyonu, İstanbul Teknik Üniversitesi Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, 40, İstanbul.