An optimal data-splitting algorithm for aircraft sequencing on a single runway

Abstract

During peak-hour busy airports have the challenge of turning aircraft around as quickly as possible, which includes sequencing their landings and take-offs with maximum efficiency, without sacrificing safety. This problem, termed aircraft sequencing problem (ASP) has traditionally been hard to solve optimally in real-time, even for flights over a one-hour planning window. In this article, we present a novel data-splitting algorithm to solve the ASP on a single runway with the objective to minimize the total delay in the system both under segregated and mixed mode of operation. 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 divide-and-conquer paradigm, the algorithm divides the given set of flights into several disjoint subsets, each of which is optimized using 0-1 MIP while ensuring the optimality of the entire set. One hour peak-traffic instances of this problem, which is NP-hard in general, are computationally difficult to solve with direct application of the commercial solver, as well as existing state-of-the-art dynamic programming method. Using our data-splitting algorithm, various randomly generated instances of the problem can be solved optimally in near real-time, with time savings of over 90%.