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

Document Type

Article

Publication Title

Journal of the Operational Research Society

Publication Date

10-7-2015

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.

Volume

66

Issue

10

First Page

1717

Last Page

1729

DOI

10.1057/jors.2014.131

ISSN

01605682

E-ISSN

14769360

Link to Full Text

Share

 
COinS