An optimal data-splitting algorithm for aircraft sequencing on two runways

Abstract

We study the static aircraft sequencing and scheduling problem (during peak hour) on a two independent runway system both under arrivals only and mixed mode of operations. This problem is formulated as a 0–1 mixed-integer program with the objective of maximizing the total throughput of both runways, taking into account several realistic constraints including safety separation standards, wide time-windows, and constrained position shifting. This NP-hard problem is computationally harder than its single runway counterpart due to the additional runway allocation decisions. Recognising the intractability of peak-traffic instances of this problem by direct application of the MIP formulation, a novel application of data-splitting algorithm (DS-ASP) is proposed to the case of two runways scenario. DS-ASP divides the given set of flights into several disjoint subsets, and then optimises each of them using 0–1 MIP while ensuring the optimality of the entire set. Computational results show a significant reduction in average solution time (by more than 92% in some scenarios) compared to direct use of a commercial solver while achieving optimality in all of the instances. Capable of producing real-time solutions for various peak-traffic instances even with sequential implementation, pleasingly parallel structure further enhances its efficiency and scalability.