基于改進DK算法繞飛限制區的航線規劃

摘 要：終端區內往往存在限制區，這些限制區的存在制約了飛行的流暢性，對于一些限制區可以提前向軍方申請，引用動態航路概念。繞飛終端區時綜合考慮航線長度、飛機性能等指標，選取航線經濟性最優為目標函數，實現繞飛限制區的航線網絡規劃。實例表明，算法運行穩定，效率明顯提高。

關鍵詞：終端區限制區；航線規劃；dijkstra算法

引言

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

1 限制區模型建立

二分法求解航線到限制區距離：

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

一點，并且經緯度是Y1，Y2的緯度中點。

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

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

2.1 帶權圖鄰接矩陣

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

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

2.2 算法步驟

上面已經給出了帶權圖鄰接矩陣的定義，可以用帶權圖鄰接矩陣求任意兩點間的距離。

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

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

3 實例仿真

3.1 定義限制區類型

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

3.2 實例分析

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

3.3 算法比較

基于改進的dijkstra算法與傳統dijkstra算法的比較：

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

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

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

（3）算法的時間復雜度由原來的O（N2）降至O（N（logN+E）），并且隨著網格中的節點數和邊數的增多，改進的dijkstra算法優勢越明顯。

4 結束語

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

參考文獻

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

[3]周蕊.終端區空域規劃若干問題的研究[J].

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

[5]劉衛國.Matlab程序設計與應用[J].