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

Aksoy, Nimet (2010) Pricing by local search in column generation for the airline crew pairing problem. [Thesis]

[thumbnail of NimetAksoy_381629.pdf] PDF

Download (1MB)


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 flight 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.
Item Type: Thesis
Uncontrolled Keywords: Crew pairing. -- Column generation. -- Pricing subproblem. -- Multi-label shortest path problem. -- Flight network. -- Duty network. -- Local search. -- Ekip eşleme. -- Kolon türetme. -- Ücretlendirme altproblemi. -- Çok takılı en kısa yol problemi. -- Uçuş serimi. -- Uçuş görev serimi. -- Yerel arama.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 09 May 2012 16:13
Last Modified: 26 Apr 2022 09:55

Actions (login required)

View Item
View Item