Pricing by local search in column generation for the airline crew pairing problem

Abstract

Havayolu ekip eşleme problemi uçuş çizelgesindeki her bir uçuşun kapsanmasını sağlayacak şekilde en az maliyetli ekip eşlemelerinin bulunmasıdır. Bu problem literatürde genel olarak küme bölüntüleme veya küme kapsama problemi olarak modellenmektedir. Olası eşlemelerin (kolonların) sayısındaki fazlalık nedeniyle bu modellerin kolon türetme yöntemiyle çözülmesi sıkça başvurulan bir yaklaşımdır. Havayolu ekip eşleme problemi için kolon türetme yönteminin ücretlendirme altproblemi uçuş serimi üzerinde çözülen çok takılı en kısa yol problemine karşılık gelmektedir. Uçuş serimi üzerinde çözülen çok takılı en kısa yol problemi NP-zor bir problemdir ve karmaşıklığı orta büyüklükteki çizelgeler için bile üsseldir.Bu çalışmada, havayolu ekip eşleme problemini, ücretlendirme altprobleminin karmaşıklığını azaltmak amacıyla melez bir ücretlendirme prosedürü kullanarak, kolon türetme yöntemiyle çözmekteyiz. Önerdiğimiz melez prosedürde, ücretlendirme altproblemi üç adımdan oluşmaktadır. İlk olarak, kısmi uçuş görev havuzu üzerinde uyguladığımız yerel arama yöntemi ile negatif azaltılmış maliyetli eşlemeler oluşturmaya çalışmaktayız. Yerel arama yönteminin böyle bir eşleme oluşturamadığı durumlarda çok takılı en kısa yol problemini kısmi uçuş görev serimi üzerinde çözmekte ve kısıtlı ana probleme eklemek üzere negatif azaltılmış maliyetli eşlemeler aramaktayız. Bu metodun da kısıtlı ana probleme eklenecek eşleme bulamadığı durumlarda çok takılı en kısa yol problemini uçuş serimi üzerinde çözmekteyiz. Benimsediğimiz melez yaklaşım sayesinde, çok takılı en kısa yol probleminin uçuş serimi üzerinde çözüldüğü kolon türetme iterasyonlarının sayısını ve iterasyon başına düşen çözüm süresi ile toplam çözüm süresini azaltmayı amaçlamaktayız. Yaklaşımımızın etkinliğini yerel bir havayolu şirketinden edindiğimiz örnek problemler üzerinde test etmekte ve sayısal sonuçlar sunmaktayız.

The airline crew pairing problem (ACP) is finding the least costly set of crew pairings so that each flight given in the flight schedule is covered. The ACP is traditionally modeled either as a set partitioning problem or a set covering problem. Due to the large number of possible pairings (columns), these models are usually solved by the column generation (CG) method. For the ACP, the pricing subproblem of the CG corresponds to a multi-label shortest path problem (MLSP) typically solved over a flight network. The MLSP over the fight network is NP-hard and it suffers from an exponential complexity even for moderate size flight networks. In order to overcome the complexity of the pricing subproblem, we propose a column generation method to solve the ACP, in which a hybrid pricing procedure is used. In this hybrid procedure, the pricing subproblem consists of three steps. First, we apply a local search mechanism on the partial duty period pool to construct pairings with negative reduced cost. In cases local search mechanism cannot find such a pairing, we execute a heuristic MLSP algorithm over the partial duty network to price out negative reduced cost pairings for the restricted master problem (RMP). If this method also fails, we solve the MLSP over the flight network. By adopting this hybrid approach, we aim to decrease the number of CG iterations where the MLSP is executed over the flight network, and reduce the computation time per iteration as well as the total computation time. We test the efficiency of our approach on real-life instances acquired from a local airline company, and present numerical results.