基于幾何算法的空中交通改航路徑規(guī)劃

1、 文章編號(hào):100124098(20080820037204基于幾何算法的空中交通改航路徑規(guī)劃李雄1,徐肖豪2,朱承元2,李冬賓1(1.南京航空航天大學(xué)民航學(xué)院,江蘇南京210016;2.中國民航大學(xué)空中交通管理學(xué)院,天津300300摘要:為解決空中交通流量管理中惡劣天氣或流量受限下的航班改航問題,提出了基于幾何算法的改航路徑規(guī)劃方法。首先,將幾何算法應(yīng)用于航班改航路徑的規(guī)劃研究,給出了初始改航點(diǎn)的確定方法。然后,從實(shí)際可操作性出發(fā),分別給出了在轉(zhuǎn)彎角度、航段距離和改航點(diǎn)數(shù)量限制下的改航路徑修正方法。最后,運(yùn)用本文提出的方法對我國西南雷暴多發(fā)地區(qū)的改航路徑進(jìn)行了研究。研究結(jié)果表明:本文提出的改

2、航路徑規(guī)劃方法可安全有效的避開飛行受限區(qū)域,算法簡單可行。關(guān)鍵詞:空中交通管理;路徑規(guī)劃;幾何算法;改航中圖分類號(hào):V 355文獻(xiàn)標(biāo)識(shí)碼:A1引言改航飛行是指在某些空域或航路受特殊情況影響而無法正常使用的情況下(如惡劣天氣、導(dǎo)航設(shè)備失效、航線容量飽和等,安排航空器臨時(shí)選擇一條不受影響的航線繞過飛行受限區(qū)域的飛行。實(shí)施改航飛行可有效地解決日益嚴(yán)重的航班延誤問題,提高空域的利用率。對改航問題的研究最早開始于1993年,具有代表性的算法主要有:基于網(wǎng)格的航線搜索算法1-3。該方法將改航區(qū)域劃分為X Y 個(gè)網(wǎng)格,應(yīng)用D ijk stra 或Bell m an 2Ford 算法搜索最短飛行路徑。但算法復(fù)

3、雜度較大,當(dāng)網(wǎng)格數(shù)目較多時(shí)搜索速度慢,無法滿足實(shí)時(shí)性要求?；谝延泻铰伏c(diǎn)的A 3搜索算法4。該方法在計(jì)劃航線周圍選取未受影響的航路點(diǎn),運(yùn)用A 3算法搜索最短飛行路徑。其缺點(diǎn)在于對航線結(jié)構(gòu)依賴性強(qiáng),在流量擁塞空域或航路點(diǎn)稀疏空域不易找到理想的改航路徑?；谧杂娠w行的航線搜索算法5。該方法借鑒飛行沖突探測和解脫思想,將飛行受限區(qū)域等同于飛行沖突進(jìn)行避讓,但只考慮了單個(gè)航班的避讓路徑不利于全局優(yōu)化和實(shí)際空管指揮?；诙噙呅蔚暮骄€搜索算法6。該方法根據(jù)飛行受限區(qū)的形狀,運(yùn)用幾何算法適量選取改航點(diǎn),規(guī)劃出改航路徑。運(yùn)用該方法得到的改航路徑結(jié)構(gòu)簡單,適用性強(qiáng),但不足之處在于未考慮實(shí)際飛行性能和空管工作負(fù)荷

4、等因素對改航路徑的約束。本文在借鑒文獻(xiàn)6和機(jī)器人避障領(lǐng)域相關(guān)算法7-8的基礎(chǔ)上,考慮了空中交通管制程序和航空器飛行性能對改航路徑的約束,提出了基于幾何算法的改航路徑規(guī)劃方法,并以我國西南雷暴多發(fā)地區(qū)的改航問題為例驗(yàn)證了該方法的有效性。2初始改航點(diǎn)的確定出于安全因素的考慮,航班改航通常從側(cè)向繞過影響飛行安全的區(qū)域9-10,即假設(shè)在該區(qū)域內(nèi)各高度層均禁用。因此,飛行改航區(qū)(fl ow constrained area ,FCA 以2維簡單多邊形方式表示11,航空器不得穿越該區(qū)域飛行。航班在空中的飛行路線由沿航線方向的不同航路點(diǎn)組成,設(shè)某航班的固定航線為F ,由航路點(diǎn)f 1,f 2,f N 組成,受

5、惡劣天氣影響而無法正常飛行。針對需要改航飛行的航班建立相應(yīng)的直角坐標(biāo)系x oy ,其中坐標(biāo)原點(diǎn)為改航航班的起飛機(jī)場,y 軸正方向?yàn)榇疟?x 軸正方向?yàn)榇疟逼珫|90.設(shè)FCA 各頂點(diǎn)為p i (x i ,y i ,i =1,2,n ,為了易于理解,以圖1所示FCA 及航線為例,改航點(diǎn)位置的確定方法為:步驟1:確定飛行改航區(qū)邊界與航線的交匯點(diǎn)。沿航線方向最先與FCA 邊界相交的點(diǎn)為飛入交匯點(diǎn),q e (x e ,y e ;另一交匯點(diǎn)為飛出交匯點(diǎn),q l (x l ,y l 。若航線與FCA邊界重合則認(rèn)為該段航線在FCA 之外,未受飛行改航區(qū)的影響。第26卷第8期(總第176期系統(tǒng)工程V ol .2

6、6,N o .82008年8月Syste m s Engineering A ug .,2008收稿日期:2008206230基金項(xiàng)目:國家“863”計(jì)劃資助項(xiàng)目(20060112A 1033作者簡介:李雄(19802,男,天津人,南京航空航天大學(xué)民航學(xué)院博士研究生,研究方向:空中交通規(guī)劃與流量管理。步驟2:確定改航航段起始點(diǎn)q o和終結(jié)點(diǎn)q f.在f1, f2,f N中選取距離q e最近,且在FCA之外的航路點(diǎn)定義為q o,q o=f io;選取距離q l最近,且在FCA之外的航路點(diǎn)定義為q f,q f=f if.定義q e q l的中點(diǎn)q m.步驟3:q e q l將FCA分為兩部分,將分

7、屬兩部分的頂點(diǎn)分別放入集合P r和P l.判斷方法為:將各頂點(diǎn)帶入q e q l 直線的一般方程,如果大于0則頂點(diǎn)屬于P r,反之屬于P l.如圖1中,P r=p2,p3,p4;P l=p1,p5,p6。步驟4:在P r與P l中分別搜索距點(diǎn)q m最遠(yuǎn)的點(diǎn)(如圖1中p4和p5,并分別將此距離記為d r、d l,選取r m in= m ind r,d l。圖1初始改航點(diǎn)的確定步驟5:過q m,在r m in所在一側(cè)(p5所在一側(cè),作垂直于q e q l的射線l.以q m為圓心r m in為半徑作弧,與射線l的交點(diǎn)q r(x r,y r,即為所求改航點(diǎn),其坐標(biāo)值可由式(1得出。原先由q o飛往q

8、f的航段,改為由q o經(jīng)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.當(dāng)q r在點(diǎn)集P r一側(cè),則b r和r m in取“+”號(hào);當(dāng)q r在點(diǎn)集P l一側(cè),則b r和r m in取“-”號(hào)。在特殊情況

9、下,若P r或P l中只存在一個(gè)頂點(diǎn),且該頂點(diǎn)與q m的距離等于r m in,則該頂點(diǎn)即為改航點(diǎn)q r.步驟6:若改航航段q o q r(或q r q f與FCA邊界相交,則需在q o q r(或q r q f間增加新的改航點(diǎn)。其方法為,將q r 轉(zhuǎn)化為新的q f(或q o,回步驟3,直至新的改航路徑不穿越FCA。通過上述方法,可得到由f io經(jīng)一個(gè)或多個(gè)改航點(diǎn)至f if 的初步改航路徑。3改航點(diǎn)的修正航班實(shí)施改航飛行需要考慮空中交通管制程序和航空器飛行性能的相關(guān)約束3,主要包括:轉(zhuǎn)彎角度、航段距離和改航點(diǎn)數(shù)量。3.1轉(zhuǎn)彎角度約束雷達(dá)管制條件下,出于航路飛行安全因素考慮,在繞飛危險(xiǎn)天氣區(qū)域時(shí)航

10、向的最大改變量通常小于90,即轉(zhuǎn)彎角度H C90.因此,若改航路徑中存在H C90的改航點(diǎn),可通過如下方法進(jìn)行調(diào)整:方法1:在航線航路點(diǎn)f i中重新選擇改航航段起始點(diǎn)qo和終結(jié)點(diǎn)qf,使其滿足最大轉(zhuǎn)彎角度的約束(圖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:當(dāng)改航點(diǎn)q ri+1的轉(zhuǎn)彎角度大于90時(shí)(圖2(b,過q ri+1作平行于q riq ri+2的直線,在q ri+1的兩側(cè)分別確定新的改航點(diǎn)qri+1和qri+1,使其滿足最大轉(zhuǎn)彎角度的約束,同時(shí)qri+1qri+1的長

11、度l SD(qri+1,qri+1應(yīng)滿足最小航段距離的約束。qri+1和qri+1的坐標(biāo)值可由式(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改航點(diǎn)位置修正3.2航段距離約束航段距離(lSD指兩個(gè)轉(zhuǎn)彎點(diǎn)(改航點(diǎn)或航路點(diǎn)之間83系統(tǒng)工程2008年 的距離,其長度應(yīng)滿足在該距離內(nèi)航空器可順利完成2次轉(zhuǎn)彎(H C 90方法1:在航線航路點(diǎn)f i 中重新選擇航段起始點(diǎn)q o和終結(jié)點(diǎn)q f (圖2(a ,其調(diào)整方法與3.1節(jié)方法1相似,l SD (q o ,q r 和l SD (q f ,q r 應(yīng)滿足最短航段距離的約束。方法2:當(dāng)存在多個(gè)改航點(diǎn)時(shí),如圖2(c 所示,l SD (q r i +1,q r i +290,需進(jìn)行修正。圖4昆明2廣州航線改航路徑規(guī)劃93第8期李雄,徐肖豪等:基于幾何算

13、法的空中交通改航路徑規(guī)劃修正后的改航路徑,如圖4(b所示。重新確定改航航段的終結(jié)點(diǎn)q f為BSE,改航路徑為L X I2q r11的坐標(biāo)為(257.62,-18.33。調(diào)整后新的改航路徑符合轉(zhuǎn)彎角度、航段距離和改航點(diǎn)數(shù)量的約束。本文應(yīng)用幾何算法研究了惡劣天氣、流量受限等情況下的航班改航路徑規(guī)劃問題,給出了初始改航點(diǎn)的確定方法。考慮了改航飛行中的空中交通管制程序和航空器性能,給出了轉(zhuǎn)彎角度、航段距離和改航點(diǎn)數(shù)量約束下的改航路徑修正方法。本算法為全局規(guī)劃方法,根據(jù)飛行改航區(qū)各個(gè)頂點(diǎn)的位置,規(guī)劃出的改航路徑可滿足絕大多數(shù)情況下的改航需求。算法的時(shí)間復(fù)雜度為改航區(qū)頂點(diǎn)的線性階,能滿足實(shí)時(shí)性的要求。實(shí)例

14、分析驗(yàn)證了本文提出的改航路徑規(guī)劃方法的有效性和可操作性,在空中交通流量管理改航問題中有較強(qiáng)的應(yīng)用價(jià)值。參考文獻(xiàn):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、南京航空航天大學(xué),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何利等.基于幾何學(xué)的路徑規(guī)劃方法J.哈爾濱工業(yè)大學(xué)學(xué)報(bào),2005,37(7:947949.8莊惠忠,杜樹新,吳鐵軍.機(jī)器人路徑規(guī)劃及相關(guān)算法研究J.科技通報(bào),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