Optimal algorithms for sequencing of aircraft arrivals and departures

In airport operations, runways are scarce and expensive resources and constitute a key bottleneck. Further, capacity on the runway is limited by the safety separation between flights, thereby providing a huge opportunity to optimize the aircraft sequencing and scheduling operations on the runways, commonly referred to in the literature as the aircraft sequencing problem (ASP). However, ASP is an NP-hard problem and sequencing and scheduling decisions have to be made in real-time. Thus, motivated by the challenge posed by this very important problem, in this dissertation comprising of four essays pertaining to four different variants of ASP, models and algorithms are proposed to enable optimal sequencing in real-time. This thesis considers the ASP on a single runway, as well as, a dualindependent runway system under both segregated and mixed mode of operations. In each of the four essays, ASP is formulated as a 0–1 mixed-integer program while taking into account several realistic constraints including airline equity considerations, implemented using constrained position shifting. The first essay addresses the ASP on a single runway with the objective of minimizing the total delay in the system. Observing the computational difficulty in getting real-time optimal solutions of various large-scale realistic instances of this problem by directly employing the MIP model, a novel data-splitting algorithm is proposed, the first method to solve these instances in real-time. Under the data-splitting algorithmic framework, which is also pleasingly parallel, the given set of flights is divided into several subsets, each of which is then optimized using 0–1 MIP. The proposed algorithm is based on a divide-andconquer strategy, and novelty is introduced in both dividing and solving so as to ensure the optimality of the entire set. Detailed algorithmic insights and analysis to validate the rationale, proof of optimality, and strength of the proposed method, including a combinatorial exposition of the estimated reduction in the search space, are also presented. Computations demonstrate that the average solution time can be reduced significantly (by as much as 99%) over direct solution by a commercial solver, while achieving the optimal solution in real-time for nearly all the instances. The second essay considers the ASP with the objective of maximizing the total throughput of a runway. This problem enjoys a separable structure under the given constraints, thereby attracting a state-of-the-art algorithm based on dynamic programming; however, this algorithm can handle arrival traffic operations in real-time, but may not handle mixed mode of operations and some other set of problem scenarios with the same efficiency. Recognizing this, the data-splitting algorithm is tailored to solve this problem which also exploits its separability property. Further, a novel algorithmic enhancement procedure to further reduce the solution time, and a framework to split the flight dataset at multiple points to handle very large-sized instances, are presented. Computational results show that the difficult instances can be optimally solved in real-time under various scenarios, while achieving significant reduction in computational time (by as much as 99%) over direct use of the commercial solver. Further reduction in computational time is also demonstrated using the parallelized implementation. The third essay considers the ASP on a dual-independent runway system with the objective of maximizing the total throughput of the runways. This problem is computationally harder than single runway scheduling due to the additional runway allocation decision; moreover, unlike maximizing throughput on a single runway, it does not possess any special separable structure. The lack of separability precludes the use of dynamic programming. Recognizing that large scale realistic instances of this problem cannot be solved optimally in real or nearreal time by directly employing the MIP formulation either, the data-splitting algorithm is adapted to solve the problem. In addition, various algorithmic improvement procedures and a framework to split the flight dataset at multiple points, are proposed. Computational results show a significant reduction in average solution time (by as much as 92%) compared to direct use of commercial solver, while achieving optimality in all of the instances. The results indicate that sequential implementation of the algorithm solves all the instances in real or near-real time for the maximum position shifting (MPS) parameter of one, whereas the parallelized implementation solves nearly all of the instances in real or near-real time for MPS parameter value of up to two. The fourth essay addresses the ASP over the entire terminal maneuvering area (TMA) for a single runway operating in segregated and mixed-mode scenario. In contrast with existing approaches that only consider the runway as a bottleneck, this approach optimizes flight sequences and schedules by taking into account the configuration and associated constraints of the entire TMA region. Computational results on illustrative examples show that significant reduction in delay can be achieved over the sequencing policy which only considers safety separation at runway.Doctor of Philosoph