The Optimization of Chinese Air Route Network with Cooperative Coevolving PSO

Abstract

With the rapid development of Chinese air transportation, the performance of the Chinese air route network (ARN) becomes more and more important. Since the location of air route waypoints (ARWs) is crucial for the performance of ARN, we propose an ARW optimization model in this paper. In the model, the cooperative coevolving particle swarm optimization (CCPSO) is adopted to optimize the location of ARWs. The simulation results show that CCPSO can effectively decrease the total flight conflict coefficient and improve the performance of the Chinese ARN. Our work will be helpful to better understand and optimize the Chinese air route network. Introduction The air route is the real track that every flight travels from one airport to another. In the air route network (ARN), airports or air waypoints are nodes and links are denoted by the air route segments. Airports are the points that generate and absorb air traffic flow while air waypoints are the points that only transmit traffic flow without generating or absorbing any air traffic flow. There are two kinds of waypoints in ARN, one is the air route waypoints (ARWs) and the other is the crossing waypoints (CWs). An ARW is a navigation marker which keeps the pilots informed about the desired track [1,2], while a CW is a crossing point where two or more aircrafts may encounter with each other. With the rapid development of air transportation, researchers and practitioners have pay great attention in past decades to improve the efficiency and safety of the air transportation system [3,4]. Different models aiming to optimize the performance of ARN have been proposed and some important aspects have been taken into account [5,6], such as flights efficiency, potential conflict and airspace capacity. Siddiquee [5] firstly presented a mathematical model to quantify various attributes of the air route network. Mehadhebi et al. [7] proposed an approach to minimize the total airline cost of the ARN. Zhou et al. [8] proposed a multi-objective optimization algorithm to minimize both airline costs and flight conflicts. Cai et al. [9] proposed a bi-objective optimization model to solve the crossing waypoint location (CWL) problems. Their approach not only reduces the total airline cost (TAC) but also decreases the total flight conflict coefficients (TFCC). Jin et al. [10] proposed a triple-objectives model to solve the CWL problems, where three key factors (flights efficiency, potential conflict and airspace capacity) are investigated. Since the number of ARWs is larger than that of CWs, it is more difficult to optimize the location of ARWs. It is known that the cooperative coevolution (CC) algorithms [11-14] are suitable for solving large-scale optimization problems, and the particle swarm optimization (PSO) is an effective solution to solve complicated optimization problems. Thus, in this paper, we use the cooperative coevolving particle swarm optimization (CCPSO) to optimize the location of ARWs of the Chinese ARN. The rest of this paper is organized as follows. Section 2 describes the CCPSO algorithm in detail. Section 3 presents the ARW optimization model based on the CCPSO. Section 4, simulation results and correspondent theoretical analysis are provided. Finally, we give the including remarks in section 5. 2nd International Conference on Electronics, Network and Computer Engineering (ICENCE 2016) © 2016. The authors Published by Atlantis Press 378 The CCPSO Algorithm The CC algorithms can be regarded as automatic approaches to implement the divide-and-conquer strategy [11-14] and are quite effective for large-scale optimization problems. The particle swarm optimization (PSO) is a nature-inspired algorithm that has shown excellent performance in solving many real optimization problems. The CCPSO is a comprehensive optimization algorithm, where PSO and CC are incorporated together. The framework of CCPSO can be summarized as follows: (1) Problem decomposition: A high-dimensional decision vector is decomposed into some smaller subcomponents. This is a dynamically grouping process, where the variables are selected randomly to form groups and a scheme is used to dynamically determine the size of the coevolving subcomponent variables. (2) Subcomponent optimization: The algorithm of Cauchy and Gaussian PSO is used to optimize the subcomponents. In the algorithm, each swarm is located in a ring topology structure, which is potential to slow down the speed of convergence and maintains the diversity of population. (3) Subcomponents coadaptation: Since interdependencies may exist between subcomponents, coadaptation is essential to capture such interdependencies during the optimization process. It is necessary to combine all subcomponents to a complete decision vector. The best individual from other subpopulations will be used when the objective function is calculated. The ARW Optimization Model Actually, the ARW location optimization problem is a high-dimension problem. The challenge of the location optimization of the ARWs is two-fold: first, a typical problem involves a large number of design variables; second, the objective function is non-differentiable. It is difficult to solve these problems by using traditional optimization algorithms [15-17], which suffer from the “curse of dimensionality”, i.e., the performance will deteriorate rapidly as the dimensionality of search space increases. In our ARW optimization model, we will adopt the CCPSO [14] algorithm to optimize the location of ARWs. The target of the ARW optimization model is to optimize the location of ARWs within a limited airspace. Following the previous work [9], the mathematical formulation of the ARW optimization problem has three assumptions and principles: (1) The ARN is defined as a planar graph, without considering aircrafts’ climbing or descending among different flight levels. (2) The trajectory of each flight is always the shortest path in the ARN. (3) Since the airport is a part of flight trajectory, we define the position of airports as one of the decision variables. An ARW is a navigation marker whose longitude and latitude coordinates are determined by the ground navaids. Thus, the location of airports and ARWs can be represented as 2-dimensional vectors, xmin i ≤xi≤xmax i , ∀i∈{1, ..., n}, ymin i ≤yi≤ymax i , ∀i∈{1, ..., n}, (1) where xi and yi represent the location of ARW i. Objective: The objective can be measured by the total flight conflict coefficient (TFCC). Here, the TFCC is a reference value indicating how “dangerous” the network is. Generally, the larger the total flight conflict is, the higher the flight conflicting risk is. min TFCC = ∑ ∑ ∑ fji∙fki∙S V∙cos ( αjk i 2 ) Ti k=1 Ti j=1 j≠k n i=1 , (2) where fji is the traffic flow from node j to node i, and fki is the traffic flow from node k to node i; ajk i ∈[0,π] is the included angle between air routes ji and ki; S is the horizontal separation standard (km) of air traffic control, and V is the average cruising speed (km/h) of flights. Constraint: The flight efficiency, which can be calculated by the total airline cost (TAC) of flights. min TAC = ∑ ∑ fij∙dij, m+n j=1 m+n i=1 (3)

Original document

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

• http://dx.doi.org/10.2991/icence-16.2016.74 under the license https://creativecommons.org/licenses/by-nc

• https://download.atlantis-press.com/article/25860930.pdf

• https://www.atlantis-press.com/proceedings/icence-16/25860930,

https://academic.microsoft.com/#/detail/2521484050 under the license cc-by-nc