Three-Dimensional Planning of Arrival and Departure Route Network Based on Improved Ant-Colony Algorithm

(王超), nan(賀超男)

College of Air Traffic Management, Civil Aviation University of China, Tianjin 300300, P.R.China (Received 18 April 2014; revised 2 May 2015; accepted 12 July 2015)

Three-Dimensional Planning of Arrival and Departure Route Network Based on Improved Ant-Colony Algorithm

WangChao(王超)*,HeChaonan(賀超男)

College of Air Traffic Management, Civil Aviation University of China, Tianjin 300300, P.R.China (Received 18 April 2014; revised 2 May 2015; accepted 12 July 2015)

In order to improve safety, economy efficiency and design automation degree of air route in terminal airspace, Three-dimensional(3D) planning of routes network is investigated. A waypoint probability search method is proposed to optimize individual flight path. Through updating horizontal pheromones by negative feedback factors, an antcolony algorithm of path searching in 3D terminal airspace is implemented. The principle of optimization sequence of arrival and departure routes is analyzed. Each route is optimized successively, and the overall optimization of the whole route network is finally achieved. A case study shows that it takes about 63 s to optimize 8 arrival and departure routes, and the operation efficiency can be significantly improved with desirable safety and economy.

terminal airspace; arrival/departure route; ant-colony algorithm; path planning; transportation network design

0　Introduction

Arrival and departure route network are important airspace resources and play an important role in terminal air traffic control. Well structured route network can not only reduce flight conflicts but also shorten flight distances, thus improving safety margin and reducing aircraft operating cost. However, artificial design of arrival/departure routes has been subject to limited signal covering ranges of ground-based navigation equipments in the past,and could not efficiently balance safety with economy. Fortunately, the application of performance based navigation(PBN) technology provides a technical basis for flexible route planning. Therefore, it is valuable to study automatic arrival/departure route planning for satisfying multiple objective requirements.

Arrival and departure routes in terminal airspace is a tree network composed of one-way paths in three-dimensional(3D) space. Arrival and departure routes regulate landing aircraft and taking-off aircraft seperately, which is a kind of traffic flow segregation. In arrival/departure route planning, it is the priority to search the proper flight path between two points, while the connectivity between different routes can be neglected. Obviously, arrival/departure route network planning is different from common network design problem(NDP), and similar to the thought of ″routing one by one and further optimizing them into a network″[1-3]in public traffic network. Therefore, the flight path planning in 3D airspace can be considered as the foundation of arrival/departure route planning.

At present, abundant researches have focused on path planning including real-time trajectory planning of air launched cruise missile[4], UAV threat avoidance path planning[5-6], and path planning of mobile robot in dynamic environment[7-8]. Path planning methods can be roughly classified into three categories:(1) Path planning based on schematic diagram;(2) path planning based on grid; (3) path planning based on analogy. Each kind of methods utilizes a different heuristic algorithm, such as Voronoi diagram, particle swarm algorithm, A*algorithm, genetic algorithm, and artificial neural network,to search the optimal path satisfying certain conditions.

However, the previous work mainly concentrated on 2D space path planning, while 3D arrival/ departure route network has been seldom reported. Pfeil[9]has proposed a 3D optimization method of arrival/departure routes based on A*algorithm, but its search space was so large that the running time would extend exponentially with an increasing number of routes to be optimized.

In our work,the optimization of individual route is achieved first, and then a probability search method is proposed to select waypoints. Therefore, the path search algorithm in 3D space is established with the help of ant-colony algorithm. On this basis, the previous optimization results are used as current constraints according to a certain priority principle, and the arrival/departure routes are planed one by one to complete the planning and design of route network. Finally, the runway 05L of Xi′an/Xianyang Airport is taken as an example for the verification and analysis of our proposed algorithm.

1　Design of Arrival/Departure Route Network in Terminal Airspace

The arrival/departure route in terminal airspace is referred to an airborne route provided by ground-based or satellite-based navigation equipment which meets the requirement of a certain navigation performance. Arrival aircraft converge to runway-in-use along the arrival route from entrance waypoints of different upper air routes (UARs), and eventually finish descending and landing; while departure aircraft take-off from runway-in-use and diverge to different exit waypoints connected with the UARs, and eventually reach cruising level. Therefore, the arrival/departure routes and the network composed by them are important facilities for controlling air traffic. Regarding to the principle of ″routing one by one and further optimizing them into a network″, the network planning of arrival/departure route mainly includes two challenges:

(1) Search the optimal route in 3D airspace which meets the requirement of flyability with a pair of known original waypoint and destination waypoint of an individual route;

(2) Sequentially optimize the whole network of multiple paths based on the optimization of individual routes.

1.1Model of initial conditions for terminal airspace

Terminal airspace is the space scope of arrival/departure route network optimization, and the establishment of terminal airspace diagram model is the precondition of arrival/departure route network research.

A model of initial conditions of general airspace is established, as shown in Fig.1. With the reference point of airport as the coordinate originO, a rectangular plane coordinate system is constructed, and thus the main units of terminal airspace include:

(1) Terminal control areaG

The boundary of control zoneGis defined by a point sequence {v1,v2,vi,…,vz}, which also determines the space scope of arrival/departure route network.

(2) Restricted airspace (RA)

RA refers to the non-civil airspace, usually denoted by a convex polygon. Considering RA spatial attributes, we put forward four kinds of RA models:Ground restricted area, suspended restricted area, tall restricted area and final approach restricted zone,where the final approach restricted zone is a populated area of landing aircraft. In order to prohibit the routes traversing from final approach and avoid route crossing, a rectangular restricted area is designated, with a width of 20 km where the runway center is the starting point, and with a length of 30 km along the inverse landing direction.

(3) Runway (RW) and original and destination points of routes

RW is described by the airport reference pointcr, the runway lengthland the runway numbernrdenoting its orientation. The starting pointasiofanarrivalrouteRarris the transfer point between UAR and terminal airspace; and the terminal point is the initial approach fixaeiof runway-in-use; the starting point of a departure routeRdepis the initial turning pointdsiin taking-off direction, and the exit point is the transfer pointdeiof terminal airspace and UAR.

Fig.1　Initial conditions model in terminal airspace

1.2Route planning

Network planning of arrival /departure route is essentially to search 3D paths which obey the constraint of avoiding all kinds of restricted areas and meet certain optimization objectives in the terminal airspace. Suppose routeRhasmsegments, with starting pointp0=(xs,ys,hs)andendingpointpe=(xe,ye,he),wherexs,ys,hsandxe,ye,hearethelateral,thelongitudinalandtheverticalcoordinatesofp0andpe,respectively.UsuallyrouteRcan be expressed by a waypoint sequence or a segment sequence. Here, segment is a vector composed of the current waypointpi=(xi,yi,hi) and the next waypointpi+1=(xi+1,yi+1,hi+1), wherexi,yi,hirepresentthelateral,thelongitudinalandtheverticalcoordinates,respectively.

2　Multiple Objective Model of Arrival/Departure Route Planning

The solution space range of arrival/departure route planning would be quite large[9],causing a low algorithm efficiency, if feasible waypoints was directly searched in 3D space. Therefore,we expect to decouple the optimization of 3D routes into 2D(horizontal and vertical)planes.Route optimization in horizontal plane mainly solves the shortest path problem, while the vertical one mainly tries to approach the most economical performance profile of aircraft. The above problems have different objective dimensions, large numerical difference and incommensurability, so it is necessary to establish a fuzzy satisfaction function for each objective.

2.1Objective functions

(1) Economy in horizontal profile

(1)

In order to ensure the economical operation of the route,dminis defined as the shortest straight distance between the starting point and the ending point of routeR, without considering the restricted airspace condition. Selectingdminasareferenceofrouteprojectionlength,thendmincanbecalculatedasfollows

(2)

Inordertoevaluatethesatisfactiondegreeofhorizontalprofileeconomyandensurethetotallengthoftherouteprojectiondapproachesdminascloseaspossible,theeconomicalmembershipfunctionofrouteRin the horizontal profile is established as

(3)

(2) Closeness of flight performance in vertical profile

In vertical profile, statistical analysis showed that the optimal climbing model was to climb to cruise altitude as soon as possible with 7% gradient, while the optimal descending model selected 3% gradient[10]. In order to meet the requirements of aircraft flight performance and obtain the optimal economical profile, route gradient should approach the optimal vertical section as close as possible.

Suppose that climb/descent gradient of segmentSiof routeRisγi,whichobeysGaussdistributionbeforeaircraftclimbtoh1or descend toh2. Thus, the approaching degree membership function of segmentSiin the vertical section can be expressed as

(4)

whereγ0denotestheoptimalclimb/descentgradient,σtheextentofdeviationbetweenγiandthecorrespondingoptimalclimb/descentgradient,hthe section climb/descent height, andh1andh2represent the highest route climb and descent point, respectively.

As the entire route is formed by multiple segments, the approaching degree of routeRin the vertical profile equals to the sum of approaching degree in each segment, as

(5)

To unify the dimension of different objectives, all the vertical profile functions should be normalized before next operation. Definefmaxas the sum of optimal gradient in each segment of routeR, and then the membership functions of the whole routeRin the vertical profile can be expressed as

(6)

2.2Constraint conditions

(1) Segment obstacle safety

Segment obstacle means that the civil aircraft need to maintain a sufficient vertical distance when they fly over each ground restricted zone. Suppose that the aircraft flight height ishand the minimum obstacle clearance of current flight step is minimum obstacle clearance(MOC). The restricted area in terminal airspace isB={b1,b2,…,bj,bg}, wherebj=(xj,yj,hj), withxj,yjandhjdenotingthelateral,thelongitudinalandtherelativeheight,respectively.ThestartingpointofsegmentSiispi=(xi,yi,hi),andtheendingpointispi+1=(xi+1,yi+1,hi+1).

AccordingtotherequirementsofDOC8168[11],ahorizontalprotectionzonewithawidthofwand a length of |si| is constructed by taking the projected trajectory |si| ofSias center. If obstaclebjis in the protection zone, the obstacle should be considered as a potential dangerous obstacle. Then, it is necessary to calculate the vertical obstacle clearancehMOC[12], as

(7)

whereyis the distance between obstaclebjand the projected trajectory measured along the direction perpendicular to the trajectory. Therefore, the vertical distance betweenSiandbjshould meet the following conditions

(8)

(2) Obstacle avoidance

The tall restricted area in terminal airspace is impassable obstacle for civil aircraft. Therefore, the designed routes must avoid this kind of restricted area and maintain a sufficient horizontal distanced0. Notably, it is necessary to calculate the distances between each segment and the tall restricted area when compute the distance between the route and the tall restricted area. Suppose the vertex sequence of a restricted area lines in a clockwise order aso1,o2,…ok,…,oK; the segment of routeRisSi=(pi,pi+1), and that the vertical intersection point ofokandSior its extension line ispik. Defineq=(pi,pik),d1=(ok,pi),d2=(ok,pi+1) anddp=(ok,pik), and thus the horizontal distance between vertexokandSiis[13]

(9)

For all the distances between the segment and the tall restricted area, take the minimum value as the distance between routeRand the tall restricted area[13], namely

(10)

whereRRAis the using airspace of restricted area,mthe arrival/departure route segment number, andKthe number of tall restricted zone vertices.

Therefore, the following condition needs to be satisfied for routeRto bypass the tall restricted area horizontally

(11)

(3) Flight feasibility constraint

Flight feasibility is an index of the air route smoothness degree. In order to meet the requirements of mobility and passenger comfort of civil aircraft, the deflection angle between a segment and the next segment should satisfy

(12)

In the planning set of arrival and departure routes, the objectives corresponding to each solution has its own membership function value, and we can determine the satisfaction degree of the planning according to the relative distance. Considering different objective requirements, we adopt the optimization strategy of weighted sum to realize the maximum optimization of each objective under the following constraint conditions

(13)

3　Route Planning Based on Improved Ant-Colony Algorithm

3.1Initial solution based on the MAKLINK line

According to the research of Maki K[14], path planning method based on visual diagram can effectively avoid the restricted area and reduce the search space of waypoint, thus improving the algorithm efficiency. Therefore, the MAKLINK line should be designated based on the restricted zones in terminal airspace,e.i.,o1o2o3o4．Intherouteoptimizationprocess,arrivalanddepartureroutesarenotallowedtoexceedtheinternalregionoftheterminalairspace,sotheMAKLINKlineshouldberemovedoutoftheterminalairspace,asthedottedlineinFig.2.

AsshowninFig.2,dIAFis the initial approach location of approach procedure.dsindicates the starting point anddethe end of a departure route. We denoteasas the starting point andaethe end of arrival route. The midpoint of every MAKLINK line is denoted asui. When departing or arriving, turning angels of aircraft should meet the requirement of flight feasibility. Therefore we need to take the route deflection angle as the flight feasibility constrain. We selectdsordIAFas starting points, MARKLINK linesl1andl2are artificially constructed separately. Normally they are 30 km long. Thus, the defection angle can be satisfied by choosing points on them.

The initial solution of route is a feasible routeR0in the solution space composed of midpoints of MAKLINK lines,the given starting point and the ending point of each arrival/departure route, as follows:

Given a starting point and an ending point of each arrival/departure route, an initial solutionR0could be searched in the solution space composed of midpoints of MAKLINK lines using Dijkstra algorithm[15], andR0can be expressed as

(14)

To sum up, routeR0is the optimized initial feasible solution of arrival/departure route, and the point set sequence in MAKLINK lines makes up of the route solution space.

3.23D space route optimization based on improved ant colony algorithm

Ant-colony algorithm (ACO) is a new heuristic algorithm based on evolution simulation, which can be used to solve complex optimization problems[16]. The goal of arrival/departure route optimization is to make the vertical profile close to the optimal section on the premise of the shortest total length of the route in horizontal plane. Therefore, a waypoint searching method which works along the horizontal direction first and then the vertical direction is proposed.

3.2.1Searching rules of horizontal and vertical waypoints

Fig.3 shows the searching rules of segments. Supposexants line from the starting pointp0to the ending pointpe. At waypointpi=(xi,yi,zi), the searching steps of the next waypointpi+1are as follows:

(1) Divide the searching solution space of waypoint into two parts as horizontal and vertical sections, and partition the MAKLINK lineLiLi′equally in the horizontal section, with the level discrete degree ofaand discrete nodes ofl1,l2, …,la;

(2) Select horizontal nodeliwith a certain probabilityphoz, as calculated in Eq.(15);

(3) On this basis, partition the gradient equally, with the vertical discrete degree ofband discrete nodes ofe1,e2, …,eb;

(4) Select vertical nodeejaccording to a certain probabilitypver, as calculated in Eq.(15)

(15)

Fig.3　Searching rules of segments

Throughtheabovesteps,thenewwaypointcanbeobtained,andthewaypointsearchofthewholeroutecanbeachievedbyrepeatingthesesteps.

3.2.2Updatingrulesofhorizontalandverticalpheromones

Intheant-colonyalgorithm,asamediaofinformationtransmission,pheromonesaretoguidethealgorithmrunningorientation.Ingeneral,thepositivefeedbackupdatingruleisadopted,namelythemoreantswalkalongapath,thehighertheprobabilityoflaterantschoosingthatpathis.However,ifthewaypointsdonotsatisfytheconstraintsofobstaclesafetyandflightfeasibility,thealgorithmwillchoosenottoupdatepheromonesortoabandontheroute,whichleadstolocaloptimalornooptimalsolutionfortheroutesearch,aswellasaslowconvergenceofthealgorithm.Therefore,thenegativefeedbackruleisproposedtoupdatesuchpheromones.

Supposef0is an evaluation value of the previous route. If the new routef(R) satisfies the constraints and excels the former route, the pheromonesτhozinthehorizontaldirectionandτverintheverticaldirectionareupdatedaccordingtothepositivefeedbackrules.Iff(R) does not satisfy the constraints, it is necessary to add negative feedback factorreinto pheromones of the new route to reduce the pheromones in the horizontal direction and further enlighten the route to fly around horizontally

(16)

(17)

4　Optimization of Arrival/ Departure Route Network

4.1Principles of optimization sequence

There are usually many arrival/departure routes in terminal airspace, which inevitably cross with each other. As the optimization order directly affects economic benefits, principles for optimization should be proposed:

(1) Since civil aircraft cost more fuel in low altitude flying and climbing than in high altitude cruising, departing aircraft need to climb up to cruising altitude under high thrust without interruption. On the other hand, arriving aircraft generally use descent mode of engine idling with almost zero thrust, and the fuel consumption is little. Thus, route length is no longer a bottleneck of reducing fuel consumption especially in continuous descent approach(CDA) technology. Therefore, the principle that departure route is prior to arrival route is proposed.

(2) On the basis of the first principle, lots of aircraft can operate closely to their ideal vertical profile by reducing interference to the vertical profile of the routes with heavy traffic flow, which decreases the overall cost of fuel. Therefore, interference minimization of those routes with heavier traffic flow is a prior factor in route optimization.

4.2Vertical separation of route intersection

Route intersection problem is an inherent factor which leads to flight conflicts, so enough vertical separation should be established as far as possible at the intersection. Suppose that arrival routeRarrand departure routeRdephave an intersectionzin the horizontal plane belonging to segmentspipi+1andqjqj+1, and that the gradients areγaandγdrespectively.Ifpi=(xa,ya,ha)andqj=(xd,yd,hd), we definedarrandddepas the horizontal distances between the segment starting pointspi,qjand the intersection, respectively, and the vertical separation at the intersection can be obtained as

(18)

In order to satisfy the flight safety margin at the intersection, we take the designed departure routeRdepas a vacant restricted area, and construct a rectangular protection zone of 300 m wide and |qjqj+1| long with segmentqjqj+1as the center. Ifpi+1is in the zone, the intersection does not meet the requirement that the vertical separation between arriving and departing aircraft should be larger than 300 m, and we should search waypoint again according to Section 4.3 until the vertical separation satisfies the requirement.

4.3Lateral separation between routes

To ensure the proximity of two adjacent routes with adequate lateral safety distance, the distance between routes needs to be determined. We separate the two routes with seperate unit length separationda, and obtain the discrete point sequence that characterizes the routes. As a result, the distance between the two routes can be calculated using the distance between two point sets of different routes. We adopt forward Hausdorff distance to define the distance of two flight paths as

(19)

wherep(i,s)andp(j,t)denote the discrete point coordinates with sequence numbersandt, respectively. Therefore, the lateral separation should be larger than 10 000 m in order to ensure the lateral safety margin between routes.

4.4Route evaluation function

Route evaluation function is a function to assess the satisfaction degree of routes, which calculates the quantitative evaluation value according to the route economy in the horizontal section and the approaching degree in the vertical section. We build a piecewise route evaluation function under route constraints to describe the feasibility of objective function in the horizontal and vertical sections. Route evaluation function is defined as

(20)

whereω1andω2aretheweightingfactorstoevaluatedifferentobjectives.

5　Case Study

Taking the 05L runway of Xi′an/Xianyang international airport as an example, the 3D planning of arrival/departure route network is studied, and the initial condition diagram model in terminal airspace is shown in Fig.4. The terrain of this terminal airspace is complex and there are many ground restricted zones. Considering four typical dangerous obstacles in Fig.4, obstacleb1is1 359mhigh,andfourtallrestrictedzonesareR306,R307,R308,andR309.Besides,afinalapproachrestrictedzoneR310of20kmwideand30kmlongisdesignatedwiththerunwaycenterasitsstartingpoint.SelecttheendofRunway05LasthestartingpointTOF,whilethecompulsoryreportingpointsofTEBIB,LOVRAandP54andtherequestedreportingpointofP32astheendingpoints,andthenwecandefinefourdepartureroutesofRd1,Rd2,Rd3,Rd4. Select the compulsory reporting points NUGLA and VOR navigation stations of NSH and HO as starting points, while the initial approaching locating point IAF as an ending point, and we can define three arrival routes ofRa1,Ra2,Ra3.TheMAKLINKlinegeneratedaccordingtoSection3.1isadottedlineasshowninFig.4.

Fig.4　Terminal airspace model of Xi′an/Xian Yang Airport

(1)Individualrouteplanningbasedonantcolonyalgorithm

Table 1　Optimization results of air route Rd1

(2) Network optimization of departure routes

According to principles of optimization sequence and the actual air traffic flow of Xiaan Airport, optimization order of the departure routes is determined asRd1

Fig.5　Optimization results for arrival and departure route network

(3)Networkoptimizationofarrivalroutes

Thearrivalrouteoptimizationisachievedbasedondeparturerouteoptimization,andtheoptimizationorderisRa1

RouteRa1anddeparturerouteRd2intersectatpointA. The distance betweenAand the ground end of routeRd2is94 720m,whilethedistancebetweenAand the ground end of routeRa1is112 900m.Theverticalseparationatthatpointcanbecalculatedasdz_A=1 093 m using Eq.(18), as shown in Figure 6. RoutesRa1andRd1intersectatpointB, and the vertical separation dz_B=316 m. Without considering the constraints of the vertical and lateral separation, the optimization result of routeRa2isthedottedlineinFig. 5(b).Takingda=1 000 m, the lateral separation ofRa2canbeobtainedasd(Ra1,Rdi) =3 260 m according to Section 4.3, which apparently does not satisfy the lateral separation requirements. If we use the Eq.(16) to reduce pheromones of waypoint in the horizontal direction and enlighten the route to bypass obstacles, obvious shift can be achieved. Thus, the arrival route would intersect with departure routesRd3andRd1atpointsCandD, and vertical separation requirements can be satisfied, as shown in Fig.6. Table 2 shows the results of network optimization of arrival/departure route.

Fig.6　Vertical profile of departure and arrival routes

Para?meterSeg1Seg2Seg3Seg4Seg5Seg6Seg7d/kmγi/%d/kmγi/%θ/(°)d/kmγi/%θ/(°)d/kmγi/%θ/(°)d/kmγi/%θ/(°)d/kmγi/%θ/(°)d/kmγi/%θ/(°)μH～(R)μV～(R)Rd113．569．979236．9717148．401800．97640．9845Rd212．0682．1515632．2717932．701790．98510．8659Rd310．5716．379490．601370．96891Rd410．5716．3794105．261370．96770．9957Ra110．0345．13178562．13180278318037．501800．99861Ra223．436．9218016．8217916．531089．1315750．8311477．601710．94330．9895Ra310．3340．5317952．331800．99791

The algorithm could create a satisfactory route only with a starting point and an ending point. The parallel runways usually have different IAF, and the arrival route will has different ending points correspondingly, so it can be considered as two independent arrival routes. After passing their own initial approach fix, aircraft will be assigned a landing runway dynamically by air traffic controller according to present operation situation, and this is beyond the airspace planning area. It should be noted that the route planning method is independent from runway-in-use.

(4) Algorithm iteration process

Fig.7　Convergence process of route optimization solution

As reported in Ref.[9], when four routes were optimized with A*algorithm, the optimization time was 43 s; while for 8 routes , the optimization time was 4 h. Obviously, search time is greatly affected by the number of routes,mainly because the large searching space can not constrain the new route search by optimized routes. Therefore, we divide the terminal airspace with MAKLINK line, and the route searching scope can be directly determined by the initial route. Thus, most routes can reach or approach the optimal solution in 300 iteration times. As shown in Fig.7, the algorithm running time is 63 s, and the efficiency is greatly improved without being affected by the number of routes to be optimized.

6　Conclusions

Arrival and departure routes planning is an important foundation for safety and efficiency of air traffic operations. A two-stage method is adopted to achieve the route network optimization and design: the path finding of individual route is realized first, and then individual route is optimized one by one.Finally, a route network is constructed according to the priority under the constraints of the previous optimization results. For the choice of individual route waypoints, a probabilistic searching method,working along the horizontal direction first and then the vertical direction,is presented.Therefore,the path search algorithm in 3D space can be realized with an improved ant-colony algorithm.

The terminal airspace model is constructed with visual diagram, which effectively reduces the search space. Therefore, the search efficiency of flight routes has heen greatly improved, and the problem that the search time increases significantly with the increase of route number in A*algorithm has been solved.

Our future work will focus on the convergence of multiple arrival routes. Arrival routes are generated in turns according to the principles of optimization sequence, but it is still necessary to be studied intensively that how the successive route joins into the previous ones.

Acknowledgements

This study was supported by the National Natural Science Foundation of China(No.61039001), the State Technology Supporting Plan(No.2011BAH24B08), and the Fundamental Research Funds for the Central Universities(No.ZXH2011A002).

[1]Tian Qingfei. Study on urban transit network generation and optimization based on complex network theory[D]. Changchun:Jilin University,2013:3-18. (in Chinese)

[2]Wang Wei, Yang Xinmiao, Chen Xuewu. Urban public transportation system planning method and management technology[M]. Beijing:Science Press, 2002:77-95. (in Chinese)

[3]Chen Xin. The strategy of optimization and planning for urban traffic network[D]. Wuhan:Huazhong University of Science and Technology, 2005. (in Chinese)

[4]Zhang Yongfang, Zhang An, Zhang Zhiyu. Planning algorithm of tactics flight path[J]. Journal of Traffic and Transportation Engineering, 2006, 6(4):84-87. (in Chinese)

[5]Beard R W, McLain T W, Goodrich M A, et al. Coordinated target assignment and intercept for unmanned air vehicles[J].IEEE Transactions on Robotics and Automation,2002,18(6):911-922.

[6]Zheng C, Li L, Xu F, et al. Evolutionary airline planner for unmanned air vehicles[J].IEEE Transactions on Robotics,2005,21(4):609-620.

[7]Chen S B, Jiang J P. Research on path planning and trajectory tracking of autonomous mobile robot[D]. Hangzhou:Zhejiang University,2008. (in Chinese)

[8]Gorbenko A, Popov V. Self-learning algorithm for visual recognition and object categorization for autonomous mobile robots[M]. Computer, Informatics, Cybernetics and Applications. Netherland:Springer, 2012: 1289-1295.

[9]Pfeil D M. Optimization of airport terminal-area air traffic operations under uncertain weather conditions [D].California,USA:University of California at Berkeley, 2011.

[10]Eurocontrol.Airspace concept handbook for the implementation of performance based navigation[EB/OL].(2013-12-10)[2015-12-22]．http://www.eurocontrol.int/sites/default/files/publication/files/hand-bo-ok-pbn-implement-2013-ed-3a.pdf.

[11]International Civil Aviation Organization. A-2-2:A-2-5—1996,DOC 8168-OPS/611 Air Navigation Service-Aircraft Operations[S]. China:ICAO Montreal,1996.(in Chinese)

[12]Wang Chao. Research on evaluation theory and simulation application of flight procedure Operation [D]. Nanjing:Nanjing University of Aeronautics and Astronautics,2012. (in Chinese)

[13]Wang Chao, Wang Fei. Multi-objective intelligent optimization of noise abatement departure trajectory[J]. Journal of Southwest Jiao tong University,2013,48(1):147-153. (in Chinese)

[14]Habib M K. Efficient method to generate collision free paths for autonomous mobile robot based on new free space structuring approach[J]. IEEE/RSJ International Workshop on Intelligent Robots and System, 1991, 91(6): 563-567.

[15]Baase S, Gelder A V. Computing algorithms[M]. Beijing: Higher Education Press,2001: 235-267.

[16]Xu Jingming, Cao Xianbing, Wang Xufa. Polymorphic ant colony algorithm[J]. Journal of University of Science and Technology of China, 2005, 35 (1): 59-65. (in Chinese)

(Executive Editor: Zhang Bei)

V355.1Document code:AArticle ID:1005-1120(2015)06-0654-11

*Corresponding author: Wang Chao, Associate Professor, E-mail: wangch6972@aliyun.com.

How to cite this article: Wang Chao, He Chaonan. Three-dimensional planning of arrival and departure route network based on improved ant-colony algorithm[J]. Trans. Nanjing U. Aero. Astro., 2015,32(6):654-664. http://dx.doi.org/10.16356/j.1005-1120.2015.06.654