Optimization Online


Solving the integrated airline recovery problem using column-and-row generation

Stephen J Maher (stephen.maher***at***unsw.edu.au)

Abstract: Airline recovery presents very large and difficult problems requiring high quality solutions within very short time limits. To improve computational performance, the complete airline recovery problem is generally formulated as a series of sequential stages. While the sequential approach greatly simplifies the complete recovery problem, there is no guarantee of global optimality or solution quality. To address this, there has been increasing interest in the development of efficient solution techniques to solve an integrated recovery problem. In this paper, an integrated airline recovery problem is proposed by integrating the schedule, crew and aircraft recovery stages. To achieve short runtimes and high quality solutions, this problem is solved using column-and-row generation. Column-and-row generation achieves an improvement in solution runtimes by reducing the problem size and thereby achieving a faster execution of each LP solve. Further, the results demonstrate that a good upper bound achieved early in the solution process, indicating an improved solution quality with the early termination of the algorithm. This paper also details the integration of the row generation procedure with branch-and-price, which is used to achieve integral optimal solutions. The benefits of applying column-and-row generation to solve the integrated recovery problem are demonstrated with a comparison to a standard column generation technique.

Keywords: airline recovery, column generation, row generation

Category 1: Applications -- OR and Management Sciences (Airline Optimization )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: University of New South Wales, Sydney, NSW, Australia. December 2012.

Download: [PDF]

Entry Submitted: 12/03/2012
Entry Accepted: 12/03/2012
Entry Last Modified: 08/22/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society