An Optimal Data-Splitting Algorithm for Aircraft Sequencing on Two Runways

Journal: Transportation Research Part C: Emerging Technologies

In this work, the researchers study the static aircraft sequencing and scheduling problem on a two-runway independent system for both an 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 requirements. This NP-hard problem is computationally harder than its single runway counterpart due to the presence of additional runway allocation decisions.

Recognizing the intractability of peak-traffic instances of this problem via a direct application of the MIP formulation, a variant of the data-splitting algorithm (DS-ASP) is proposed. The DS-ASP divides the given set of flights into several disjoint subsets, and then optimizes each of them using the underlying 0-1 MIP formulation, while ensuring the optimality of the entire set. Computational results show a significant reduction in average solution time as  compared to a direct use of a commercial solver and achieving optimality in all of the instances.

Capable of producing real-time solutions for various peak-traffic instances even with sequential implementation, its pleasingly parallel structure further enhances the efficiency and scalability of the proposed approach.