Aksaklıklara karşı dayanıklı Havayolu Ekip Eşleme Problemi için çözüm algoritmaları ve karar destek çerçeve önerisi

Abstract

Bu tez çalışmasında aksaklıklara karşı dayanıklı havayolu ekip eşleme problemi (HEEP) ile ilgilenilmiştir. Gerçek yaşam problemi olan aksaklıklara karşı dayanıklı HEEP, ekip çizelgelerinin uygulanması safhasındaki belirsizlikleri dikkate alarak yapılan proaktif bir planlama yaklaşımıdır. Bu yaklaşımda esas amaç, aksaklıklara daha az maruz kalabilecek veya aksaklıklara maruz kalındığında onarılması daha kolay ekip eşlemelerinin üretilmesidir. Bu çalışmada söz konusu problem, yayılan gecikmelerin beklenen değerinin enazlanması ve aynı zamanda belirli bir seviyede maliyet-etkin bir çözümün muhafaza edilmesini amaçlayan Çift Amaçlı Genel Küme Bölüntüleme modeli olarak formüle edilmiştir. Çalışmada, eşlemeler oluşturulurken aksaklık bilgilerini içeren geçmiş veri setlerinin kullanılması önerilmiştir. Önerilen modelde dayanıklılığın bedeli, ε-yöntemi kullanılarak sınırlandırılmıştır. Çözüm yaklaşımı olarak, Dal-Sınır ağacının her bir düğümünde sütun oluşturma yöntemi uygulanan Dal-Ücret esaslı bir algoritma geliştirilmiştir. Elde edilen çözümlerin dayanıklılık performansının değerlendirilmesi için ise, bir kesikli olay benzetim modeli önerilmiştir. Ayrıca, geliştirilen model ve algoritmalar bir karar destek çerçevesinde kavramsal olarak birleştirilmiştir.Önerilen model ve çözüm yaklaşımının değerlendirilmesi için Türkiye'deki orta ölçekli bir havayolu şirketine ait gerçek veriler kullanılarak deneysel çalışmalar yapılmıştır. Deneysel çalışmalar sonucunda, önerilen yaklaşımın eniyi sonuçlar üretebildiği ve son karar öncesi birçok değişik senaryonun değerlendirilmesine imkân verecek ölçüde, kabul edilebilir işlem zamanlarında çözümlerin elde edilebildiği gözlenmiştir.

Robust Airline Crew Pairing Problem (ACPP) is considered in this dissertation. Robust ACPP is a proactive planning approach, which includes considering delays and disruptions that could happen in the operations. The main objective is to create crew pairings that are less prone to disruptions or easier to reschedule once disrupted. We model the problem as a Bi-Objective General Set Partitioning Problem to minimize the estimated propagated delay while at the same time maintaining a certain level of cost effective solution. We also exploit historical information on disruptions. In the model, the price of robustness is limited by using ε-constraint method. We develop a Branch-and-Price based solution algorithm in which column generation is applied at each node of the Branch-and-Bound tree. Also, a dicrete event simulation model (DAYPERSİM) is developed to assess the robustness performance of the solutions. Additionally, the proposed models and algorithms are incorporated into a decision support framework.A field-collected actual schedule dataset for a mid-scale Turkish airline, which operates short-haul domestic flights on a hub-and-spoke network, is used for the experiments in evaluating the model and the proposed solution method. The computational results show that on average the proposed methodology attains optimal solutions for the obtained dataset, and solution times are reasonable enough to conduct several different scenarios for a final decision.