Stabilised branch-and-check method for optimising multi-runway aircraft landing problem modelled through stochastic programming with learning-driven arrival time predictions

Abstract

The continuous growth in air traffic demand has strained the capacity of many hub airports. Effective runway operations are essential for optimising the utilisation of existing runways, and one of the key tasks is to manage runway operations under uncertainty. This paper examines the multi-runway aircraft landing problem (MALP) under arrival time uncertainty at hub airports with a multi-runway system, aiming to devise efficient and environmentally friendly aircraft landing operations. We model this problem using stochastic programming (SP) with a two-stage decision framework. With the support of advanced aviation technologies, air traffic control can typically make aircraft sequencing decisions based on precisely predicted arrival times. Therefore, we incorporate aircraft sequencing decisions into the second stage of the SP model. In the first stage, we assign aircraft to runways. In the second stage, we make aircraft sequencing and scheduling decisions after the arrival times are revealed. Given that the second-stage problem includes both integer and continuous variables, the model is termed the SP model with mixed-integer recourse (SP-MIR). We propose an optimisation-enhanced learning-driven scenario generation (OLSG) method, which employs machine learning techniques to estimate the distribution of unknown parameters, construct scenarios, and utilise the p-median problem to sample representative scenarios for input into the SP-MIR model. To efficiently solve the SP-MIR model, we present a novel exact decomposition approach, referred to as the stabilised branch-and-check (SBAC) method. This approach decomposes the original problem into a stabilised master problem and subproblems, wherein the master problem is stabilised around a designated stability centre to facilitate the generation of strong Benders cuts. The incorporated algorithmic enhancements further improve computational performance in solving both the stabilised master problem and subproblems. Our numerical experiment results demonstrate that the proposed SP-MIR model and OLSG method can enhance operational efficiency and reduce environmental impact in multi-runway operations for actual scenarios and real-world implementation. The results of scalability analysis indicate that the SBAC method and algorithmic enhancements achieve significant improvement in CPU time compared to well-known benchmark methods from the literature.