The aircraft sequencing problem with arrivals and departures

Abstract

This thesis investigates the Aircraft Sequencing Problem (ASP) with Arrivals and Departures. The ASP is the problem of sequencing the arriving and departing aircraft on a single nmway to minimize certain performance criteria. We focus on minimizing the total weighted delay. Both the theoretical aspects of the problem, and some practical issues are discussed. The static version of the problem is basically a scheduling problem with sequence dependent processing times and ready times, with the objective of minimizing total weighted delay. Exact algorithms for this problem are not fast enough for practical implementation. WP- give several algorithms that can be used both for the static and the dynamic versions of the problem. These algorithms are not exact solutions, however they are much faster than an exact algorithm and address some very important practical issues related to the ASP. Computational results from these algorithms are given. The computational results demonstrate that the potential benefits of using optimization in the sequencing of arrivals and departures in the Terminal Area are fairly significant. For example, the algorithm HWTW with 11,f PS= (0,0) reduces delays by 40% compared to FCFS. Certain fairness and safety issues are addressed as well. Acknowlegmets I would like to thank my advisor, Prof. Amedeo R. Odoni for his support during the past two years. This research was partially supported by the Federal Aviation Administration (FAA) under the project" Advanced Concepts for Collaborative Decision Making (CDM)," award number SA1603JB and by the Charles Stark Draper Laboratory Inc., under Contract Numnber DLH- 505328.