Pricing in column generation for a robust airline crew pairing problem

Taş, Duygu (2008) Pricing in column generation for a robust airline crew pairing problem. [Thesis]

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: (Table of Contents)


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.

Item Type:Thesis
Uncontrolled Keywords:Scheduling. -- Robustness. -- Extra flights. -- Crew pairing. -- Column generation. -- Multi-label shortest path problem. -- Domination rules. -- Çizelgeleme. -- Dayanıklılık. -- Ekstra uçuşlar. -- Ekip eşleme. -- Kolon türetme. -- Çok takılı en kısa yol problemi. -- Baskı kuralları.
Subjects:T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
ID Code:13952
Deposited By:IC-Cataloging
Deposited On:13 May 2010 15:11
Last Modified:13 May 2010 15:11

Repository Staff Only: item control page