The Research Of Terminal Airspace Sector Design Based On Graph Partitioning

With the increase of the number of aircrafts and the density of air traffic flow, the current airspace sector structure can no longer accommodate to the traffic flow. The air traffic flows are different in different kinds of airspaces. In some sectors the flow go over the capacity, but at the same times the flow far below the capacity in other sectors. In this case the airspace can not be used effectively. Therefore, the reasonable division of terminal area has a vital significance on the rational use of airspace resources and air traffic safety.To solve the problems above, the sector classification rules are studied, and the algorithm of the terminal airspace sector optimization which based on the air traffic flow is put forward. Terminal airspace graphic model, airspace sector partition and airspace boundary optimization method are studied.Firstly, abstract the airspce into the network topology graph. Bsaed on the basic air route network structure of control airspace and air traffic flow, a connection model between vertices are proposed. With the using of vertices fusion and route discretization methods, an terminal airspace graphic model is built. Secondly, airspace graph vertices are clustered by using the spectral clustering algorithm. With this method, the problem of bad partition for close parallel routes is solved, and also the sector convex hulls are constructed and partitioned.Finally, the graph theory based on convex hull and MAKLINK and an optimal path selection algorithm for sector boundaries based on Dijkstra algorithm are proposed.With xi ’an terminal area as an example for analysis, the experiments result shows that the algorithm can design and optimize airspace sectors according to the requirements of air traffic flow with high accuracy and efficiency.The algorithm of airspace sector design based on graph partitioning proposed can partion the terminal airspace into several sectors to balance the flows in different sectors andminimize the cooperation work, and also solve the problem that the close parallel routes are divided into different clustering at the same time. The algorithm has a high efficiency which can satisfy the dynamic change of air traffic demand and the need for flexible use of the airspace.