自由航線規劃技術與算法研究

劉芊池 皮晚晴 楊坤奇 寇云凱 周 航

中國民航大學中歐航空工程師學院 天津 300300

1 概述

自由航線空域(Free Route Airspace，FRA)是指在一定的空域內，航空器可以自由地選擇飛行路線，允許飛機選擇其最直接的(或最優的)飛行航線，而不是按照規定的飛機航線飛行。航空器可實時根據飛行環境改變航線，達到減少飛行時間與航空公司運營成本，降低航空器燃油消耗，減少污染物排放的目的。自由航線空域的概念是美國聯邦空管局在1994年為了提升空域容量并解決航線擁堵的問題提出的構想[1]。此外，自由航線空域也是歐洲單一天空計劃的重要組成部分[2]。因此，實施FRA計劃的地區可同時優化整片空域的航路航線，在出現極端天氣情況或軍航活動時，動態地優化航線網絡能充分利用空域資源，有效避免限制區域，是增強民航運輸科學性、經濟型、安全性的有效手段。國內民航業起步較晚，自由航線及其優化的相關項目并未實施。未來，我國將成為世界第一航空運輸大國[3]。因此，可預見自由航線在我國實施，以提高空域利用率，適應民航業的發展要求。

目前，針對自由航線優化問題的相關研究一直非?；钴S，形成了新的研究熱點。2001年，Jardin等[4]首先提出基于最近鄰算法的特定風速下水平飛行的航空器航線優化。后來又出現了兩類優化方法：一類是包括建立離散網絡的航線優化方法，例如，A-star算法[5]和Dijkstra算法[6]，這類方法一般被認為是解決路徑優化問題(Path Optimization Problem，POP)的最優方法；另一類方法類似于Farin[7]發明的前傳播法，例如，水平設置法、快速行進法、有序逆風法等。

文中使用了一種漣漪擴散算法(Ripple-Spreading Algorithm，RSA)[8]來解決自由航線空域中的航線優化問題。在動態空域模型中，變化的氣流速度、移動的惡劣天氣區域、禁飛區等將作為影響因素。RSA算法對于動態環境的路線優化十分有效，通過單次運算即可以獲得最佳路線。本文將介紹基于漣漪擴散算法的動態空域下的自由航線優化模型與算法，并通過模擬測試驗證方法的有效性。

本文結構如下所述，第二部分針對單機高空巡航飛行的問題，建立自由航線優化問題的數學模型；第三部分應用動態加權路網中的漣漪擴散算法；第四部分通過仿真實驗說明該方法的有效性；第五部分為本文總結。

2 數學模型

2.1 問題描述

本項研究是研究優化飛機自由航路的模型和方法。在這里只研究飛機從給定的出發位置到目的地位置的巡航過程。首先，假定飛機以一個恒定的真空速(true airspeed，TAS)在一個固定的飛行高度(FL)巡航，此時飛機的地速為：

其中(x，y)是飛機的位置坐標，va是真空速，θa是飛機的航向，vw是風速，θw是風向，他們的關系如圖1所示。

圖1 地速、真空速和風速的矢量

目的是找到最優路徑，也就是使飛機飛行時間最短的路徑。因為飛機飛行的真空速TAS是常數，所以這條路線也代表著飛機所消耗的燃料最少。在考慮隨時間變化的惡劣天氣地區后，飛機飛行的優化路線可以描述為一個最小化問題。

其中t1代表飛機的起飛時間，tr代表飛機到達目的地的時間，(xi，yi)代表起飛位置，(xf，yf)代表飛機的目的地位置，Rp(t)因不利因素需要繞行的地區，共有Nr個。

2.2 自由航線

為模擬自由航路問題，本文建立了一個基本的路網模型G(V，L)，其中主要包含兩個參量，分別是節點集合V和鏈接集合L，節點集合可表示為V={Vi}i∈[1，Nnode]，包含Nnode個節點，而這些節點之間的連接集合L可表示為L={Lj}j∈[1，Nlink]。首先，rmax和θd分別表示飛機起飛位置(xi，yi)到目的地位置(xf，yf)的距離和方向角，選擇一個角度θ∈[θd-θmax，θd+θmax]且半徑r∈[0，rmax]的扇形作為節點網絡區域，如圖2(a)所示。其次，在半徑范圍為r∈{kΔr，rmax}(k∈[1，int(rmax/Δr)])的圓形區域，每個節點具有固定的間距Δl，如圖2(a)所示。

(a)

(b)

(d)圖2

模型中節點間的鏈接L對應飛機可能自由飛行的路線，對于每個節點來說，它只連接到下一個圓形上的節點，因此可以得到方位角θ∈[θd-φmax，θd+φmax]，φmax表示飛機航向角度的最大范圍。此外，為了避免出現飛機無法有效到達目的地的情況，增加了最后的圓Ndl和代表目的地的節點的直接鏈接，如圖2(c)中的虛線所示。每個鏈接的權重為wj，其中j∈[1，Nlink]，代表飛機通過長度dj的鏈接Lj的飛行時間。

2.3 動態空域模型

在動態空域中，需要考慮氣流的速度和方向、移動的不利天氣區域和限制區域。

首先，在圖2(d)中給出了依賴于時間的氣流的速度和方向。采用了從美國航空氣象中心測試數據服務器的API接口獲取的真實氣流數據。因此，采用了一個四維的(時間加上三維坐標空間)線性插值空間，風的矢量表示為(vw(t)，θw(t))(x，y，z)。

其次，惡劣天氣可能會對飛機造成嚴重危害，應該避免在這些區域飛行。在飛機飛行期間，不利天氣區域可能會持續移動，如圖2(d)中的橢圓形區域所示。在進行優化的過程中，Rp(t)，p∈[1，Nr]這些節點是不可訪問的。

最后，考慮了危險區域、限制區域和一些禁區的影響。如圖2(d)中的矩形表示，該區域在t1到t2需要繞行。限制區域也可以用Rp(t)表示，且不隨時間變化。

3 運用漣漪擴散算法優化自由航線

考慮到動態空域中氣流的方向和速度、飛行禁區以及時刻變化的天氣云團等因素，于是便在原有的航空路網的基礎上對自由航路問題進行了優化。在這部分中，首先介紹漣漪擴散算法的基本原理，以及對此算法進行優化和改進，使其與動態路網更加契合。

3.1 漣漪擴散算法(RSA)的基本原理

通常情況下，為了能夠很好地解決動態路徑優化(DPO)問題，我們會采用對線路在線重新優化(OLRO)的方法。但OLRO這種方法并不是從起始點出發去尋找最佳路徑，僅僅是在部分節點或者鏈接上改變當前行駛路徑，這便導致了OLRO方法所得到的優化路徑并不是最優解。

怎樣才能避免這一情況出現？RSA將環境參數和路徑優化過程共同演化，因此只需將這一算法運行一次便可得到最優路徑。RSA算法過程如圖3所示，圖中位置實時變化的禁區內包含的節點和鏈接用紅色標示，這一區域自西北方向往東南方向移動。在初始時刻ti，一個漣漪自起始點出發以恒定的速度向各個方向進行擴散，當漣漪到達了新的節點時將從這個節點產生新的漣漪向各個方向進行擴散，依次進行下去直到t=ti+mΔt(m∈N)時刻到達終點，最終通過反向跟蹤漣漪找到一條最佳路徑。同理，對于自由航路的優化，可以加入天氣以及飛行禁區等因素，運用RSA算法找到最佳自由航路。

圖3 在存在不可到達的區域時漣漪擴散算法的優化過程

3.2 具有動態網絡權重的漣漪擴散算法

傳統方法無法有效模擬自由航路優化問題中實時氣流對飛行器的影響，因此本文提出了基于動態賦值路網改進的漣漪擴散算法?；谠撍惴M的自由航路路線，能夠充分利用飛機巡航時的時變性氣流，從而以更快速度到達目的地。

正如2.3動態空域模型中所提到的，可以用如下式表示的風向和風速，對空間和時間進行離散化，得到風向風速數：

(vw(t)，θw(t))(x，y，z)

需要對每一次t=ti+mΔt時刻，重新依據風的參數重新賦值。例如，鏈接Lj的賦值ωj(t)可以通過圖1所示計算，認為飛機沿連線Lj飛行，地面速度矢量用如下公式表示，vg(t)方向應該與鏈路相同：

vg(t)=va(t)+vw(t)

可得：

那么對于所有t=ti+mΔt(m∈N)時刻的權重{ωj(t)}j∈[1，Nlink]，將依據實時風參數進行重新計算，從而便建立了一個動態網絡權重的路網。

雖然漣漪的傳播速度保持不變，但動態賦值網路導致飛機沿每個鏈路的飛行時間隨時變氣流參數的變化而變化。最后，通過在動態賦值網路運行一次RSA，便可得到在有氣流存在情況下的最佳自由航路。

圖4 在動態路由網絡下漣漪擴散過程及每個部分的權重

4 應用優化方法進行仿真測試

在復雜空域中，對飛機的自由飛行路徑的優化進行數值試驗。測試是在MATLAB環境(R2018a)中進行的處理器Intel(R)Core(TM)i7-8550U CPU @ 1.80GHz RAM 8GB。

其中仿真權重包括，參與計算的取值區間x∈[-1200，1700]，y∈[-1200，1700]，單位為海里(Nm)，起始位置為(xi，yi)=(-1000，-1000)，目標位置為(xf，yf)=(1000，1000)。我們選擇飛機的運行速度為va=500N/m，這是民用航空飛機常見的巡航速度。

網絡圖的權重包括Δr=150Nm，Δl=50Nm，θmax=40°，Фmax=35°，Ndl=2。這些權重的意義和第二部分中的相同，運行出的路線網絡圖如圖5所示。

圖5 對路由網絡的情況進行數值實驗

我們設置幾個惡劣天氣區域和限制區域，如下表所示，我們假設所有的區域都是圓形，前三個區域對應移動惡劣天氣區和它的相應速度，后兩個區域是固定限制區域。

惡劣天氣區域及限制區域初始位置半徑移動速度1(-1000,-400)100(75,-45)2(-1000,500)300(12.5,25)3(600,-200)600(-37.5,65.5)4(0,-600)100(0,0)5(1000,0)100(0,0)

氣流數據是通過對預測數據[位置(x，y，z)和時間t]進行四維差值得到的。圖6繪制了不同時間的風向量的計算域。我們設置漣漪擴散的速度是50/△t，也就是說，在△t的時間內，漣漪的半徑增加50Nm。

圖6 在不同時刻風的參數

在第三部分介紹的RSA應用于基于動態網絡權重的飛行路線優化。在執行一次運算后，即可得到一條最優路徑。優化的中間過程如圖7所示。圓內的區域代表惡劣天氣和限制區域，實心圓代表已經運行的節點。在圖7(d)中，被粗線圈起的區域是無法到達的節點和路線。除此之外，我們還可以看到上部分的漣漪傳播前沿要比下部分的離目的地更近。

(a)在t=tih (b)在t=ti+1.6h

(c)在t=ti+3.4h (d)在t=ti+5.0h

本次動態空域的最優飛行路線如圖8(a)所示。最優路線長度總和是2926.2Nm，飛行時間是5.18h，程序運行時間為67.9s。在該路線中，飛機利用氣流的優勢在最短的時間里避免危險區域，到達目的地。我們將這個結果與不考慮氣流因素的結果相比較，如圖8(b)所示，這兩種飛行軌跡受氣流影響并不是相同的。在不考慮氣流的測試中，優化路徑總路程為2908.4Nm，飛行時間是5.92h。即使它的飛行路程更短，但相較于前者，它的飛行時間增長了0.74h。此次程序的運行時間為2.5s，由于本次測試不考慮動態空域，所以運行時間要比前者短很多，結果符合預期。因此，文中的方法在解決動態空域中飛行路徑計劃的問題中具有有效性。

(a)存在在氣流

(b)不存在氣流圖8 自由航路在兩種情況下的優化結果

結語

本文對自由空域下單機航線的優化問題進行了建模，將惡劣天氣、禁飛區、氣流作為影響因素。這種方法的主要優點是將復雜環境下的航線優化簡化為數學模型，通過應用RSA算法解決問題并且可以通過模擬仿真實驗驗證。

通過進一步地研究，我們可以考慮以下幾方面問題：該方法可以應用于實際的航線優化問題，還可以應用于文章中相對復雜的網絡，也可以將該方法進一步應用于多機的航線優化問題。