基于改進DK算法繞飛限制區(qū)的航線規(guī)劃

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

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

引言

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

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

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

如圖1所示，OA存在極小值，因為等角航線的曲率小于圓形空域的曲率所以極小值是唯一的?？梢杂脭?shù)值解法求出近似值。這里選用改進的二分法直接求出OA的最小值如圖所示。Y1（？準1，？姿1），Y2（？準2，？姿2）。先求？準1和？準2的均值？準3=？準1+？準2/2 由公式：

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

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

2 求解任意兩點間最短路徑模型

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

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

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

2.2 算法步驟

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

設A=（aij）n×k，B=（bij）k×m，定義Q=A？茚B=（qij）n×m其中qij=min{aij，bij}，現(xiàn)在討論鄰接矩陣應用這兩種運算所產(chǎn)生的結(jié)果。討論帶權(quán)無向圖的情形。設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é)點i到節(jié)點j的路徑長度，ai2+aj2表示經(jīng)過中間點2到結(jié)點j的路徑長度，其余相類似，都表示從結(jié)點I到節(jié)點j的路徑長度，aij（2）是取它們的最小值，它們的意義就是從結(jié)點I最多經(jīng)過一個中間點到達結(jié)點j的所有路徑中長度最短的那條路徑。

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

3 實例仿真

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

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

3.2 實例分析

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

3.3 算法比較

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

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

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

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

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

4 結(jié)束語

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

參考文獻

[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]賀超男，王超，姜玉琴.基于改進算法的進離場航線網(wǎng)絡3D規(guī)劃[J].

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

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

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