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

Bülent SOYKAN; Serpil EROL

Article Details

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

Authors:

Bülent SOYKAN | Serpil EROL

Publisher:

Millî Savunma Üniversitesi

Journal:

The Journal of Defense Sciences 2014 Vol.13 Issue 1, pp.37-74

Document Type:

Article

Publication Date:

2/2014

Document Language:

Turkish

Document ID (Org No.):

2000569360

Frequency:

Bi-Annual

eISSN:

2148-1776

pISSN:

1303-6831

Abstract:

 

Robust Airline Crew Pairing Problem 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 Covering Problem to minimize the estimated propagated delay while at the same time maintaining a cost effective solution. We exploit historical information on disruptions and separate dataset into two subsets. We optimize the expected propagated delays based on the first portion of the dataset, and limit the price of robustness using ε-constraint method. We develop a branch-and-price based solution algorithm that column generation is applied at each node of the branch-and-bound tree. A ﬁeld-collected actual schedule dataset for a small-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. We also conduct simulation experiments to verify optimization results and to determine the robustness of the obtained solutions, where the second part of the historical data is used as an input. The computational results obtained are encouraging, which 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.

 

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, bsoyk001@odu.edu.Prof, 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.

Article Details

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

Authors: Bülent SOYKAN | Serpil EROL

Publisher: Millî Savunma Üniversitesi

Journal: The Journal of Defense Sciences 2014 Vol.13 Issue 1, pp.37-74

Document Type: Article

Publication Date: 2/2014

Document Language: Turkish

Document ID (Org No.): 2000569360

Frequency: Bi-Annual

eISSN: 2148-1776

pISSN: 1303-6831

Issues

Authors:

Bülent SOYKAN | Serpil EROL

Publisher:

Millî Savunma Üniversitesi

Journal:

The Journal of Defense Sciences 2014 Vol.13 Issue 1, pp.37-74

Document Type:

Article

Publication Date:

2/2014

Document Language:

Turkish

Document ID (Org No.):

2000569360

Frequency:

Bi-Annual

eISSN:

2148-1776

pISSN:

1303-6831