Havayolu operasyonlarında planlama ve çizelgeleme
Planning and scheduling in airline operations
Yazar: MUHAMMET DEVECİ
Danışman: DOÇ. DR. NİHAN ÇETİN DEMİREL
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2016
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Havayolu operasyonları uçuş çizelgeleme, uçak çizelgeleme, ekip çizelgeleme (ekip eşleme ve ekip atama) ve düzensiz olayların yönetilmesinden meydana gelmektedir. Bu planlama problemlerinden ekip eşleme problemi havayolu planlamasında karşılaşılan en kapsamlı problemlerden biridir. Bu tez çalışmasında, ekip eşleme problemi ayrıntılı olarak incelenip işletmeler için önemli maliyet kazanımları sağlanması ve bir optimizasyon algoritması geliştirilmesi amaçlanmaktadır. 
Ekip eşleme, bir veya birden fazla uçuş görevinden oluşan ve ana üs (ikamet merkezi)'te başlayıp tekrar ana üs'te biten uçuş dizisidir. Aynı zamanda ekip eşleme, havayolu ekip planlamasının ana maliyet belirleyici aşamasıdır. Havayolları için uçuş çizelgesinin ekip eşleme optimizasyonu son derece önemli bir süreçtir. Çünkü operasyonel ekip maliyetlerini minimuma indirebilmek ve ekip kullanımını maksimum yapabilmek için bu süreçten faydalanılır. Kabul edilebilir ekip eşlemesi SGHM (Sivil Havacılık Genel Müdürlüğü)'nin yasal kısıtlarına, FAA (Federal Havacılık) kurallarına ve havayolu şirketleri tarafından belirlenen özel kısıtlara uymak zorundadır. Bu kısıtlamalar ve kurallara dikkate alarak optimizasyonun temel amacı, uçuş çizelgesindeki tüm uçuşları kapsayan en düşük maliyetli ekip eşlemesini bulmaktır. Bu tez çalışması için, literatürde zaten var olan ekip eşleme optimizasyonları incelenmiş ve önceki çalışmaların üzerine yeni bir dinamik tabanlı genetik algoritma varyantları ve memetik algoritma yaklaşımı, alternatif ekip eşleme arama (pas uçuş azaltma) ve kısmi çözüm yaklaşımı (düşük maliyetli eşleme arama) geliştirilmiştir. 
Ekip eşleme problemi beş aşamada çözülmüştür. Problemin ilk aşamasında, SGHM'nin yasal kısıtlarına, FAA kurallarına ve havayolu şirketleri tarafından belirlenen özel kısıtlara uygun yasal ana ekip eşleme kümeleri oluşturulmuştur. İkinci aşamada ise, oluşturulan yasal ekip eşlemeleri arasından uçuş çizelgesindeki tüm uçuşları kapsayan en düşük maliyetli ekip eşlemesi alt kümesi oluşturulur. Üçüncü aşamada ise alt küme problemin optimizasyonu için evrimsel algoritmalardan olan genetik algoritma varyantları ve memetik algoritma yaklaşımı kullanılmıştır. Dördüncü aşamada, optimizasyon aşamasında elde edilen en iyi çözüm kümesine güncelleme işlemi uygulanır. Bu güncelleme işlemi pas uçuş azaltma ve düşük maliyetli eşleme arama sezgiselleri ile yapılmaktadır. Beşinci aşamada ise durdurma koşulu sağlanana kadar algoritma çalışır ve en iyi çözüm elde edilir. Ekip eşleme aşamasının çıktısı, optimizasyon aşamanın girdisi olarak kullanılmış olup problem Java Eclipse platformunda bütünleşik olarak çözülmüştür.  Önerilen algoritmayı test etmek için Türk Hava Yolları (THY) şirketinin web sayfasından alınan uçuş verileri kullanılmış ve optimal ekip çizelgeleri oluşturulmuştur. Önerilen algoritmalardan en iyisi literatürde meta-sezgisel yöntemler ile çözülmüş bir çalışmadan elde edilen sonuçlar ile karşılaştırılmıştır. Bu yöntemlerden elde edilen sonuçların anlamlı olup olmadığını test etmek için istatistiksel yöntemlerden faydalanılmıştır. Sonuçlardan da anlaşılacağı üzere yapılan iyileştirme ile önerilen algoritmanın çok daha iyi sonuçlar verdiği görülmüştür.

Abstract:
Airline operations consist of flight scheduling, aircraft scheduling, crew scheduling (crew pairing and crew rostering), as well as managing irregular issues. The crew pairing problem, which is one of the planning problems, is one of the most sophisticated problems encountered when dealing with airline operations. The purpose of this thesis is to examine the crew pairing problem in detail, to reduce the costs of the companies and to develop an optimization algorithm.   
Crew pairing stands for a series of flights, namely round-trips, starting and ending at the home base. Crew pairing is also the cost-determining phase of the crew scheduling.  For airliners, the crew pairing optimization of flight scheduling is vital since this process is used for minimizing the operational crew costs while maximizing the efficient use of the crew. An acceptable crew pairing must meet the legal restrictions of SGHM (Directorate General of Civil Aviation), FAA (Federal Aviation) rules and special restrictions laid down by the airliners. Considering these restrictions and rules, the main purpose of the optimization is to determine the most cost effective crew pairing comprising of all the flights in the flight schedule. For this thesis, crew pairing optimizations already existing in the literature were examined and, based on these studies, a new dynamic based on genetic algorithm variants, a memetic algorithm approach, an alternative crew pairing search (to reduce the occurrence of deadhead and a partial solution approach (a cost effective pairing search) were developed.  
The crew pairing problem was solved in 5 phases. In the first phase of the problem, the legal main crew pairings are formed pursuant to the legal restrictions of SGHM, the FAA rules and the special restrictions laid down by the airliners. As for the second phase, the subset of the most cost effective crew pairing consisting of all the flights in the flight schedule is constituted through selection among the legal main crew pairings mentioned above. As for the third phase, variants of the genetic algorithm and the memetic algorithm, which are evolutionary algorithms, are used for the optimization of the subset problem. In the fourth phase, the updates are applied to the subset according to the best solution set which was obtained in the optimization phase. This update is applied by means of heuristic approach to reduce the number of deadhead and of low-cost pairing search. As for the fifth phase, the algorithm runs until the stopping condition is satisfied and then the best solution is obtained. The outcome of the crew pairing process is used as the input for the optimization phase and the problem is solved in the Java Eclipse platform in integrated form. In order to test the recommended algorithm, flight data obtained from Turkish Airlines (THY) were used and the optimum crew schedules were created. The best of the recommended algorithms was compared with the outcomes obtained from the one studies, presenting problems solved through meta-heuristic methods. Statistical methods were used to determine whether the outcomes of these methods were meaningful. As it can be seen from the results, the recommended algorithm generated much better solutions after the phases were applied.