基于几何算法的空中交通改航路径规划

1、 文章编号:100124098(20080820037204基于几何算法的空中交通改航路径规划李雄1,徐肖豪2,朱承元2,李冬宾1(1.南京航空航天大学民航学院,江苏南京210016;2.中国民航大学空中交通管理学院,天津300300摘要:为解决空中交通流量管理中恶劣天气或流量受限下的航班改航问题,提出了基于几何算法的改航路径规划方法。首先,将几何算法应用于航班改航路径的规划研究,给出了初始改航点的确定方法。然后,从实际可操作性出发,分别给出了在转弯角度、航段距离和改航点数量限制下的改航路径修正方法。最后,运用本文提出的方法对我国西南雷暴多发地区的改航路径进行了研究。研究结果表明:本文提出的改

2、航路径规划方法可安全有效的避开飞行受限区域,算法简单可行。关键词:空中交通管理;路径规划;几何算法;改航中图分类号:V 355文献标识码:A1引言改航飞行是指在某些空域或航路受特殊情况影响而无法正常使用的情况下(如恶劣天气、导航设备失效、航线容量饱和等,安排航空器临时选择一条不受影响的航线绕过飞行受限区域的飞行。实施改航飞行可有效地解决日益严重的航班延误问题,提高空域的利用率。对改航问题的研究最早开始于1993年,具有代表性的算法主要有:基于网格的航线搜索算法1-3。该方法将改航区域划分为X Y 个网格,应用D ijk stra 或Bell m an 2Ford 算法搜索最短飞行路径。但算法复

3、杂度较大,当网格数目较多时搜索速度慢,无法满足实时性要求。基于已有航路点的A 3搜索算法4。该方法在计划航线周围选取未受影响的航路点,运用A 3算法搜索最短飞行路径。其缺点在于对航线结构依赖性强,在流量拥塞空域或航路点稀疏空域不易找到理想的改航路径。基于自由飞行的航线搜索算法5。该方法借鉴飞行冲突探测和解脱思想,将飞行受限区域等同于飞行冲突进行避让,但只考虑了单个航班的避让路径不利于全局优化和实际空管指挥。基于多边形的航线搜索算法6。该方法根据飞行受限区的形状,运用几何算法适量选取改航点,规划出改航路径。运用该方法得到的改航路径结构简单,适用性强,但不足之处在于未考虑实际飞行性能和空管工作负荷

4、等因素对改航路径的约束。本文在借鉴文献6和机器人避障领域相关算法7-8的基础上,考虑了空中交通管制程序和航空器飞行性能对改航路径的约束,提出了基于几何算法的改航路径规划方法,并以我国西南雷暴多发地区的改航问题为例验证了该方法的有效性。2初始改航点的确定出于安全因素的考虑,航班改航通常从侧向绕过影响飞行安全的区域9-10,即假设在该区域内各高度层均禁用。因此,飞行改航区(fl ow constrained area ,FCA 以2维简单多边形方式表示11,航空器不得穿越该区域飞行。航班在空中的飞行路线由沿航线方向的不同航路点组成,设某航班的固定航线为F ,由航路点f 1,f 2,f N 组成,受

5、恶劣天气影响而无法正常飞行。针对需要改航飞行的航班建立相应的直角坐标系x oy ,其中坐标原点为改航航班的起飞机场,y 轴正方向为磁北,x 轴正方向为磁北偏东90.设FCA 各顶点为p i (x i ,y i ,i =1,2,n ,为了易于理解,以图1所示FCA 及航线为例,改航点位置的确定方法为:步骤1:确定飞行改航区边界与航线的交汇点。沿航线方向最先与FCA 边界相交的点为飞入交汇点,q e (x e ,y e ;另一交汇点为飞出交汇点,q l (x l ,y l 。若航线与FCA边界重合则认为该段航线在FCA 之外,未受飞行改航区的影响。第26卷第8期(总第176期系统工程V ol .2

6、6,N o .82008年8月Syste m s Engineering A ug .,2008收稿日期:2008206230基金项目:国家“863”计划资助项目(20060112A 1033作者简介:李雄(19802,男,天津人,南京航空航天大学民航学院博士研究生,研究方向:空中交通规划与流量管理。步骤2:确定改航航段起始点q o和终结点q f.在f1, f2,f N中选取距离q e最近,且在FCA之外的航路点定义为q o,q o=f io;选取距离q l最近,且在FCA之外的航路点定义为q f,q f=f if.定义q e q l的中点q m.步骤3:q e q l将FCA分为两部分,将分

7、属两部分的顶点分别放入集合P r和P l.判断方法为:将各顶点带入q e q l 直线的一般方程,如果大于0则顶点属于P r,反之属于P l.如图1中,P r=p2,p3,p4;P l=p1,p5,p6。步骤4:在P r与P l中分别搜索距点q m最远的点(如图1中p4和p5,并分别将此距离记为d r、d l,选取r m in= m ind r,d l。图1初始改航点的确定步骤5:过q m,在r m in所在一侧(p5所在一侧,作垂直于q e q l的射线l.以q m为圆心r m in为半径作弧,与射线l的交点q r(x r,y r,即为所求改航点,其坐标值可由式(1得出。原先由q o飞往q

8、f的航段,改为由q o经q r飞往q f.x r=-k r(-b r(k2r+1y r=+k2rb r(k2r+1 (1式中:k r=(y l-y e (x l-x e,=(x l y e-x e y l (x l-x e,=(x2l+y2l-x2e-y2e 2(y l-y e,b r=k2r+1 r m in.若x l=x e,则x r=x er m in,y r=(y e+y l 2;若y l=y e,则x r=(x e+x l 2,y r=y er m in.当q r在点集P r一侧,则b r和r m in取“+”号;当q r在点集P l一侧,则b r和r m in取“-”号。在特殊情况

9、下,若P r或P l中只存在一个顶点,且该顶点与q m的距离等于r m in,则该顶点即为改航点q r.步骤6:若改航航段q o q r(或q r q f与FCA边界相交,则需在q o q r(或q r q f间增加新的改航点。其方法为,将q r 转化为新的q f(或q o,回步骤3,直至新的改航路径不穿越FCA。通过上述方法,可得到由f io经一个或多个改航点至f if 的初步改航路径。3改航点的修正航班实施改航飞行需要考虑空中交通管制程序和航空器飞行性能的相关约束3,主要包括:转弯角度、航段距离和改航点数量。3.1转弯角度约束雷达管制条件下,出于航路飞行安全因素考虑,在绕飞危险天气区域时航

10、向的最大改变量通常小于90,即转弯角度H C90.因此,若改航路径中存在H C90的改航点,可通过如下方法进行调整:方法1:在航线航路点f i中重新选择改航航段起始点qo和终结点qf,使其满足最大转弯角度的约束(图2(a。令qo=f io-i o,qf=f i f+i f,且满足i o-i o1,i f+i fN,i o,i f=0,1,N-2,i o或i f通常取1。方法2:当改航点q ri+1的转弯角度大于90时(图2(b,过q ri+1作平行于q riq ri+2的直线,在q ri+1的两侧分别确定新的改航点qri+1和qri+1,使其满足最大转弯角度的约束,同时qri+1qri+1的长

11、度l SD(qri+1,qri+1应满足最小航段距离的约束。qri+1和qri+1的坐标值可由式(2和(3分别求出。xri+1=x ri+1-l SD2k2ri,r i+2+1yri+1=y ri+1-l SD k ri,r i+22k2ri,r i+2+1(2xri+1=x ri+1+l SD2k2ri,r i+2+1yri+1=y ri+1+l SD k ri,r i+22k2ri,r i+2+1(3式中:k ri,r i+2=(y r i+2-y r i (x r i+2-x r i,若x r i+2=x r i,则xri+1=xri+1=x ri,yri+1=y ri+1-l SD 2

12、,yr i+1=y ri+1+l SD 2。图2改航点位置修正3.2航段距离约束航段距离(lSD指两个转弯点(改航点或航路点之间83系统工程2008年 的距离,其长度应满足在该距离内航空器可顺利完成2次转弯(H C 90方法1:在航线航路点f i 中重新选择航段起始点q o和终结点q f (图2(a ,其调整方法与3.1节方法1相似,l SD (q o ,q r 和l SD (q f ,q r 应满足最短航段距离的约束。方法2:当存在多个改航点时,如图2(c 所示,l SD (q r i +1,q r i +290,需进行修正。图4昆明2广州航线改航路径规划93第8期李雄,徐肖豪等:基于几何算

13、法的空中交通改航路径规划修正后的改航路径,如图4(b所示。重新确定改航航段的终结点q f为BSE,改航路径为L X I2q r11的坐标为(257.62,-18.33。调整后新的改航路径符合转弯角度、航段距离和改航点数量的约束。本文应用几何算法研究了恶劣天气、流量受限等情况下的航班改航路径规划问题,给出了初始改航点的确定方法。考虑了改航飞行中的空中交通管制程序和航空器性能,给出了转弯角度、航段距离和改航点数量约束下的改航路径修正方法。本算法为全局规划方法,根据飞行改航区各个顶点的位置,规划出的改航路径可满足绝大多数情况下的改航需求。算法的时间复杂度为改航区顶点的线性阶,能满足实时性的要求。实例

14、分析验证了本文提出的改航路径规划方法的有效性和可操作性,在空中交通流量管理改航问题中有较强的应用价值。参考文献:1D ixon M,et al.A utom ated aircraft routing th roughw eather2i m pacted airs paceA.F ifth internati onal Conference on A viati on W eather Syste m sC.V ienna,VA,1993:295298.2K rozel J,W eidner T,H unter G.T er m inal areaguidance incorporating

15、 heavy w eatherA.A I A AGuidance,N avigati on,and Control ConferenceC.N e w O rleans,LA,1997:411421.3K rozel J,L ee C,M itchell J S B.E sti m ating ti m eof arrival in heavy w eather conditi onsA.A I A AGuidance,N avigati on,and Control ConferenceC.Portland,OR,1999:14811495.4宋柯.空中交通流量管理改航策略初步研究D.南京:

16、南京航空航天大学,2002.5K rozel J,et al.Comparis on of algorithm s for synthe2sizing w eather avoidance routes in transiti on airs paceA.A I A A Guidance,N avigati on,and ControlConferenceC.P rovidence,R I,2004:116.6Sridhar B,et al.Integrati on of traffic fl ow m anage2m ent decisi onsA.A I A A Guidance,N av

17、igati on,andControl ConferenceC.M onterey,California,2002:19.7何利等.基于几何学的路径规划方法J.哈尔滨工业大学学报,2005,37(7:947949.8庄惠忠,杜树新,吴铁军.机器人路径规划及相关算法研究J.科技通报,2004,20(3:210215.9L oveW,et al.A ssess m ent of p redicti on error i m pacton res oluti ons for aircraft and severe w eather avoid2 anceA.A I A A4th T echnol o

18、gy,Integrati on,andOperati ons ForumC.Ch icago,I L,2004:110. 10李春生.雷暴航空飞行的天敌J.空中交通管理,2006,1:2839.11L i X,et al.E stablishm ent of fligh t rerouting areaand air route p lanning based on convey polygonA.2008Ch inese Control and D ecisi on ConferenceC.Yantai,2008:29993004.A i r Traff i c Reroute Plann

19、i n g ba sed on Geo m etry A lgor ith mL I X i ong1,XU X iao2hao2,ZHU Cheng2yuan2,L IDong2bin1(1.College of C ivil A viati on,N anjing U niversity of A eronautics and A stronautics,N anjing210016,Ch ina;2.College of A ir T raffic M anage m ent,C ivil A viati on U niversity of Ch ina,T ianjin300300,Ch inaAbstract:To s olve the reroute p roble m of air traffic fl ow m anage m ent in severe w eather or fl ow constrained areas,a ne w rerouting m ethod based on geom etry algorithm is p roposed.F irst,the geom etry algorithm is int