Abstract

This dissertation contributes to the ongoing national project concerning the \\emph{Next Generation Air Transportation System} (NextGen) that endeavors, in particular, to reshape the management of air traffic in the continental United States. Our work is part of this effort and mainly concerns modeling and algorithmic enhancements to the Airspace Planning and Collaborative Decision-Making Model (APCDM). First, we augment the APCDM to study an \\emph{Airspace Flow Program} (AFP) in the context of weather-related disruptions. The proposed model selects among alternative flight plans for the affected flights while simultaneously (a) integrating slot-exchange mechanisms induced by multiple Ground Delay Programs (GDPs) to permit airlines to improve flight efficiencies through a mediated bartering of assigned slots, and (b) considering issues related to sector workloads, airspace conflicts, as well as overall equity concerns among the involved airlines in regard to accepted slot trades and flight plans. More specifically, the APCDM is enhanced to include the following: \\begin{enumerate}[a.] \\item The revised model accommodates continuing flights, where some flight cannot depart until a prerequisite flight has arrived. Such a situation arises, for example, when the same aircraft will be used for the departing flight. \\item We model a slot-exchange mechanism to accommodate flights being involved in multiple trade offers, and to permit slot trades at multiple GDP airports (whence the flight connection constraints become especially relevant). We also model flight cancelations whereby, if a flight assigned to a particular slot is canceled, the corresponding vacated slot would be made available for use in the slot-exchange process. \\item Alternative equity concepts are presented, which more accurately reflect the measures used by the airlines. \\item A reduced variant of the APCDM, referred to as \\textbf{APCDM-Light}, is also developed. This model serves as a fast-running version of APCDM to be used for quick-turn analyses, where the level of modeling detail, as well as data requirements, are reduced to focus only on certain key elements of the problem. \\item As an alternative for handling large-scale instances of APCDM more effectively, we present a \\emph{sequential variable fixing heuristic} (SFH). The list of flights is first partitioned into suitable subsets. For the first subset, the corresponding decision variables are constrained to be binary-valued (which is the default for these decision variables), while the other variables are allowed to vary continuously between 0 and 1. If the resulting solution to this relaxed model is integral, the algorithm terminates. Otherwise, the binary variables are fixed to their currently prescribed values and another subset of variables is designated to be binary constrained. The process repeats until an integer solution is found or the heuristic encounters infeasibility. \\item We experiment with using the APCDM model in a \\emph{dynamic, rolling-horizon framework}, where we apply the model on some periodic basis (e.g., hourly), and where each sequential run of the model has certain flight plan selections that are fixed (such as flights that are already airborne), while we consider the selection among alternative flight plans for other imminent flights in a look-ahead horizon (e.g., two hours). \\end{enumerate} These enhancements allow us to significantly expand the functionality of the original APCDM model. We test the revised model and its variants using realistic data derived from the \\emph{Enhanced Traffic Management System} (ETMS) provided by the \\emph{Federal Aviation Administration} (FAA). One of the new equity methods, which is based on average delay per passenger (or weighted average delay per flight), turns out to be a particularly robust way to model equity considerations in conjunction with sector workloads, conflict resolution, and slot-exchanges. With this equity method, we were able to solve large problem instances (1,000 flights) within 30 seconds on average using a 1\\% optimality tolerance. The model also produced comparable solutions within about 20 seconds on average using the Sequential Fixing Heuristic (SFH). The actual solutions obtained for these largest problem instances were well within 1\\% of the best known solution. Furthermore, our computations revealed that APCDM-Light can be readily optimized to a 0.01\\% tolerance within about 5 seconds on average for the 1,000 flight problems. Thus, the augmented APCDM model offers a viable tool that can be used for tactical air traffic management purposes as an airspace flow program (particularly, APCDM-Light), as well as for strategic applications to study the impact of different types of trade restrictions, collaboration policies, equity concepts, and airspace sectorizations. The modeling of slot ownership in the APCDM motivates another problem: that of generating detoured flight plans that must arrive at a particular slot time under severe convective weather conditions. This leads to a particular class of network flow problems that seeks a shortest path, if it exists, between a source node and a destination node in a connected digraph $G(N,A)$, such that we arrive at the destination at a specified time while leaving the source no earlier than a lower bounding time, and where the availability of each network link is time-dependent in the sense that it can be traversed only during specified intervals of time. We refer to this problem as the \\emph{reverse time-restricted shortest path problem} (RTSP). We show that RTSP is NP-hard in general and propose a dynamic programming algorithm for finding an optimal solution in pseudo-polynomial time. Moreover, under a special regularity condition, we prove that the problem is polynomially solvable with a complexity of order $O(|N||A|)$. Computational results using real flight generation test cases as well as random simulated problems are presented to demonstrate the efficiency of the proposed solution procedures. The current airspace configuration consists of sectors that have evolved over time based on historical traffic flow patterns. \\citet{kopardekar_dyn_resect_2007} note that, given the current airspace configuration, some air traffic controller resources are likely under-utilized, and they also point out that the current configuration limits flexibility. Moreover, under the free-flight concept, which advocates a relaxation of waypoint traversals in favor of wind-optimized trajectories, the current airspace configuration will not likely be compatible with future air traffic flow patterns. Accordingly, one of the goals for the \\emph{NextGen Air Transportation System} includes redesigning the airspace to increase its capacity and flexibility. With this motivation, we present several methods for defining sectors within the \\emph{National Airspace System} (NAS) based on a measure of sector workload. Specifically, given a convex polygon in two-dimensions and a set of weighted grid points within the region encompassed by the polygon, we present several mixed-integer-programming-based algorithms to generate a plane (or line) bisecting the region such that the total weight distribution on either side of the plane is relatively balanced. This process generates two new polygons, which are in turn bisected until some target number of regions is reached. The motivation for these algorithms is to dynamically reconfigure airspace sectors to balance predicted air-traffic controller workload. We frame the problem in the context of airspace design, and then present and compare four algorithmic variants for solving these problems. We also discuss how to accommodate monitoring, conflict resolution, and inter-sector coordination workloads to appropriately define grid point weights and to conduct the partitioning process in this context. The proposed methodology is illustrated using a basic example to assess the overall effect of each algorithm and to provide insights into their relative computational efficiency and the quality of solutions produced. A particular competitive algorithmic variant is then used to configure a region of airspace over the U.S. using realistic flight data. The development of the APCDM is part of an ongoing \\emph{NextGen} research project, which envisages the sequential use of a variety of models pertaining to three tiers. The \\emph{Tier 1} models are conceived to be more strategic in scope and attempt to identify potential problematic areas, e.g., areas of congestion resulting from a severe convective weather system over a given time-frame, and provide aggregate measures of sector workloads and delays. The affected flow constrained areas (FCAs) highlighted by the results from these \\emph{Tier 1} models would then be analyzed by more detailed \\emph{Tier 2} models, such as APCDM, which consider more specific alternative flight plan trajectories through the different sectors along with related sector workload, aircraft conflict, and airline equity issues. Finally, \\emph{Tier 3} models are being developed to dynamically examine smaller-scaled, localized fast-response readjustments in air traffic flows within the time-frame of about an hour prior to departure (e.g., to take advantage of a break in the convective weather system). The APCDM is flexible, and perhaps unique, in that it can be used effectively in all three tiers. Moreover, as a strategic tool, analysts could use the APCDM to evaluate the suitability of potential airspace sectorization strategies, for example, as well as identify potential capacity shortfalls under any given sector configuration. Ph. D.