A column generation approach for aircraft sequencing problems: a computational study

Abstract

This paper investigates the computational tractability of aircraft sequencing problems over multiple runways under mixed mode operations, contrasting an enhanced mixed-integer programme (MIP) and an accelerated column generation approach. First, we examine the benefit of augmenting a base MIP with valid inequalities, preprocessing routines, and symmetry-defeating hierarchical constraints in order to improve the performance of branch-and-bound (B&B)/cut techniques as implemented in commercial solvers. Second, we alternatively reformulate the problem as a set partitioning model that prompts the development of a specialized column generation approach. The latter is accelerated by incorporating an interior point dual stabilization scheme and a complementary column generation routine. Empirical results using a set of new, computationally challenging instances and classical instances in the OR Library reveal the potential and limitations of the two methodologies.

Keywords:

• runway scheduling
• mixed-integer programming
• column generation
• stabilization techniques
• symmetry-defeating constraints

Acknowledgements

This research has been supported by Qatar National Research Fund under Grant Number NPRP 09-253-2-103. We also would like to thank five anonymous reviewers for their helpful comments.