Large Scale Modeling And Optimization Of En Route Air Traffic Flow

Air Traffic Management (ATM) aims at ensuring safe and efficient movement of aircraft in the airspace. The National Airspace System is currently undergoing a comprehensive overhaul known as NextGen. With the predicted growth of air transportation, providing traffic flow managers with the tools to support decision making is essential. These tools should aid in accommodating the air traffic throughput increase, while limiting controller workload and ensuring high safety levels. In the National Airspace System (NAS), the goal of en-route Traffic Flow Management (TFM) is to balance air traffic demand against available airspace capacity, in order to ensure a safe and expeditious flow of aircraft, both under nominal and perturbed conditions. The objective of this thesis is to develop a better understanding of how to analyze, model and simulate air traffic in a given airspace, under both nominal and degraded conditions. First, a new framework for en-route Traffic Flow Management and Airspace Health Monitoring is developed. It is based on a data-driven approach for air traffic flow modeling using historical data. This large-scale 3D flow network of the Cleveland center airspace provides valuable insight on airspace complexity. A linear formulation for optimizing en-route Air Traffic is proposed. It takes into account a controller taskload model based on flow geometry, in order to estimate airspace capacity. The simulations run demonstrate the importance of sector constraints and traffic demand patterns in estimating the throughput of an airspace. To analyze airspace degradation, weather blockage maps based on vertically integrated liquid (VIL) are incorporated in the model, representing weather perturbations on the same data set used to compute the flows. Comparing the weather blockages and the network model of the airspace provides means of quantifying airspace degradation. Simulations under perturbed conditions are then run according to different objectives. The results of the simulations are compared with the data from these specific days, to identify the advantages and drawbacks of the present model.

This book combines the research activities of the authors, both of whom are researchers at Ecole Nationale de l’Aviation Civile (French National School of Civil Aviation), and presents their findings from the last 15 years. Their work uses air transport as its focal point, within the realm of mathematical optimization, looking at real life problems and theoretical models in tandem, and the challenges that accompany studying both approaches. The authors’ research is linked with the attempt to reduce air space congestion in Western Europe, USA and, increasingly, Asia. They do this through studying stochastic optimization (particularly artificial evolution), the sectorization of airspace, route distribution and takeoff slots, and by modeling airspace congestion. Finally, the authors discuss their short, medium and long term research goals. They hope that their work, although related to air transport, will be applied to other fields, such is the transferable nature of mathematical optimization. At the same time, they intend to use other areas of research, such as approximation and statistics to complement their continued inquiry in their own field. Contents 1. Introduction. Part 1. Optimization and Artificial Evolution 2. Optimization: State of the Art. 3. Genetic Algorithms and Improvements. 4. A new concept for Genetic Algorithms based on Order Statistics. Part 2. Applications to Air Traffic Control 5. Air Traffic Control. 6. Contributions to Airspace Sectorization. 7. Contribution to Traffic Assignment. 8. Airspace Congestion Metrics. 9. Conclusion and Future Perspectives. About the Authors Daniel Delahaye works for Ecole Nationale de l’Aviation Civile (French National School of Civil Aviation) in France. Stéphane Puechmorel works for Ecole Nationale de l’Aviation Civile (French National School of Civil Aviation) in France.

The Air Traffic Management (ATM) system enables air transportation by ensuring a safe and orderly air traffic flow. As the air transport demand has grown, ATM has become increasingly challenging, resulting in high levels of congestion, flight delays and environmental impacts. To sustain the industry growth foreseen and enable more efficient air travel, it is important to develop mechanisms for better understanding and predicting the air traffic flow behavior and performance in order to assist human decision-makers to deliver improved airspace design and traffic management solutions. This thesis presents a data-driven approach to modeling air traffic flows and analyzes its contribution to supporting system level ATM decision-making. A data analytics framework is proposed for high-fidelity characterization of air traffic flows from large-scale flight tracking data. The framework incorporates a multi-layer clustering analysis to extract spatiotemporal patterns in aircraft movement towards the identification of trajectory patterns and traffic flow patterns. The outcomes and potential impacts of this framework are demonstrated with a detailed characterization of terminal area traffic flows in three representative multi-airport (metroplex) systems of the global air transportation system: New York, Hong Kong and Sao Paulo. As a descriptive tool for systematic analysis of the flow behavior, the framework allows for cross-metroplex comparisons of terminal airspace design, utilization and traffic performance. Novel quantitative metrics are created to summarize metroplex efficiency, capacity and predictability. The results reveal several structural, operational and performance differences between the metroplexes analyzed and highlight varied action areas to improve air traffic operations at these systems. Finally, the knowledge derived from flight trajectory data analytics is leveraged to develop predictive and prescriptive models for metroplex configuration and capacity planning decision support. Supervised learning methods are used to create prediction models capable of translating weather forecasts into probabilistic forecasts of the metroplex traffic flow structure and airport capacity for strategic time horizons. To process these capacity forecasts and assist the design of traffic flow management strategies, a new optimization model for capacity allocation is developed. The proposed models are found to outperform currently used methods in predicting throughput performance at the New York airports. Moreover, when used to prescribe optimal Airport Acceptance Rates in Ground Delay Programs, an overall delay reduction of up to 9.7% is achieved.

This volume is a compendium of papers presented during an Advanced Seminar on Air Traffic Control (ATC) that took place in Capri, Italy on October 28-31, 1991. The Seminar was' organized by the Progetto Finalizzato Trasporti of the Italian National Research Council. The papers presented in the Seminar dealt with a wide range of topics which are currently important in ATC. For example, there were papers on such subjects as recent developments in primary and secondary radar technologies, communications networks and protocols, and the future uses of satellite-based communications, navigation and surveillance in ATC. However, all the papers contained in the volume were selected exclusively from that set of papers that addressed some aspect of the main area of emphasis in the Seminar, namely massive data-processing requirements and computer intensive problems in ATC. Data-processing requirements in A TC have grown enormously over the years. Obviously, the rapid increase in air traffic volumes in most of the world is one of the factors that has contributed to this growth. However, two other developments have contributed much more significantly: first, the ATC system now collects (mostly automatically) immensely more "information per flight" than in the past; and, second, as the system's complexity increases and as it becomes more tightly interconnected geographically, so grows the need to communicate, process and "filter" the data presented to the system's various components.

Due to a soaring air travel growth in the last decades, air traffic management has become increasingly challenging. As a consequence, planning tools are being devised to help human decision-makers achieve a better management of air traffic. Planning tools are divided into two categories, strategic and tactical. Strategic planning generally addresses a larger planning domain and is performed days to hours in advance. Tactical planning is more localized and is performed hours to minutes in advance. An aggregate route model for strategic air traffic flow management is presented. It is an Eulerian model, describing the flow between cells of unidirectional point-to-point routes. Aggregate routes are created from flight trajectory data based on similarity measures. Spatial similarity is determined using the Frechet distance. The aggregate routes approximate actual well-traveled traffic patterns. By specifying the model resolution, an appropriate balance between model accuracy and model dimension can be achieved. For a particular planning horizon, during which weather is expected to restrict the flow, a procedure for designing airborne reroutes and augmenting the traffic flow model is developed. The dynamics of the traffic flow on the resulting network take the form of a discrete-time, linear time-invariant system. The traffic flow controls are ground holding, pre-departure rerouting and airborne rerouting. Strategic planning---determining how the controls should be used to modify the future traffic flow when local capacity violations are anticipated---is posed as an integer programming problem of minimizing a weighted sum of flight delays subject to control and capacity constraints. Several tests indicate the effectiveness of the modeling and strategic planning approach. In the final, most challenging, test, strategic planning is demonstrated for the six western-most Centers of the 22-Center national airspace. The planning time horizon is four hours long, and there is weather predicted that causes significant delays to the scheduled flights. Airborne reroute options are computed and added to the route model, and it is shown that the predicted delays can be significantly reduced. The test results also indicate the computational feasibility of the approach for a planning problem of this size.

A key limitation in accommodating continuing air traffic growth is the fixed airspace structure (sector boundaries), which is largely determined by historical flight profiles that have evolved over time. The sector geometry has stayed relatively constant despite the fact that route structures and demand have changed dramatically over the past decade. Dynamic Airspace Sectorization (DAS) is a concept where the airspace is redesigned dynamically to accommodate changing traffic demands. Various methods have been proposed to dynamically partition the airspace to accommodate traffic growth while also considering other sector constraints and efficiency metrics. However, these approaches suffer several operational drawbacks, and their computational complexity increases exponentially as the airspace size and traffic volume increase. In this thesis, I experimentally evaluate and identify gaps in existing 3D sectorization methods, and propose an improved Agent Based Model (iABM) to address these gaps. I also propose three additional models using KD-Tree, Support Plane Bisection (SPBM) and Constrained Voronoi Diagrams (CVDM) in 3D, to partition the airspace to satisfy the convexity constraint and overcome high computational cost inherent in agent-based approaches. I then look into optimizing the airspace sectors generated by these four models (iABM, KD-Tree, SPBM, and CVDM), using a multi-objective optimisation approach with Air Traffic Controller (ATC) task load balancing, average sector flight time, and minimum distance between sector boundaries and traffic flow crossing points as the three objectives. The performance and efficiency of the proposed models are demonstrated by using sample air traffic data. Experimental results show that all the approaches have strengths and weaknesses. iABM has the best performance on task load balancing, but it can't satisfy the convexity constraint. SPBM and CVDM perform worse than iABM on task load balancing but better on average sector flight time, and they can satisfy the convexity constraint. The KD-tree based model is the most efficient, but not effective as it performed poorly on the given objectives because of its representational bias, which also limits its use in an operational environment. To further investigate SPBM and CVDM for national airspace sectorization, a real time air traffic monitoring and advisory system, called TOP-LAT (Trajectory Optimization and Prediction of Live Air Traffic), is developed and implemented. TOP-LAT is a real time system, synthesizing real time air traffic data to measure and analyse airspace capacity, airspace safety, air traffic flow and aviation emission, to enable ATM participants to access timely, accurate and reliable information for ATM decisions. TOP-LAT provides an ATM environment to evaluate and investigate the advanced ATM concepts, such as DAS. A number of experiments of Australian airspace sectorization by the two proposed DAS models are conducted in this thesis. In these experiments, the current and projected air traffic demands are generated based on public statistics, and some future ATM concepts (e.g. User Preferred Trajectory) are prototyped in order to investigate the performances of the proposed models. The results show that both models have advantages over the current airspace sector configurations in terms of task load balancing, longer flight sector time, larger minimum distance between sector boundaries and traffic flow crossing points, and reduced maximum task load for ATC. These experiments also show that Both models have the capability to be compatible with other advanced ATM concepts. However, no single approach can meet all complex air traffic management objectives. It is the air traffic flow pertaining to the kind of airspace and the associated traffic complexity which can determine the best approach for dynamic sectorization.

The steady increase of congestion in air traffic networks has resulted in significant economic losses and potential safety issues in the air transportation. A potential way to reduce congestion is to adopt efficient air traffic management policies, such as, optimally scheduling and routing air traffic throughout the network. In recent years, several models have been proposed to predict and manage air traffic. This thesis focuses on the comparison of two such approaches to air traffic flow management: (i) a discrete Mixed Integer Program model, and (ii) a continuous flow-based model. The continuous model is applied in a multi-commodity setting to take into account the origins and destinations of the aircraft. Sequential quadratic programming is used to optimize the continuous model. A comparison of the performance of the two models based on a set of large scale test cases is provided. Preliminary results suggest that the linear programming relaxation of the discrete model provides results similar to the continuous flow-based model for high volumes of air traffic.