Havayolu ekip eşleme problemi: Genetik ve karma algoritmalar

Abstract

Havayolu endüstrisi; uçuş çizelgeleme, filo atama, uçak rotalama ve ekip atama gibi birçok eniyileme problemi ile ilgilenmektedir. Literatürde, bu problemler arasından en çok ekip planlama problemi çalışılmıştır. Çünkü ekip maliyetleri havayolu şirketleri tarafından kontrol edilebilir en büyük gider kalemini oluşturmaktadır. Etkin ve düşük maliyetli ekip çizelgeleri oluşturmak için literatürde birçok model önerilmektedir. Bu modellerin çoğu, problemi ekip eşleme ve ekip atama olmak üzere iki farklı probleme ayırarak çözmektedir.Bu tezde, uçuş çizelgesindeki tüm uçuşları kapsayan ve en düşük maliyete sahip ekip eşlemeleri kümesini seçmeyi amaçlayan ekip eşleme problemi çözülmektedir. Bu problemi çözmek için, rassal üretimli eniyileme algoritması, genetik tabanlı algoritma ve karma sütun üretme yaklaşımı olmak üzere üç farklı yaklaşım geliştirilmiştir. Geliştirilen algoritmaların performansını karşılaştırabilmek amacı ile bu problemin çözümünde literatürde en çok kullanılan teknik olan Sütun Üretme Yaklaşımı kullanılmıştır. Yaklaşımların performansları iki ayrı problem seti için incelenmiş ve sonuçlar elde edilmiştir.

The airline industry deals with many optimization problems such as flight and crew scheduling, fleet assignment and aircraft routing. As the crew expenses are the largest controllable component in airline companies? payments, crew schelduling is the most studied one among forementioned problems. To find effective and low cost crew schedules, many models are proposed in the literature. Many of these models divide the problem into two as crew pairing and crew rostering.In this study, a crew pairing problem that focuses on covering all the flights at the flight schedule and selecting the low cost crew pairing set is solved. Tree approaches, which are randomly generated optimization algorithm, genetic algorithm based approach and hybrid column generation approach, are developed. To compare the efficiency of the developed algorithms, a column generation approach which is commonly used in literature is prefered. Two different problem sets are used to test the performance of the algorithms and the solutions are demonstrated.