An Optimal Data-Splitting Algorithm for Aircraft Sequencing on a Single Runway

Journal: Annals of Operations Research

During peak-hours, busy airports face the challenge of turning aircraft around as quickly as possible, which includes sequencing their arrivals and departures with maximum efficiency, while respecting the required safety standards. This problem, termed the aircraft sequencing problem (ASP) has traditionally been hard to solve to optimality in real-time, even for flights over a one-hour planning horizon.

In this article, the researchers present a novel data-splitting algorithm to solve the ASP on a single runway with the objective of minimizing the total delay in the system, under segregated and mixed mode of runway operations. The problem is formulated as a 0–1 mixed integer program, taking into account several realistic constraints, including safety separation standards, wide time-windows, and constrained position shifting. Following a divide-and-conquer paradigm, the algorithm divides the given set of flights into several disjoint subsets, each of which is optimized using an underlying 0-1 MIP, and finally reconstructing the entire sequence to ensure optimality of the entire set.

While problem instances corresponding to peak traffic scenarios cannot be solved via a direct application of a commercial MIP solver or an existing state-of-the-art dynamic programming method, the proposed data-splitting algorithm efficiently solves such problems to optimality in real-time with nearly a 90% reduction in average computational time.