This paper proposes a new method for dynamic airspace configuration based on a weighted graph model. The method begins with the construction of an undirected graph for the given airspace, where the vertices represent ...This paper proposes a new method for dynamic airspace configuration based on a weighted graph model. The method begins with the construction of an undirected graph for the given airspace, where the vertices represent those key points such as airports, waypoints, and the edges represent those air routes. Those vertices are used as the sites of Voronoi diagram, which divides the airspace into units called as cells. Then, aircraft counts of both each cell and of each air-route are computed. Thus, by assigning both the vertices and the edges with those aircraft counts, a weighted graph model comes into being. Accordingly the airspace configuration problem is described as a weighted graph partitioning problem. Then, the problem is solved by a graph partitioning algorithm, which is a mixture of general weighted graph cuts algorithm, an optimal dynamic load balancing algorithm and a heuristic algorithm. After the cuts algorithm partitions the model into sub-graphs, the load balancing algorithm together with the heuristic algorithm transfers aircraft counts to balance workload among sub-graphs. Lastly, airspace configuration is completed by determining the sector boundaries. The simulation result shows that the designed sectors satisfy not only workload balancing condition, but also the constraints such as convexity, connectivity, as well as minimum distance constraint.展开更多
With the continuous air traffic growth and limits of resources, there is a need for reducing the congestion of the airspace systems. Nowadays, several projects are launched, aimed at modernizing the global air transpo...With the continuous air traffic growth and limits of resources, there is a need for reducing the congestion of the airspace systems. Nowadays, several projects are launched, aimed at modernizing the global air transportation system and air traffic management. In recent years, special interest has been paid to the solution of the dynamic airspace configuration problem. Airspace sector configurations need to be dynamically adjusted to provide maximum efficiency and flexibility in response to changing weather and traffic conditions. The main objective of this work is to automatically adapt the airspace configurations ac- cording to the evolution of traffic. In order to reach this objective, the airspace is considered to be divided into predefined 3D airspace blocks which have to be grouped or ungrouped depending on the traffic situation. The airspace structure is represented as a graph and each airspace configuration is created using a graph partitioning technique. We optimize airspace configurations using a genetic algorithm. The developed algorithm generates a sequence of sector configurations for one day of operation with the minimized controller workload. The overall methodology is implemented and successfully tested with air traffic data taken for one day and for several different airspace control areas of Europe.展开更多
This paper deals with dynamic airspace sectorization （DAS） problem by an improved genetic algorithm （iGA）. A graph model is first constructed that represents the airspace static structure. Then the DAS problem is ...This paper deals with dynamic airspace sectorization （DAS） problem by an improved genetic algorithm （iGA）. A graph model is first constructed that represents the airspace static structure. Then the DAS problem is formulated as a graph-partitioning problem to balance the sector workload under the premise of ensuring safety. In the iGA, multiple populations and hybrid coding are applied to determine the optimal sector number and airspace sectorization. The sector constraints are well satisfied by the improved genetic operators and protect zones. This method is validated by being applied to the airspace of North China in terms of three indexes, which are sector balancing index, coordination workload index and sector average flight time index. The improvement is obvious, as the sector balancing index is reduced by 16.5 %, the coordination workload index is reduced by 11.2 %, and the sector average flight time index is increased by 11.4 % during the peak-hour traffic.展开更多
As the air traffic demand is anticipated to be increased significantly in the near future,dynamic and effective allocation of the airspace resource is becoming a world-wide focus in the research field of air traffic m...As the air traffic demand is anticipated to be increased significantly in the near future,dynamic and effective allocation of the airspace resource is becoming a world-wide focus in the research field of air traffic management（ATM）.Taking the U.S.targeting the en-route airsapce,a dynamic airspace configuration（DAC） algorithm to reconfigure the airspace in consideration of higher efficiency and safety is presented.First,a modeling technique based on graph theory is proposed to generate a mathematical model for the airspace,and then,the graph model is partitioned into subgraphs for the purpose of sectorizatoin.The final step generates sector configuration with desirable geometry shape.Through analysis on the Cleveland airspace center（ZOB） in the U.S.,the algorithm is proved to be robust to time-varying traffic load.展开更多
Dynamic airspace management （DAM） is an important approach to extend limited air space resources by using them more efficiently and flexibly. This paper analyzes the use of the dynamic air-route adjustment （DARA） ...Dynamic airspace management （DAM） is an important approach to extend limited air space resources by using them more efficiently and flexibly. This paper analyzes the use of the dynamic air-route adjustment （DARA） method as a core procedure in DAM systems. DARA method makes dynamic decisions on when and how to adjust the current air-route network with the minimum cost. This model differs from the air traffic flow management （ATFM） problem because it considers dynamic opening and closing of air-route segments instead of only arranging flights on a given air traffic network and it takes into account several new constraints, such as the shortest opening time constraint. The DARA problem is solved using a two-step heuristic algorithm. The sensitivities of important coefficients in the model are analyzed to determine proper values for these coefficients. The computational results based on practical data from the Beijing ATC region show that the two-step heuristic algorithm gives as good results as the CPLEX in less or equal time in most cases.展开更多
基金supported by the National Natural Science Foundationof China(No.61079001)
文摘This paper proposes a new method for dynamic airspace configuration based on a weighted graph model. The method begins with the construction of an undirected graph for the given airspace, where the vertices represent those key points such as airports, waypoints, and the edges represent those air routes. Those vertices are used as the sites of Voronoi diagram, which divides the airspace into units called as cells. Then, aircraft counts of both each cell and of each air-route are computed. Thus, by assigning both the vertices and the edges with those aircraft counts, a weighted graph model comes into being. Accordingly the airspace configuration problem is described as a weighted graph partitioning problem. Then, the problem is solved by a graph partitioning algorithm, which is a mixture of general weighted graph cuts algorithm, an optimal dynamic load balancing algorithm and a heuristic algorithm. After the cuts algorithm partitions the model into sub-graphs, the load balancing algorithm together with the heuristic algorithm transfers aircraft counts to balance workload among sub-graphs. Lastly, airspace configuration is completed by determining the sector boundaries. The simulation result shows that the designed sectors satisfy not only workload balancing condition, but also the constraints such as convexity, connectivity, as well as minimum distance constraint.
文摘With the continuous air traffic growth and limits of resources, there is a need for reducing the congestion of the airspace systems. Nowadays, several projects are launched, aimed at modernizing the global air transportation system and air traffic management. In recent years, special interest has been paid to the solution of the dynamic airspace configuration problem. Airspace sector configurations need to be dynamically adjusted to provide maximum efficiency and flexibility in response to changing weather and traffic conditions. The main objective of this work is to automatically adapt the airspace configurations ac- cording to the evolution of traffic. In order to reach this objective, the airspace is considered to be divided into predefined 3D airspace blocks which have to be grouped or ungrouped depending on the traffic situation. The airspace structure is represented as a graph and each airspace configuration is created using a graph partitioning technique. We optimize airspace configurations using a genetic algorithm. The developed algorithm generates a sequence of sector configurations for one day of operation with the minimized controller workload. The overall methodology is implemented and successfully tested with air traffic data taken for one day and for several different airspace control areas of Europe.
基金funded by the Joint Funds of the National Natural Science Foundation of China (61079001)
文摘This paper deals with dynamic airspace sectorization （DAS） problem by an improved genetic algorithm （iGA）. A graph model is first constructed that represents the airspace static structure. Then the DAS problem is formulated as a graph-partitioning problem to balance the sector workload under the premise of ensuring safety. In the iGA, multiple populations and hybrid coding are applied to determine the optimal sector number and airspace sectorization. The sector constraints are well satisfied by the improved genetic operators and protect zones. This method is validated by being applied to the airspace of North China in terms of three indexes, which are sector balancing index, coordination workload index and sector average flight time index. The improvement is obvious, as the sector balancing index is reduced by 16.5 %, the coordination workload index is reduced by 11.2 %, and the sector average flight time index is increased by 11.4 % during the peak-hour traffic.
基金Supported by the State Scholarship Foundation from China Scholarship Council(2008603024)
文摘As the air traffic demand is anticipated to be increased significantly in the near future,dynamic and effective allocation of the airspace resource is becoming a world-wide focus in the research field of air traffic management（ATM）.Taking the U.S.targeting the en-route airsapce,a dynamic airspace configuration（DAC） algorithm to reconfigure the airspace in consideration of higher efficiency and safety is presented.First,a modeling technique based on graph theory is proposed to generate a mathematical model for the airspace,and then,the graph model is partitioned into subgraphs for the purpose of sectorizatoin.The final step generates sector configuration with desirable geometry shape.Through analysis on the Cleveland airspace center（ZOB） in the U.S.,the algorithm is proved to be robust to time-varying traffic load.
基金Supported by the Basic Research Foundation of Tsinghua National Laboratory for Information Science and Technology (TNList)the National High-Tech Research and Development (863) Program of China (Nos. 2006AA12A114 and 2006AA12A105)the FokYing Tung Education Foundation (No. 114026)
文摘Dynamic airspace management （DAM） is an important approach to extend limited air space resources by using them more efficiently and flexibly. This paper analyzes the use of the dynamic air-route adjustment （DARA） method as a core procedure in DAM systems. DARA method makes dynamic decisions on when and how to adjust the current air-route network with the minimum cost. This model differs from the air traffic flow management （ATFM） problem because it considers dynamic opening and closing of air-route segments instead of only arranging flights on a given air traffic network and it takes into account several new constraints, such as the shortest opening time constraint. The DARA problem is solved using a two-step heuristic algorithm. The sensitivities of important coefficients in the model are analyzed to determine proper values for these coefficients. The computational results based on practical data from the Beijing ATC region show that the two-step heuristic algorithm gives as good results as the CPLEX in less or equal time in most cases.
