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