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

作者：Ghoniem Ahmed^*; Farhadi Farbod

来源：Journal of the Operational Research Society, 2015, 66(10): 1717-1729.

DOI：10.1057/jors.2014.131

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

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.

• 出版日期2015-10