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

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.