Latest revision as of 22:19, 1 February 2021

Abstract

network queuing model of the National Airspace System has been developed to support research into a strategic air traffic flow management capability. One of the challenges in the execution of the model is the size of the network – the computing resources required when modeling the entire United States are immense. As a way to reduce the network size, we investigate route clustering, i.e., grouping similar routes to reduce the number of paths between two airports. Clustering routes comes at a cost: as the number of clusters falls, the with-in cluster variability rises, and the solution quality is diminished. A trade-off curve for solution quality vs. cluster variability is developed for a sample problem involving seven major airports. I. Introduction/Background A prototype capability for strategic air traffic flow management is undergoing research and development. The capability, called Flow Contingency Management (FCM), will supply automated decision support for what currently is a mostly manual process. 1 It is recognized that strategic decisions made with a 2- to 24-hour time horizon will likely improve air traffic flows in the National Airspace System (NAS) by averting large-scale traffic congestion due to weather. The Next-Generation Air Transportation System (NextGen) mid-term concept reflects the need for this type of capability. Basic functionality has been developed for the prototype, including the representation of weather and traffic forecasts, and the integration of the two forecasts for predictions of significant impact. At the operative look-ahead times, there is significant uncertainty in the forecasts of both weather and traffic and, therefore, it is not appropriate to represent traffic at the level of individual flights. Rather, an aggregate model has been developed whereby traffic is represented as flows (an undifferentiated count of flights progressing in quarter-hour steps) in a queuing network. An initial formulation of such a model uses historical aircraft routings, one-day-prior filed flight routes, and “dayof” filed and predicted counts as input to a regression model to create the demand on a network of routes between airports. In the network, routes are represented by sequences of airspace sectors, 5 demand is expressed as the fraction per route of total flow between airports, and airports are represented as source and sink nodes. The queuing network model operates by associating air traffic demand with a sequence of sectors, and advancing time in quarterhour increments. Sectors have a finite capacity, and flights may queue before transiting a sector, if demand would exceed capacity. In prior work, it was found that clustering airports reduced the network size and complexity, as well as the model’s run-time. 2 In this paper, we explore another means of reducing network size: route clustering, i.e., grouping of similar routes between airports. Assessing similarity of routes requires a similarity/difference measure and we propose the use of a specialized algorithm called “edit distance,” appropriate for lexical string representation, i.e., the sequence of sectors in a route. The paper is organized as follows. The next section describes the clustering algorithm: edit distance, similarity/difference assessment, and selection of a clustering method. Subsequent sections examine initial results, selection of a similarity threshold, and trading-off regression model error and resultant network size. A final section summarizes findings and suggests a next step in the analysis.

Original document

The different versions of the original document can be found in:

• http://www.mitre.org/sites/default/files/publications/air-route-clustering-for-queuing-network-model-14-1750.pdf

• http://arc.aiaa.org/doi/pdf/10.2514/6.2014-2161,

http://dx.doi.org/10.2514/6.2014-2161

• https://www.mitre.org/sites/default/files/publications/air-route-clustering-for-queuing-network-model-14-1750.pdf,

https://arc.aiaa.org/doi/10.2514/6.2014-2161,

https://academic.microsoft.com/#/detail/2319309396