Search

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%. [ABSTRACT FROM AUTHOR]

Highlights • Exactly optimize the throughput of peak-traffic instances of ASP with CPS. • The first LP-based branch-and-cut approach to optimally solve this problem. • More flexible than existing state-of-the-art dynamic programming-based solutions. • Algorithm with potential to be included in the arrival-departure management systems. Abstract In this research, we present a data-splitting algorithm to optimally solve the aircraft sequencing problem (ASP) on a single runway under both segregated and mixed-mode of operation. This problem is formulated as a 0–1 mixed-integer program (MIP), taking into account several realistic constraints, including safety separation standards, wide time-windows, and constrained position shifting, with the objective of maximizing the total throughput. Varied scenarios of large scale realistic instances of this problem, which is NP-hard in general, are computationally difficult to solve with the direct use of commercial solver as well as existing state-of-the-art dynamic programming method. The design of the algorithm is based on a recently introduced data-splitting algorithm which uses the divide-and-conquer paradigm, wherein the given set of flights is divided into several disjoint subsets, each of which is optimized using 0–1 MIP while ensuring the optimality of the entire set. Computational results show that the difficult instances can be solved in real-time and the solution is efficient in comparison to the commercial solver and dynamic programming, using both sequential, as well as parallel, implementation of this pleasingly parallel algorithm. [ABSTRACT FROM AUTHOR]