Solving A Robust Airline Crew Pairing Problem With Column Generation

Ibrahim Muter, S. Ilker Birbil, Kerem Bulbul, Guvenc Sahin, Duygu Tas, Dilek Tuzun, Husnu Yenigun

Research output: Contribution to journalArticle

29 Citations (Scopus)

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 difficult 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 local airlines in Turkey.
Original languageEnglish
Pages (from-to)815-830
JournalComputers and Operations Research
Volume40
Issue number3
DOIs
Publication statusPublished - 2013

Fingerprint

Column Generation
Pairing
Robustness
Recovery
Mathematical programming
Labels
Set Covering
Shortest Path Problem
Column generation
Airlines
Complications
Mathematical Programming
Computational Experiments
Pricing
Programming Model
Schedule
Costs
Cover
Mathematical Model
Experiments

Cite this

Muter, I., Birbil, S. I., Bulbul, K., Sahin, G., Tas, D., Tuzun, D., & Yenigun, H. (2013). Solving A Robust Airline Crew Pairing Problem With Column Generation. Computers and Operations Research, 40(3), 815-830. https://doi.org/10.1016/j.cor.2010.11.005

Solving A Robust Airline Crew Pairing Problem With Column Generation. / Muter, Ibrahim; Birbil, S. Ilker; Bulbul, Kerem; Sahin, Guvenc; Tas, Duygu ; Tuzun, Dilek ; Yenigun, Husnu.

In: Computers and Operations Research, Vol. 40, No. 3, 2013, p. 815-830.

Research output: Contribution to journalArticle

Muter, I, Birbil, SI, Bulbul, K, Sahin, G, Tas, D, Tuzun, D & Yenigun, H 2013, 'Solving A Robust Airline Crew Pairing Problem With Column Generation', Computers and Operations Research, vol. 40, no. 3, pp. 815-830. https://doi.org/10.1016/j.cor.2010.11.005
Muter, Ibrahim ; Birbil, S. Ilker ; Bulbul, Kerem ; Sahin, Guvenc ; Tas, Duygu ; Tuzun, Dilek ; Yenigun, Husnu. / Solving A Robust Airline Crew Pairing Problem With Column Generation. In: Computers and Operations Research. 2013 ; Vol. 40, No. 3. pp. 815-830.
@article{6bbeaa3f2f5e4ac99d2906744cdabcb7,
title = "Solving A Robust Airline Crew Pairing Problem With Column Generation",
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 difficult 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 local airlines in Turkey.",
author = "Ibrahim Muter and Birbil, {S. Ilker} and Kerem Bulbul and Guvenc Sahin and Duygu Tas and Dilek Tuzun and Husnu Yenigun",
year = "2013",
doi = "10.1016/j.cor.2010.11.005",
language = "English",
volume = "40",
pages = "815--830",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier",
number = "3",

}

TY - JOUR

T1 - Solving A Robust Airline Crew Pairing Problem With Column Generation

AU - Muter, Ibrahim

AU - Birbil, S. Ilker

AU - Bulbul, Kerem

AU - Sahin, Guvenc

AU - Tas, Duygu

AU - Tuzun, Dilek

AU - Yenigun, Husnu

PY - 2013

Y1 - 2013

N2 - 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 difficult 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 local airlines in Turkey.

AB - 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 difficult 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 local airlines in Turkey.

UR - https://doi.org/10.1016/j.cor.2010.11.005

U2 - 10.1016/j.cor.2010.11.005

DO - 10.1016/j.cor.2010.11.005

M3 - Article

VL - 40

SP - 815

EP - 830

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 3

ER -