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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abela J, Abramson D, Krishnamoorthy M, De Silva A and Mills G (1993). Computing optimal schedules for landing aircraft. In Sutton, DJ, Pearce, EM and Cousins EA. Proceedings of the 12th National ASOR Conference, Australian Society for Operations Research; Adelaide, Australia, pp 71–90.
van den Akker JM, Hoogeveen JA and van Kempen JW (2012). Using column generation to solve parallel machine scheduling problems with minmax objective functions. Journal of Scheduling 15 (6): 801–810.
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWF and Vance PH (1998). Branch-and-price: column generation for solving huge integer programs. Operations Research 46 (3): 316–329.
Beasley JE, Krishnamoorthy M, Sharaiha YM and Abramson D (2000). Scheduling aircraft landings—The static case. Transportation Science 34 (2): 180–197.
Bennell JA, Mesgarpour M and Potts CN (2011). Airport runway scheduling. 4OR: Quarterly Journal of Operations Research 9 (2): 115–138.
Chen Z-L and Powell WB (1999). Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing 11 (1): 78–94.
de Carvalho JMV (2005). Using extra dual cuts to accelerate column generation. INFORMS Journal on Computing 17 (2): 175–182.
Dror M (1994). Note on the complexity of the shortest path models for column generation in VRPTW. Operations Research 42 (5): 977–979.
du Merle O, Villeneuve D, Desrosiers J and Hansen P (1999). Stabilized column generation. Discrete Mathematics 194 (1–3): 229–237.
Ernst AT, Krishnamoorthy M and Storer RH (1999). Heuristic and exact algorithms for scheduling aircraft landings. Networks 34 (3): 229–241.
Farhadi F, Ghoniem A and Al-Salem A (2014). Runway capacity management – an empirical study with application to Doha International Airport. Transportation Research Part E 68: 53–63.
Ghoniem A and Sherali HD (2009). Complementary column generation and bounding approaches for set partitioning formulations. Optimization Letters 3 (1): 123–136.
Ghoniem A and Sherali HD (2010). Models and algorithms for the scheduling of a doubles tennis training tournament. Journal of the Operational Research Society 61 (5): 723–731.
Ghoniem A and Sherali HD (2011). Set partitioning and packing versus assignment formulations for subassembly matching problems. Journal of the Operational Research Society 62 (11): 2023–2033.
Ghoniem A, Sherali HD and Baik H (2014). Enhanced models for a mixed arrival-departure aircraft sequencing problem. INFORMS Journal on Computing 26 (3): 514–530.
Gondzio J, González-Brevis P and Munari P (2013). New developments in the primal-dual column generation technique. European Journal of Operational Research 224 (1): 41–51.
Lübbecke ME and Desrosiers J (2005). Selected topics in column generation. Operations Research 53 (6): 1007–1023.
Neame PJ (1999). Nonsmooth dual methods in integer programming. PhD Thesis, University of Melbourne, Victoria, Australia.
Pinol H and Beasley JE (2006). Scatter search and bionomic algorithms for the aircraft landing problem. European Journal of Operational Research 171 (2): 439–462.
Rousseau L-M, Gendreau M and Feillet D (2007). Interior point stabilization for column generation. Operations Research Letters 35 (5): 660–668.
Sherali HD and Adams WP (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal of Discrete Mathematics 3 (3): 411–430.
Sherali HD and Ghoniem A (2009). Joint vehicle assembly-routing problems: An integrated modeling and optimization approach. Networks 53 (3): 249–265.
Sherali HD and Smith JC (2001). Improving discrete model representations via symmetry considerations. Management Science 47 (10): 1396–1407.
Subramanian S and Sherali HD (2008). An effective deflected subgradient optimization scheme for implementing column generation for large-scale airline crew scheduling problems. INFORMS Journal on Computing 20 (4): 565–578.
Wen M, Larsen J and Clausen J (2005). An exact algorithm for aircraft landing problem. IMM-Technical Report-2005–12, Informatics and Mathematical Modelling, Technical University of Denmark.
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.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ghoniem, A., Farhadi, F. A column generation approach for aircraft sequencing problems: a computational study. J Oper Res Soc 66, 1717–1729 (2015). https://doi.org/10.1057/jors.2014.131
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2014.131