title   
  

Solving a robust airline crew pairing problem with column generation

Muter, İbrahim and Birbil, Ş. İlker and Bülbül, Kerem and Şahin, Güvenç and Yenigün, Hüsnü and Taş, Duygu and Tüzün, Dilek (2010) Solving a robust airline crew pairing problem with column generation. (Accepted/In Press)

WarningThere is a more recent version of this item available.

[img]
Preview
PDF (This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
361Kb

Official URL: http://dx.doi.org/10.1016/j.cor.2010.11.005

Abstract

In this study, we solve a robust version of the airline crew pairing problem. Our concept of robustness was partially shaped during our discussions with small local airlines in Turkey which may have to add a set of extra flights into their schedule at short notice during operation. Thus, robustness in this case is related to the ability of accommodating these extra flights at the time of operation by disrupting the original plans as minimally as possible. We focus on the crew pairing aspect of robustness and prescribe that the planned crew pairings incorporate a number of predefined recovery solutions for each potential extra flight. These solutions are implemented only if necessary for recovery purposes and involve either inserting an extra flight into an existing pairing or partially swapping the flights in two existing pairings in order to cover an extra flight. The resulting mathematical programming model follows the conventional set covering formulation of the airline crew pairing problem typically solved by column generation with an additional complication. The model includes constraints that depend on the columns due to the robustness consideration and grows not only column-wise but also row-wise as new columns are generated. To solve this dicult model, we propose a row and column generation approach. This approach requires a set of modifications to the multi-label shortest path problem for pricing out new columns (pairings) and various mechanisms to handle the simultaneous increase in the number of rows and columns in the restricted master problem during column generation. We conduct computational experiments on a set of real instances compiled from a local airline in Turkey.

Item Type:Article
Uncontrolled Keywords:Airline crew scheduling; robust crew pairing; row and column generation; multi-label shortest path
Subjects:Q Science > Q Science (General)
T Technology > T Technology (General)
ID Code:15044
Deposited By:Kerem Bülbül
Deposited On:05 Nov 2010 16:13
Last Modified:05 Dec 2012 16:23

Available Versions of this Item

Repository Staff Only: item control page