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.