Pricing in column generation for a robust airline crew pairing problem

Abstract

Ekip eşleme problemi uçuş çizelgesindeki her bir uçuşun kapsanmasını sağlayacak şekilde en az maliyetli eşleme kümesinin bulunması problemidir. Bu çalışmada, dayanıklı ekip eşleme problemi ele alınmıştır. Bu problemde, seçilen eşlemeler olağan uçuşları kapsamakta ve operasyon sırasında tanıtılabilecek bazı ekstra uçuşların kapsanmasını da sağlamaktadır. Ekip eşleme problemi genellikle kolon türetme yöntemiyle çözülmektedir ve bu yöntemin alt problemi çok takılı en kısa yol problemi olmaktadır. Dayanıklı ekip eşleme problemi için Çoban [10] tarafından önerilmiş olan iki model bulunmaktadır ve çok takılı en kısa yol probleminde bu modellerin çözümü için bazı değişiklikler gerekmektedir. Ücretlendirme problemindeki bu değişiklikler, ilişkilendirilmiş takılar ve baskı yöntemleriyle beraber aktarılmıştır.Çok takılı en kısa yol probleminin karmaşıklığı, çizelgedeki uçuş (düğüm) sayısı arttıkça üssel bir şekilde artmaktadır. Bu durum iki yaklaşık ve bir pekin kural kullanılarak çözülmektedir. Ayrıca, çok takılı en kısa yol problemini çözmeden uygun bir eşleme bulabilmek için ara kolon havuzu oluşturulmuştur. Çok takılı en kısa yol problemini çözerken, işlenen düğüm üzerindeki yolları ilk olarak temizlemek için puan hesaplamaya dayalı olan yaklaşık kurallar kullanılmaktadır. En iyi çözüm yaklaşık kuralların kaba yapısından dolayı kaçırılabilir. Eğer yaklaşık kurallar kullanılarak amaç fonksiyonunu geliştirecek bir eşleme bulunamazsa, uygulanan kural pekin kural olarak değiştirilmektedir. Diğer bir yaklaşım, hem pekin hem de yaklaşık kuralların aynı iterasyonda kullanıldığı melez yöntemdir. Bu yöntemde de eniyi sonuç bulunabilmektedir. Yerel bir havayolu şirketinden alınan veriler doğrultusunda bu çözüm yaklaşımlarının sayısal sonuçları sunulmuştur.

The crew pairing problem is to find the least costly set of pairings so that each flight given in the flight schedule is covered. In this study, the robust crew pairing problem is considered. That is, the selected pairings cover the regular flights and also provide solutions to cover some extra flights which may be introduced into the flight schedule during the operation at a later point in time. The crew pairing problem is usually solved by column generation in which the pricing subproblem becomes a multi-label shortest path problem. For the robust crew pairing problem the multi-label shortest path problem requires some modifications to solve two column generation approaches proposed by Çoban [10]. These modifications of the pricing problem with associated labels and the domination rules are presented.The complexity of the multi-label shortest path problem grows exponentially as the number of flights (nodes) in the flight schedule increases. This curse of dimensionality is solved by using approximate and exact pruning rules. Also, a buffer column pool is formed as an intermediate step in order to find a negative reduced cost pairing without solving the multi-label shortest path problem at every iteration of the column generation algorithm. In the multi-label shortest path problem, the approximate rules based on the score-calculation are used for early pruning of the paths on the processed nodes. The optimal solution may be missed because of the coarse structure of the approximate rules. When a pairing that improves the objective function cannot be found by applying the approximate rules, we switch to the exact pruning. Another method is using a hybrid approach that applies both approximate and exact rules in the same iteration to find the optimal solution. The performance of our solution approach is demonstrated through a computational study by using actual data from a local airline.