Air Route Network Generation Based on Traffic Assignment

，，

College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China

Abstract:Air route network is the carrier of air traffic flow，and traffic assignment is a method to verify the rationality of air route network structure.Therefore，air route network generation based on traffic assignment has been becoming the research focus of airspace programming technology.Based on link prediction technology and optimization theory，a bi-level programming model is established in the paper.The model includes an upper level of air route network generation model and a lower level of traffic assignment model. The air route network structure generation incorporates network topology generation algorithm based on link prediction technology and optimal path search algorithm based on preference，and the traffic assignment adopts NSGA-III algorithm.Based on the Python platform NetworkX complex network analysis library，a network of 57 airports，383 nodes，and 635 segments within China Airspace Beijing and Shanghai Flight Information Regions and 187 975 sorties of traffic are used to simulate the bilevel model.Compared with the existing air route network，the proposed air route network can decrease the cost by 50.624%，lower the flight conflict coefficient by 33.564%，and reduce dynamic non-linear coefficient by 7.830%.

Key words:air route network；link prediction；traffic assignment；bi-level programming；NSGA-III algorithm

0 Introduction

With the rapid increase of air traffic in China，the defects of air route network structures are gradually exposed，imposing bumps to the rapid development of China's civil aviation transportation industry.Air route networks are crucial to realizing effective air traffic transportation and the transportation situation can in turn act as an important basis for examining the structures of air route networks.Therefore，the generation of air route networks based on traffic assignment has become an urgent research topic in the field of airspace programming.Most research on air route network generation has focused on air route networks themselves and optimization of existing air route networks.Kotegawa et al.put forward three different algorithms based on existing historical data，logistic regression，fitness function method and artificial neural network algorithm，to predict future airport pairs route connection probability in the United States［1］.Zhang et al.explored the impact of output value of the tertiary industry，airport degree and inter-airport distance on the airline connection，and established an airline connection probability model［2］.Du et al.usedK-core algorithm to evaluate China's air route networks and to divide China's air route networks into three levels，a core level，a connection level and an edge level，and analyzed the structural characteristics of different levels of air route networks［3］.These studies have provided references for the generation of air route networks.In terms of air route network optimization，Wang et al.introduced the cellular automaton model under the“three zones”evasion condition and conducted the air route network structure optimization using the data from the no-flow Beijing Flight Information Region.They also used their model to analyze the traffic capacity limitation of the Chinese mainland airspace.Their approach reduced the cost of air route network operation，the probability of flight conflict risk，and the non-linear coefficient［4-5］.Li et al.proposed an algorithm of CoM-ARN that considered both the optimization of waypoint location and adjacency relation in order to optimize the operational cost of air route networks and airspace security，and verified it with the actual airspace data in China［6］.

However，current studies are all about network structures under the existing traffic assignment.With regard to traffic assignment，Tian et al.proposed a multi-objective nonlinear air traffic assignment optimization model，which not only optimized the flight departure time and air route selection in traffic assignment，but also reduced the workload of controllers［7］.Cai et al.developed a route and time assignment algorithm（RTA）to solve the optimization problem of multi-target air networks with traffic assignment［8］.Xiao et al.proposed an effective hybrid direct and indirect coding genetic algorithm（HybrlD-GA）for multi-objective nonlinear air traffic assignment optimization［9］.Wu et al.proposed a multi-objective optimization model for airspace spatial sector networks to solve the global traffic flow collaborative optimization of spatial sector networks［10］.

Although a large number of scholars have devoted to air route network generation and traffic assignment，the research on the integration of both has been rarely reported. This paper proposes a model that generates air route networks based on traffic assignment.This bi-level model incorporates the upper level of system programming decision maker，and the lower level of system that uses the decision maker.First，the upper level generates an air route network，and transmits the air route network to the lower level.Then the lower level selects the route for the planned air route network，and uploads the traffic assignment result to the upper level，until air traffic network structure based on traffic assignment reaches the optimization.

1 Air Route Network Related Theory

1.1 Air route network and complex network

An air route network can be abstracted as a graphG=（V，E，W）by mathematical description，whereVrepresents the set of nodes in the network；Erepresents the set of connected segments between nodes，which are used to describe some relationship between nodes；Wrepresents the set of segment weights between nodes. As shown in Fig.1，the node setVin an air route network is divided into two airport points and one node，and the side setEis composed of the segment，and the weightWbetween two nodes is represented by the flow between them.

Fig.1 Air route network

If a network is formed by a mass number of nodes with complicated relationships，the network can be called a complex network.Ref.［11］analyzed the structure of China's mainland air route network from the perspective of complex network，and concluded that China's air route network is a scale-free network，and nodeviis subject to the power law distribution.Its average route lengthLis 13.19，that is，the route of any two nodes（vi，vj）are connected by 13 nodes.Most of the node interfacesBiare small，and only a few of node interfaces are large，thus the overall distribution is uniform.The convergence coefficientCof the China's air route network is 0.119，and the connections between nodes are not close.

1.2 Link prediction

Link prediction aims to infer the relationship between the existing information route points in a network，and to predict the possible segments based on the network structure，node attributes，etc.

According to the link prediction index NSIA［12］，this paper introduces the weighted traffic flow between airport pairs of an air route network，and proposes the weighted neighbor set information traffic assignment index（WNSIA）.The formula of the link prediction on the node pair similarity scores for WNSIA is as follows

whereWxyis the airport pairs traffic flow；the conditional self-information of the connected segment between a node pair（x，y）under the known condition common neighbor setΩ.

1.3 Bi-level programming

Bi-level programming is to optimize the network by introducing decision-makers at different levels.Decision-makers at different levels have different demands for network programming，and form the optimal result of network programming through cooperation among different decision-makers.

Compared with regarding the route network problem as a single-level programming，the bi-level programming method has the following advantages:

（1）In the bi-level programming，the two hierarchical structures are neither isolated，nor simply joined.They influence and interact with each other.

（2）Bi-level programming has more hierarchical structures，more perspectives of decision-making and more potentials in practice.

（3）Bi-level programming can analyze two different decision-making angles from two hierarchical structures，both of which have their own objective functions and constraints，and even the objective functions of the two decision-makers are contradictory.

2 Model Establishment

The upper model is the air route network generation model，which reconstructs the air route network structure with the objective of network similarity.The lower model is the traffic assignment model，and the traffic demand is allocated to the air route network with the objectives of air route network operating cost，flight conflict coefficient and dynamic non-linear coefficient.Fig.2 shows the flow chart of the air route network generation based on traffic assignment.

Fig.2 Air route network generation based on traffic assignment flowchart

Some assumptions are listed as follows:

（1）Aircraft that fly on the air route network are regarded as a mass point；

（2）All aircraft in the air route network are located at the same level，regardless of those rising or landing；

（3）The flying speed of the aircraft is 800 km/h，and the range of the node movement is plus or minus 50 km；

（4）Flight conflicts in the airport terminal area are not considered.

2.1 Establishment of air route network generation model

Air route network generation aims to analyze the structural characteristics and traffic characteristics of the air route network，and generate the initial air route network structure.

2.1.1 Objective function

Air route network node pair similarity refers to the score of the connection probability between node pairs in the air route network calculated by the link prediction algorithm，considering air route network structure characteristics and flow characteristics comprehensively，and the formula is given as

whereSijis the similarity between the nodes pairij，andxija binary variable，and

2.1.2 Bound for objective function

In the process of generating air route network，the distance of the generated segment should be within a certain range，and all airports should be connected to the air route network.

（1）Segment distance constraint

wheredijis the distance of the segmentij.

（2）Airport non-isolated constraint

wherebiis the number of sides of the airporti.

2.2 Establishment of traffic assignment model

Traffic assignment aims to distribute traffic flow of airport pairs to air route network.

2.2.1 Objective function

In the process of traffic assignment，the economics，safety and feasibility of the air route network are comprehensively considered.The air route network operating cost，flight conflict coefficient and dynamic non-linear coefficient are used as the objective function for traffic assignment.

（1）Air route network operating cost

wherefijis the flow of the segmentij.

（2）Flight conflict coefficient

wherefji，fkiare the flows of the segmentjiand the segmentki，respectively；Vis the flying speed of the aircraft；Ythe horizontal safety interval；andthe angle between the segmentikand the segmentjk.

（3）Dynamic non-linear coefficient

whereIijis the non-linear coefficient between airportiand airportj，andfijthe flow of segmentij.

2.2.2 Bound for objective function

（1）Segment capacity constraint

whereCijis the capacity of the segmentij.

（2）Node flow conservation constraint

wherefiniis the flow of entering the nodeiandfoutithe flow of going out from the nodei.

（3）The number of airlines between an airport pair

wherenstis the number of airlines between the airport pairst.

3 Algorithms

3.1 Improved network topology generator

According to the analysis of Ref.［11］，air route network has a scale-free network structure，so this paper designs the initial topology structure of an air route network based on the traditional BA model.

According to the BA model，the newly added nodejand the existing nodeiare independent of the great circle distance between this two nodes，and the probability of connection isBased on Ref.［13］and link prediction similarity，the traditional BA model is improved in this paper.It is assumed that the connection probability of the newly added nodejand the existing nodeisatisfies the Eq.（11）

The initial topology generation process of air route network is listed as follows.

Step 1Sort the nodes of the air route network according to importance values.

Step 2Add the nodes into the initial structure of the air route network according to the order of the nodes，and calculate the connection probabilities between the newly added nodes and the existing nodes according to Eq.（11）.

Step 3Sort the connection probabilities，and connect the new nodes to the existing node of the first ranking.

Step 4Repeat Step 2 to Step 3 until all nodes in the air route network are added to the initial structure of the air route network.

3.2 Optimal path search algorithm based on preference

According to Ref.［14］，the optimal path search algorithm based on preference is a path search algorithm combiningKshortest path search algorithm and the idea of link prediction similarity index.

（1）Algorithm principle

The optimal path search algorithm based on preference searches paths on the air route network generated by the improved network topology generator，which is a component of the air route network generation.

（2）Algorithm process

Step 1Select an origin-destination（OD）airport pair with traffic demand in the air route network，and use the similarity-based Dijkstra algorithm to obtain a path of this OD pair；

Step 2Convert the path from the start point to the end point into a flight segment set，extract the segment from segment set continuously and set it to the off state.Then use the Dijkstra algorithm to search the path based on similarity；

Step 3Repeat Step 2 until searchingKpaths for OD airport pair are found；

Step 4Select the least number of segments in theKpath set as the final path selection of the OD airport pair；

Step 5Repeat Step 1 to Step 4 until the final results are determined for all OD airport pairs.

3.3 NSGA-III algorithm

The NSGA-III algorithm is essentially a nondominated genetic algorithm，which is a third-generation multi-objective programming algorithm based on Deb［15］.It inherits the non-dominated sorting of NSGA-II algorithm，in order to overcome the shortcomings of premature convergence of the NSGA-II algorithm.The reference distance are deduced with the method of correlation operation instead of crowded degree operator，thus improving the diversity of algorithm population.Especially when the programming model catains more than three objective functions，the programming effect of the NSGA-III algorithm is significantly better than the NSGA-II and NSGA-I algorithms［16-17］.The specific steps are as shown in Fig.3.

Fig.3 NSGA-III algorithm flowchart

4 Simulation

Based on the Python platform NetworkX of complex network analysis library，a simulation scenario is conducted for China Airspace Beijing and Shanghai Flight Information Regions.First，based on the improved network topology generator，the air route network topology is generated for these areas.Then，based on the optimal path search algorithm based on preference，the path search is performed on the generated air route network topology structure，and the initial air route network is generated for these areas.Finally，traffic assignment is carried out based on NSGA-III algorithm.

Step 1Generate air route network topology based on the improved network topology generator.

After using the improved network topology generator to generate air route network topology，we obtain 383 nodes and 436 segments.The topology diagram of air route network is given in Fig.4.The specific segment data and its similarity data are shown in Table 1.

Fig.4 Initial topology of the air route network

Table 1 Partial segments and its similarity data of initial air route network

Step 2Use the optimal path search algorithm based on preference to conduct path search on the generated route network topology.If no path is found，the path search is conducted on the full connected network to generate the initial route network.

The optimal path search algorithm based on preference is used to search the path of 226 airport pairs on the air route network topology.The initial route network structure generates 325 nodes and 433 segments.Fig.5 shows the initial generation diagram of the air route network.The specific airport pairs path search data is shown in Table 2.

Fig.5 Air route network generation

Table 2 Partial airline data

Step 3Conduct traffic assignment based on NSGA-III algorithm，and transfer the resulted assignment and changed route network structure to Step 2.

The NSGA-III algorithm is used to search the path on the optimized route network.In the air route network structure after traffic assignment，338 nodes and 521 segments are shown.Fig.6 shows the network diagram after traffic assignment. Airport pairs assignment data are shown in Table 3.

Fig.6 Air route network traffic

Table 3 Partial traffic result data for airports

5 Discussion

Air route network evaluation is divided into the static structure evaluation and the dynamic operation index evaluation. The static structure index is to evaluate the internal structure of the air route network.The dynamic operation index is to evaluate the operational data of the air route network after the demand traffic flow of OD airport pairs are assigned to the air route network.

Air route network structure evaluation includes the number of nodes，the number of segments and the nodes，as shown in Table 4.

The evaluation on the air route network evalu-ates the existing the generated air route network and air route network based on traffic assignment with air route network operating cost，flight conflict coefficient and dynamic non-linear coefficient.

Table 4 Air route network static structure evaluation index

Table 5 shows that compared with the existing air route network，the gererated network decreases the operating cost by 50.624%，decreases the flight conflict coefficient by 33.564%，and decreases the dynamic non-linear coefficient by 7.830%.

Table 5 Air route network dynamic operation evaluation index

6 Conclusions

Based on the complex network theory and the optimization theory，this paper proposes a scheme of air route network generation based on traffic assignment，and introduces a bi-level programming model that includes an upper level of air route network programming，and a lower level of an air route network system.The upper level first generates an air route network，and then transmits its structure to the lower level.The lower level chooses routes on the programmed air route network and uploads the traffic assignment to the upper level.The proposed approach regards the two levels as two decision makers to target two respect issues，which is more approaching practical scenarios.In the bi-level model，the upper level considers the similarity during air route network generation，and the lower level considers the air route network operating cost，flight conflict coefficient and dynamic non-linear coefficient of traffic assignment.Network topology generation algorithm based on link prediction and optimal path search algorithm based on preference are used to generate air route networks.NSGA-III algorithm is used for traffic assignment.Then，the flight network composed of 57 airports，383 nodes and 635 segments of the Beijing and Shanghai Flight Information Regions in China's mainland airspace and 187 975 airport traffic flows are used for simulation.After using the improved network topology generator a to generate an air route network topology，383 nodes and 436 segments are obtained.The optimal route search algorithm based on preference is used to search 226 airport pairs on the air route network topology，and there are 325 nodes and 433 segments in the network structure.The NSGA-III algorithm is used to search the route on the optimized air route network.After traffic assignment，there are 338 nodes and 521 segments. Finally，compared with the dynamic operation index of the generated air route network and the existing air route network，it is found that the air route network operating cost is decreased by 50.624%，the flight conflict coefficient by 33.564%，and the dynamic non-linear coefficient is 7.830%.However，due to the limitation of“three-zone”in practice，some adjustments need to be made in future work.