A column generation approach for aircraft sequencing problems: A computational study
Journal of the Operational Research Society
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.
Ghoniem, A., & Farhadi, F. (2015). A column generation approach for aircraft sequencing problems: A computational study. Journal of the Operational Research Society, 66 (10), 1717-1729. https://doi.org/10.1057/jors.2014.131