A Branch-and-Price Algorithm for the Robust Airline Crew Pairing Problem

Authors : Bülent SOYKAN, Serpil EROL

Pages : 37-74

Doi:10.17134/sbd.88400

View : 18 | Download : 8

Publication Date : 2014-03-01

Article Type : Research Paper

Abstract :Aksaklıklara Karşı Dayanıklı Ekip Eşleme Problemi, klasik ekip eşleme probleminin çizelgelerin uygulanması safhasında meydana gelebilecek gecikme ve aksaklıkları dikkate alarak yapılan proaktif bir planlama yaklaşımı ile ele alınmış halidir. Yaklaşımda esas amaç, aksaklıklara daha az maruz kalabilecek veya aksaklıklara maruz kalındığı zaman tekrar çizelgelenmesi daha kolay ekip eşlemelerinin üretilmesidir. Söz konusu problem, yayılan gecikmelerin beklenen değerinin enazlanması ve aynı zamanda maliyet-etkin bir çözümün muhafaza edilmesini amaçlayan Çift-Amaçlı Genel Küme Kapsama modeli olarak formüle edilmiştir. Çalışmada, aksaklık bilgilerini içeren geçmiş veri setlerinin kullanılması ve bu veri setinin iki alt parçaya ayrılması önerilmiştir. Veri setinin birinci parçasının yayılan gecikmelerin beklenen değerinin eniyilenmesinde kullanılması öngörülmüş ve dayanıklılığın bedeli, ε-yöntemi kullanılarak sınırlandırılmaya çalışı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 algoritması esaslı bir algoritma geliştirilmiştir. Önerilen model ve çözüm yaklaşımının değerlendirilmesi için yapılan deneylerde; Türkiye’de yerleşik, ana dağıtım üssü-kenar üs uçuş ağ yapısını uygulayan, küçük ölçekli bir havayolu şirketine ait gerçek veriler kullanılmıştır. Ayrıca, geçmiş veri setinin ikinci parçası girdi olarak kullanılarak elde edilen eniyileme sonuçlarının geçerlemesi ve çözümlerin dayanıklılığının Yazışma Adresi: Kara Harp Okulu, Savunma Bilimleri Enstitüsü, Harekât Araştırması ABD, Ankara, [email protected], Gazi Üniversitesi, Mühendislik Fakültesi, Endüstri Müh. Böl., Ankara.belirlenmesi için çeşitli benzetim deneyleri yapılmıştır. Gerçek veri seti kullanılarak elde edilen deneysel sonuçlar umut verici olup önerilen yaklaşımın ortalamada eniyi sonuçlar üretebildiği ve son karar öncesi birçok değişik senaryonun değerlendirilmesine imkân verecek ölçüde, kabul edilebilir çözüm zamanlarında çözümlerin elde edilebildiği gözlenmiştir.
Keywords : Dayanıklı Ekip Eşleme Eniyilemesi, Dal Ücret Algoritması, Sütun Oluşturma Yöntemi, Dayanıklılık, Gecikme Yayılımı