摘 要：終端區(qū)內(nèi)往往存在限制區(qū)，這些限制區(qū)的存在制約了飛行的流暢性，對于一些限制區(qū)可以提前向軍方申請，引用動態(tài)航路概念。繞飛終端區(qū)時綜合考慮航線長度、飛機(jī)性能等指標(biāo)，選取航線經(jīng)濟(jì)性最優(yōu)為目標(biāo)函數(shù)，實(shí)現(xiàn)繞飛限制區(qū)的航線網(wǎng)絡(luò)規(guī)劃。實(shí)例表明，算法運(yùn)行穩(wěn)定，效率明顯提高。

關(guān)鍵詞：終端區(qū)限制區(qū)；航線規(guī)劃；dijkstra算法

引言

終端區(qū)內(nèi)航線網(wǎng)絡(luò)是連接機(jī)場和航路的重要機(jī)構(gòu)，但是目前國內(nèi)的終端區(qū)航線規(guī)劃是基于機(jī)場布局，導(dǎo)航設(shè)施和限制區(qū)進(jìn)行人工設(shè)計，這樣的設(shè)計方法顯然存在著效率較低，設(shè)計方案缺乏科學(xué)驗(yàn)證等問題。文章重點(diǎn)是將航線自動生成映射到圖論中的最短路徑問題，引用dijkstra算法搜索出最優(yōu)航線，引用終端區(qū)動態(tài)航路概念，通過終端區(qū)內(nèi)限制區(qū)的航路即為條件航路，無論是軍方還是民航，都不是永久和長期的使用條件航路，但可以在需要時候申請得到使用權(quán)，以減輕終端區(qū)航路擁堵。

1 限制區(qū)模型建立

二分法求解航線到限制區(qū)距離：

如圖1所示，OA存在極小值，因?yàn)榈冉呛骄€的曲率小于圓形空域的曲率所以極小值是唯一的?？梢杂脭?shù)值解法求出近似值。這里選用改進(jìn)的二分法直接求出OA的最小值如圖所示。Y1（？準(zhǔn)1，？姿1），Y2（？準(zhǔn)2，？姿2）。先求？準(zhǔn)1和？準(zhǔn)2的均值？準(zhǔn)3=？準(zhǔn)1+？準(zhǔn)2/2 由公式：

一點(diǎn)，并且經(jīng)緯度是Y1，Y2的緯度中點(diǎn)。

計算OY和OY2的距離，判斷OY1，OY2的大小。如果OY1？芏OY2則選擇點(diǎn)Y2和點(diǎn)Y3重復(fù)上述步驟，求點(diǎn)Y2Y3的中點(diǎn)Y4，計算OY2和OY3的大小，可以看出這樣迭代下去是YN收斂于A點(diǎn)。

2 求解任意兩點(diǎn)間最短路徑模型

2.1 帶權(quán)圖鄰接矩陣

定義（帶權(quán)有向圖的鄰接矩陣）設(shè)G=（V，E）是一個簡單帶權(quán)的有向圖，V={v1，v2......vn}，則G的連接矩陣A=（Aij）是一個n階方陣，其中：

如表2所示，1到16共16個點(diǎn)，在matlab中用M代替∞這里取M=10000，又由于表1各相鄰點(diǎn)的距離都相等，這里取w=1，則表1對應(yīng)的鄰接矩陣如下：

2.2 算法步驟

上面已經(jīng)給出了帶權(quán)圖鄰接矩陣的定義，可以用帶權(quán)圖鄰接矩陣求任意兩點(diǎn)間的距離。

設(shè)A=（aij）n×k，B=（bij）k×m，定義Q=A？茚B=（qij）n×m其中qij=min{aij，bij}，現(xiàn)在討論鄰接矩陣應(yīng)用這兩種運(yùn)算所產(chǎn)生的結(jié)果。討論帶權(quán)無向圖的情形。設(shè)A=（aij）n×n是帶權(quán)無向圖G=（V，E）的鄰接矩陣，記A（2）=A*A=（aij2）n×n，則有：aij（2）=min{ai1+a1j，ai2+a2j，......，ain+anj}這里的ai1+aj1表示從結(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑長度，ai2+aj2表示經(jīng)過中間點(diǎn)2到結(jié)點(diǎn)j的路徑長度，其余相類似，都表示從結(jié)點(diǎn)I到節(jié)點(diǎn)j的路徑長度，aij（2）是取它們的最小值，它們的意義就是從結(jié)點(diǎn)I最多經(jīng)過一個中間點(diǎn)到達(dá)結(jié)點(diǎn)j的所有路徑中長度最短的那條路徑。

所以最多經(jīng)過一個中間點(diǎn)是因?yàn)橐话沩?xiàng)aij+akj（1？燮k？燮n）中也包含aii+aij和aii+ajj兩項(xiàng)，他們都等于aij，如果他是所有項(xiàng)中的最小值，則aij（2）=aij，在這種情況下就沒有經(jīng)過中間點(diǎn)。同理可知，在A（k）=aij（k）m×n中，aij（k）表示從結(jié)點(diǎn)i最多經(jīng)過（k-1）個中間點(diǎn)的到結(jié)點(diǎn)j的所有路徑中最短的那條路徑，即最短路徑。

3 實(shí)例仿真

3.1 定義限制區(qū)類型

終端區(qū)中常常出現(xiàn)限制區(qū)，在我國，按照地面目標(biāo)性質(zhì)，可以將空中限制區(qū)分為民用和軍用兩種。民用限制區(qū)是在重要城市，經(jīng)濟(jì)等目標(biāo)上空劃定的空中限制區(qū)。軍事限制區(qū)是在軍事要地，兵器試驗(yàn)場上空和航空部隊，飛行院校等航空單位的機(jī)場飛行空域規(guī)劃的空中限制區(qū)。按照使用期限可以分為固定限制區(qū)和臨時限制區(qū)。將固定限制區(qū)定義為A型限制區(qū)，將臨時限制區(qū)定義為B型限制區(qū)，對于A型限制區(qū)來說，一般采取繞飛的形式。對于B型限制區(qū)可以提前和軍方申請，經(jīng)軍方批準(zhǔn)開放后，就可以在此空域內(nèi)飛行。

3.2 實(shí)例分析

以S機(jī)場07L跑道為例，驗(yàn)證進(jìn)基于dijkstra算法的進(jìn)離場航線規(guī)劃方法。如圖2所示，終端區(qū)內(nèi)分布3個高大的限制區(qū)：R501，R502，R503。選擇規(guī)劃航線起止點(diǎn)，選擇航線Rd1，起始點(diǎn)ABTUB，終止點(diǎn)AGTIS，

3.3 算法比較

基于改進(jìn)的dijkstra算法與傳統(tǒng)dijkstra算法的比較：

（1）使用臨界表來高效存儲網(wǎng)絡(luò)數(shù)據(jù)信息，存儲空間由原來的N×N量級減少到N量級。

（2）每個節(jié)點(diǎn)從源節(jié)點(diǎn)沿著最佳路徑到本節(jié)點(diǎn)的距離來標(biāo)注，

隨著算法的進(jìn)行，標(biāo)注也不斷改變，使之反映較好的路徑。但發(fā)現(xiàn)標(biāo)注代表了從源節(jié)點(diǎn)到該節(jié)點(diǎn)的最短可能路徑時，就使它成為永久性的，不再進(jìn)行修改。

（3）算法的時間復(fù)雜度由原來的O（N2）降至O（N（logN+E）），并且隨著網(wǎng)格中的節(jié)點(diǎn)數(shù)和邊數(shù)的增多，改進(jìn)的dijkstra算法優(yōu)勢越明顯。

4 結(jié)束語

終端區(qū)航線及其網(wǎng)絡(luò)規(guī)劃是空中交通運(yùn)行安全和效率的重要基礎(chǔ)，文章采用二分法求解航線到限制區(qū)的距離，并基于改進(jìn)dijkstra算法用MATLAB仿真出最優(yōu)路徑，引用終端區(qū)動態(tài)航路概念，有效的減少了終端區(qū)航路擁擠的問題。

參考文獻(xiàn)

[1]Zheng C，Li L，Xu F，et al. Evolutionary Route Planner forUnmanned Air Vehicles[J].IEEE Transactions on Robotics，2005，21（4）：609-620.

[2]賀超男，王超，姜玉琴.基于改進(jìn)算法的進(jìn)離場航線網(wǎng)絡(luò)3D規(guī)劃[J].

[3]周蕊.終端區(qū)空域規(guī)劃若干問題的研究[J].

[4]米糧川.基于最優(yōu)搜索算法的自動航線生成[J].

[5]劉衛(wèi)國.Matlab程序設(shè)計與應(yīng)用[J].