Large scale optimization applications on the aircraft and aircrew recovery problems and their integration

Abstract

Havayolları endüstrisi her zaman ilgi çekici bir araştırma alanı olmuştur ve yöneylem araştırmacıları 1950 lerden beri, havayolları için çeşitli çözüm algoritmları ve optimizasyon araçları geliştirmektedirler. Şimdilerde havayolları bu geliştirilmiş olana optimisasyon araçlarını kullanarak kendi ana planlama süreçlerini rahatlıkla yönetebilmektedirler.Günümüzde, havayolları planlama süreçlerini yönetmektense beklenmeyen durumlar karşısında bozulan çizelgelerini düzeltmek için çaba harcamaktadırlar. Sıradan bir gün içinde, havayolları planlı çizelgelerininin bozulmasına sebep olan bir çok problemle karşılaşırlar. Böyle bir durumda da tüm operasyonel ve güvenlik kurallarına uyacak şekilde ellerindeki uygun kaynakları kullanarak, minimum maliyetli yeni çizelgeleri bulmaya çalışırlar. Bu tür yeniden çizelgeleme problemleri zorlu problemlerdir ve bu problemler için hala yeni araştırma alanları açıktır. Bu tez çalışmasında, uçak ve uçuş ekibi yeniden çizelgeleme problemleri ve bu problemlerin entegrasyonu için yeni ve etkin modeller ve çözüm algoritmaları geliştimek üzerine yoğunlaşılmıştır.Bu tez çalışmasında, öncelikle hem uçak, hem de uçuş ekibi yeniden çizelgeleme problemleri için ayrı ayrı değişik modeller geliştirilmiştir. Bu modeller geliştirilirken temel olarak iki farklı yöntem kullanılmıştır: Çoklu ürün ağ akışı ve kısıt programlama.Ancak, yeniden çizelgeleme problemleri çözülürken, hem uçuş ekibi hem de uçakların uygunluğu beraberce dikkate alınmalıdır. Bu tez çalışmasında uçak ve uçuş ekibi için ayrı ayrı geliştirilen modellerden başka, her ikisinin beraberce çözülebilmesi için de iki yeni çözüm algoritması geliştirilmiştir. Bu çözüm algoritmaları, uçak ve uçuş ekibi yeniden çizelgeleme problemlerini tek ve büyük bir modelde birleştirme ihtiyacı duymadan, ancak bu iki problemin biribiriyle olan bağını ve aralarındaki ilişkiyi dikkate alarak, iteratif bir şekilde çözer. Bu çözüm algotimaları yine iki farlı yöntem kullanılarak geliştilmiştir: Çoklu ürün ağ akışı ve kısıt programlama.Bu tez çalışmasında geliştirilen tüm model ve çözüm algoritmaları Türkiye'nin büyük havayollarından alınan gerçek verilerle test edilmiştir. Elde edilen sonuçlar, çözüm zamanları ve çözüm tekniklerinin kalitesi değerlendirilmiştir. Sonuçlar göstermektedir ki; önerilen çözüm algoritmları gerçek zamanda yeniden çizelgeleme yapabilmektedir ve kısıt programlama içeren çözüm yöntemi daha iyi sonuçlar üretmektedir. The air transport industry has always been an interesting research area and the researchers in the operations research field have been developing solution algorithms and optimization tools for airlines since 1950s. The airlines are now capable of managing their key planning process and schedules using these optimization tools.Today, the airlines spend a lot of effort on recovering their schedules in case of unpredictable events, rather than managing the planning process. In a typical day, airlines face several problems causing disruptions in the planned schedules and they try to find a minimal cost reschedules taking into account the available resources and satisfying all the operational and safety rules. These recovery problems are challenging and subject to further improvements. Therefore, this dissertation focuses on developing new efficient models and solution algorithms for the aircraft and crew recovery problems and their integration.In this dissertation several models for individual aircraft and crew recovery problems are developed using two different techniques; multi-commodity network flow and constraint programming techniques.However, while developing recovered schedules, both crew and aircraft availabilities should be considered together. This dissertation also proposes two new solution algorithms, which solve aircraft and crew recovery problems sequentially and in iterative manner, taking into account the dependency of two problems, representing the correlation between them without needing a very large model that would result integrating the aircrew and aircraft models. These solution algorithms are developed using two different techniques; multi-commodity network flow and constraint programming techniques.All the proposed models and solution algorithms developed in this dissertation are applied to real data obtained from the daily domestic flight schedule of major airlines operating in Turkey. The results, computational times and quality of the solution techniques are also evaluated. The results show that, the proposed solution algorithms generate recovered schedules in real time and constraint programming embedded solution approaches produces better solutions.