Slot-Exchange Mechanisms and Weather-Based Rerouting within an Airspace Planning and Collaborative Decision-Making Model

TR Number
Journal Title
Journal ISSN
Volume Title
Virginia Tech

We develop and evaluate two significant modeling concepts within the context of a large-scale Airspace Planning and Collaborative Decision-Making Model (APCDM) and, thereby, enhance its current functionality in support of both strategic and tactical level flight assessments. The first major concept is a new severe weather-modeling paradigm that can be used to assess existing tactical en route flight plan strategies such as the Flight Management System (FMS) as well as to provide rerouting strategies. The second major concept concerns modeling the mediated bartering of slot exchanges involving airline trade offers for arrival/departure slots at an arrival airport that is affected by the Ground Delay Program (GDP), while simultaneously considering issues related to sector workloads, airspace conflicts, as well as overall equity concerns among the airlines. This research effort is part of an $11.5B, 10-year, Federal Aviation Administration (FAA)-sponsored program to increase the U.S. National Airspace (NAS) capacity by 30 percent by the year 2010.

Our innovative contributions of this research with respect to the severe weather rerouting include (a) the concept of "Probability-Nets" and the development of discretized representations of various weather phenomena that affect aviation operations; (b) the integration of readily accessible severe weather probabilities from existing weather forecast data provided by the National Weather Service (NWS); (c) the generation of flight plans that circumvent severe weather phenomena with specified probability levels, and (d) a probabilistic delay assessment methodology for evaluating planned flight routes that might encounter potentially disruptive weather along its trajectory. Given a fixed set of reporting stations from the CONUS Model Output Statistics (MOS), we begin by constructing weather-specific probability-nets that are dynamic with respect to time and space. Essential to the construction of the probability-nets are the point-by-point forecast probabilities associated with MOS reporting sites throughout the United States. Connections between the MOS reporting sites form the strands within the probability-nets, and are constructed based upon a user-defined adjacency threshold, which is defined as the maximum allowable great circle distance between any such pair of sites. When a flight plan traverses through a probability-net, we extract probability data corresponding to the points where the flight plan and the probability-net strand(s) intersect. The ability to quickly extract this trajectory-related probability data is critical to our weather-based rerouting concepts and the derived expected delay and related cost computations in support of the decision-making process.

Next, we consider the superimposition of a flight-trajectory-grid network upon the probability-nets. Using the U.S. Navigational Aids (Navaids) as the network nodes, we develop an approach to generate flight plans that can circumvent severe weather phenomena with specified probability levels based on determining restricted, time-dependent shortest paths between the origin and destination airports. By generating alternative flight plans pertaining to specified threshold strand probabilities, we prescribe a methodology for computing appropriate expected weather delays and related disruption factors for inclusion within the APCDM model.

We conclude our severe weather-modeling research by conducting an economic benefit analysis using a k-means clustering mechanism in concert with our delay assessment methodology in order to evaluate delay costs and system disruptions associated with variations in probability-net refinement-based information. As a flight passes through the probability-net(s), we can generate a probability-footprint that acts as a record of the strand intersections and the associated probabilities from origin to destination. A flight plan's probability-footprint will differ for each level of data refinement, from whence we construct route-dependent scenarios and, subsequently, compute expected weather delay costs for each scenario for comparative purposes.

Our second major contribution is the development of a novel slot-exchange modeling concept within the APCDM model that incorporates various practical issues pertaining to the Ground Delay Program (GDP), a principal feature in the FAA's adoption of the Collaborative Decision-Making (CDM) paradigm. The key ideas introduced here include innovative model formulations and several new equity concepts that examine the impact of "at-least, at-most" trade offers on the entire mix of resulting flight plans from respective origins to destinations, while focusing on achieving defined measures of "fairness" with respect to the selected slot exchanges. The idea is to permit airlines to barter assigned slots at airports affected by the Ground Delay Program to their mutual advantage, with the FAA acting as a mediator, while being cognizant of the overall effect of the resulting mix of flight plans on air traffic control sector workloads, collision risk and safety, and equity considerations.

We start by developing two separate slot-exchange approaches. The first consists of an external approach in which we formulate a model for generating a set of package-deals, where each package-deal represents a potential slot-exchange solution. These package-deals are then embedded within the APCDM model. We further tighten the model representation using maximal clique cover-based cuts that relate to the joint compatibility among the individual package-deals. The second approach significantly improves the overall model efficiency by automatically generating package-deals as required within the APCDM model itself. The model output prescribes a set of equitable flight plans based on admissible trades and exchanges of assigned slots, which are in addition conformant with sector workload capabilities and conflict risk restrictions. The net reduction in passenger-minutes of delay for each airline is the primary metric used to assess and compare model solutions. Appropriate constraints are included in the model to ensure that the generated slot exchanges induce nonnegative values of this realized net reduction for each airline.

In keeping with the spirit of the FAA's CDM initiative, we next propose four alternative equity methods that are predicated on different specified performance ratios and related efficiency functions. These four methods respectively address equity with respect to slot-exchange-related measures such as total average delay, net delay savings, proportion of acceptable moves, and suitable value function realizations.

For our computational experiments, we constructed several scenarios using real data obtained from the FAA based on the Enhanced Traffic Management System (ETMS) flight information pertaining to the Miami and Jacksonville Air Route Traffic Control Centers (ARTCC). Through our experimentation, we provide insights into the effect of the different proposed modeling concepts and study the sensitivity with respect to certain key parameters. In particular, we compare the alternative proposed equity formulations by evaluating their corresponding slot-exchange solutions with respect to the net reduction in passenger-minutes of delay for each airline. Additionally, we evaluate and compare the computational-effort performance, under both time limits and optimality thresholds, for each equity method in order to assess the efficiency of the model. The four slot-exchange-based equity formulations, in conjunction with the internal slot-exchange mechanisms, demonstrate significant net savings in computational effort ranging from 25% to 86% over the original APCDM model equity formulation.

The model has been implemented using Microsoft Visual C++ and evaluated using a C++ interface with CPLEX 9.0. The overall results indicate that the proposed modeling concepts offer viable tools that can be used by the FAA in a timely fashion for both tactical purposes, as well as for exploring various strategic issues such as air traffic control policy evaluations; dynamic airspace resectorization strategies as a function of severe weather probabilities; and flight plan generation in response to various disruption scenarios.

Mixed-Integer Programming, Ground Delay Program, National Airspace, Trade Restrictions, Slot Offer Network, Airline Equity, Slot Exchanges, Probability-Nets, Air Traffic Control, Air Traffic Management, Collaborative Decision-Making