魏路歡，陳創(chuàng)希，周 興，魏志強*

（1.民航航空公司人工智能重點實驗室，廣東 廣州 510000；2.中國民航大學(xué)空中交通管理學(xué)院，天津 300300）

自由航路空域（free route airspace，F(xiàn)RA）是歐洲單一天空項目（single european sky ATM research，SESAR）的重要組成部分，是空域一體化改革與擴容增效的重要舉措，可以降低航空器的飛行時間、燃料消耗、飛行成本以及對環(huán)境的影響。目前歐洲3/4 的空域都已實現(xiàn)自由航路空域[1]。在自由航路空域飛行時，只需選定入口和出口，航空器就可以按照大圓航線穿過這個空域[2]。

Reynolds[3]針對不同飛行階段和地理區(qū)域，找出了衡量實際飛機軌跡與理論上最短飛機軌跡之間偏差的效率指標；Siddiquuee[4]給出了用于航路網(wǎng)絡(luò)優(yōu)化的一系列數(shù)學(xué)模型，包括航路網(wǎng)絡(luò)節(jié)點的潛在沖突系數(shù)、航路容量、航路距離等；Steve[5]提出飛行計劃優(yōu)化策略，以實現(xiàn)最佳航線、高度、速度和加油量的優(yōu)化。上述研究都是基于傳統(tǒng)的航路網(wǎng)空域開展的，沒有考慮自由航路空域（FRA）的特殊性以及對航路優(yōu)化的影響。

嚴偉等[6]針對航路網(wǎng)絡(luò)的運行成本和安全性相沖突問題，考慮多種不確定因素的影響，建立了不確定條件下的航路點布局優(yōu)化模型；嚴偉等[7]從航路網(wǎng)絡(luò)經(jīng)濟性和安全性出發(fā)，對航路點布局進行了優(yōu)化；余朝軍等[8]在多種約束的基礎(chǔ)上,建立了航班—登機口分配的多目標非線性0-1 整數(shù)規(guī)劃模型,提高了登機口的利用效率和乘客的換乘舒適度；郭野晨飛等[9]采用基于航班優(yōu)先級排列的染色體編碼方式，設(shè)計了一種改進的遺傳算法，提高了空域運行效率；王世錦等[10]闡述了3 大類航路網(wǎng)絡(luò)規(guī)劃研究技術(shù)的實施原理、存在的優(yōu)缺點及不同環(huán)境下的適用性，為交通規(guī)劃理論提供了更多的借鑒；李文等[11]提出基于可靠度的備件保障中心多目標選址模型，可作出運輸路徑最短、總成本最小的最優(yōu)選址決策；王瑛等[12]以成本和沖突系數(shù)作為航路點布局點問題的目標函數(shù)，構(gòu)建了航路點布局優(yōu)化問題模型。上述研究主要針對交叉航路對航路點位置布局進行優(yōu)化，沒有考慮自由航路空域（FRA）中的出入口優(yōu)化問題。

針對自由航路空域劃設(shè)中的出入口位置布局優(yōu)化問題，本文建立了空域限制條件模型，并以航班加權(quán)距離偏差為目標，構(gòu)建了給定出入口數(shù)量下的位置優(yōu)化模型，采用基于精英保留的遺傳算法進行了求解，最后選取歐洲某典型空域進行優(yōu)化分析。結(jié)果表明，在給定出入口數(shù)量的前提下，通過對自由航路空域出入口進行位置的布局優(yōu)化，可縮短航班航程，提高飛行效益。

1 自由空域出入口布局優(yōu)化模型

自由航路空域邊界的出入口位置布局優(yōu)化模型的構(gòu)建，主要包括建立空域限制條件模型和優(yōu)化目標計算模型。

1.1 空域限制條件模型

在一個自由航路空域中，雖然空域的范圍很大，但對于決策變量即分布在邊界的出入口的位置坐標來說，變動范圍應(yīng)該是有限的，即有空域邊界點位置約束?？沼蜻吔琰c位置約束是指所有待優(yōu)化的邊界出入口的位置變動范圍不能是全局航路網(wǎng)絡(luò)，應(yīng)約束在所在空域的進出邊界上。

圖1 自由航路區(qū)航線示意圖

式中：t為0 與1 之間的隨機數(shù)；E1為入口E1的經(jīng)緯度對；E3為入口E3的經(jīng)緯度對；O1為出口O1的經(jīng)緯度對；O2為出口O2的經(jīng)緯度對。

1.2 優(yōu)化目標計算模型

已知空域外n個起點{F1，F(xiàn)2，···，F(xiàn)n}、進入邊界x個入口{E1,E2,···,Ex}、離開邊界 y個出口{O1,O2,···,Oy}以及空域外m個終點{G1,G2,···,Gm}的經(jīng)緯度坐標。在自由航路空域外有n個起點m個終點的情況下共有(n×x×y×m)種飛行路徑組合，在路線組合中選擇起點和終點一一對應(yīng)的最優(yōu)飛行航線的模型為：

式中：dFiEk為空域外起點Fi到進入邊界入口Ek的直線距離；dEkOl為進入邊界入口Ek到離開邊界出口Ol的距離；dOlGj為離開邊界出口Ol到空域外終點Gj的距離；為空域外起點Fi到空域外終點Gj路線組合中的最短總距離。

算法模型的適應(yīng)度為自由航路空域外有n個起點m個終點的飛行路線組合的航班加權(quán)距離偏差g，即實際航班加權(quán)距離與航班加權(quán)大圓航線距離的偏差值。航班加權(quán)距離偏差能夠直觀地表達出優(yōu)化后的實際航班加權(quán)距離與大圓航線距離的接近程度，偏差越小，則實際飛行越接近直線飛行，航程越短。

式中：pij為實際情況下從空域外Fi起點到空域外Gj終點的航班飛行量（/月份）;Dij為空域外Fi起點到空域外Gj終點的大圓航線距離；gh為在一定出入口數(shù)量的情況下，出入口坐標位置不同的第h個方案。

1.3 出入口優(yōu)化流程設(shè)計

不同數(shù)量的邊界出入口，得到的穿越自由航路空域的飛行路線也有很多種，每條航線的距離不同，計算量巨大。本文采用精英保留的遺傳算法，在基礎(chǔ)遺傳算法的基礎(chǔ)上加快了收斂速度，得出較為合適的進出口數(shù)量以及對應(yīng)的最優(yōu)分布位置。具體流程如圖2 所示。

圖2 基于遺傳算法的自由航路空域邊界出入口優(yōu)化流程

1）輸入自由航路空域邊界入口的數(shù)量x和離開邊界出口的數(shù)量y，隨機生成初始串結(jié)構(gòu)，初始串長度為空域邊界出入口的數(shù)量和。采用實數(shù)編碼，根據(jù)輸入的空域出入口的數(shù)量，隨機生成x個入口的緯度坐標集和y個出口的緯度坐標集，其中，Etx為第x個入口的緯度，Oty為第y個出口的緯度。。當有M個個體N，則構(gòu)成了算法的初始種群M。

2）調(diào)用計算適應(yīng)度的函數(shù)模型，通過式（3）計算出適應(yīng)度值。適應(yīng)度值越小，代表該個體的性能越好，越滿足適應(yīng)條件。

3）采用輪盤賭的方式選擇適應(yīng)度較高的父代種群，進行交叉、變異等遺傳操作并更新種群，交叉概率為0.9，變異概率為0.1。

4）找出父代種群中最優(yōu)的個體，將其保存，使其基因染色體不會被遺傳操作破壞掉，然后替換掉經(jīng)過交叉、變異之后子代種群中，適應(yīng)度最差的個體。

5）進行循環(huán)操作，直到迭代次數(shù)等于設(shè)定次數(shù)。得到的最優(yōu)個體即為算例所求的航班加權(quán)距離偏差，對應(yīng)的自變量為不同數(shù)量下的自由航路空域邊界出入口對應(yīng)的最優(yōu)經(jīng)緯度坐標。

2 典型空域的出入口布局優(yōu)化分析

2.1 實驗數(shù)據(jù)

該算例分析的是地理位置臨近葡萄牙的一塊自由航路空域。該空域的邊界由航路點連接而成，呈不規(guī)則八邊形，如圖3 所示?？沼蛲馄瘘c為{B5、B6、B7、B8、B9}，空域外終點為{A6、A7、A8}，空域入口為{AMSEL、A1111、A2222、A3333、A4444、A5555、BATAX}，空域出口為{LUTAK、KOMUT、GUNTI、ERPES、DETOX、BANAL}。

圖3 歐洲某自由航路空域圖

主要分析空域外起點{B5、B6、B7、B8、B9}穿越進入邊界NNNNN和離開邊界XXXXX，到達空域外終點{A6、A7、A8}，從2020 年6 月1 日到6 月30 日的航班飛行情況。具體航班數(shù)量和從空域外起點到終點的15 種大圓航線距離以及實際飛行距離如表1 所示。實際飛行距離為空域外起點經(jīng)過當前出入口到達空域外終點的航線距離。

表1 不同航線上的航班量以及對應(yīng)的直飛距離

針對上述數(shù)據(jù)，計算出在當前的出入口位置布局下，航班加權(quán)距離偏差為3 661 km，即為航班加權(quán)大圓航線距離的5.832 3%。在優(yōu)化自由航路空域出入口位置的過程中，首先設(shè)定自由空域出入口的數(shù)量分別為x=4和y=4，算法隨機生成該數(shù)量的出入口經(jīng)緯度坐標，然后分別計算5×x×y×3=240 條航線的航線距離，根據(jù)空域外n個起點m個終點中選最優(yōu)模型，選出最短航線，計算出航班加權(quán)距離偏差，即為該方案下的適應(yīng)度。然后經(jīng)過精英保留的遺傳算法進行初始種群—邊界入口和出口經(jīng)緯度坐標的交叉、變異等操作，得出新的種群。該種群保留了父代種群優(yōu)良基因，再進行循環(huán)計算，直至得出在給定出入口數(shù)量下的最優(yōu)分布位置坐標。

2.2 位置優(yōu)化結(jié)果分析

根據(jù)上述航班信息，保持現(xiàn)有空域邊界的出入口分別為4 的數(shù)量不變，交叉概率為0.9，變異概率為0.1，對邊界出入口的位置布局進行優(yōu)化。圖4為傳統(tǒng)遺傳算法進化圖，航班加權(quán)距離偏差代表的算法曲線在600 代以內(nèi)逐漸下降，在800～1 200 代收斂，得出最優(yōu)結(jié)果。圖5 為精英保留的遺傳算法進化圖，航班加權(quán)距離偏差代表的算法曲線在50 代以內(nèi)快速下降，之后下降速度減慢，在150～500 代之后逐漸趨于平穩(wěn)，其航班加權(quán)偏差為263.473 4 km，為航班加權(quán)大圓航線距離的0.419 7%，比優(yōu)化前降低了5.412 6%。

圖4 對出入口位置分布優(yōu)化的傳統(tǒng)遺傳算法迭代圖

圖5 對出入口位置分布優(yōu)化的基于精英保留的遺傳算法迭代圖

通過對比2 種算法的迭代圖，可以看出基于精英保留的遺傳算法在傳統(tǒng)遺傳算法的基礎(chǔ)上加快了收斂速度，減少了迭代次數(shù)，提高了優(yōu)化速率。

進入邊界NNNNN 上優(yōu)化后的入口和離開邊界XXXXX 上優(yōu)化后的出口位置分布分別為{x1、x2、x3、x4}，{y1、y2、y3、y4}，在圖6 中用黑色圓點表示。圖6 為空域外起點B9經(jīng)過優(yōu)化后的出入口到達終點A6、A7、A8的航線與對應(yīng)的未優(yōu)化前的實際飛行航線的直觀對比。其中，黑色線段代表未優(yōu)化前的飛行航線，紅色線段代表起點B9到終點A6的優(yōu)化航線，藍色線段代表起點B9到終點A7的優(yōu)化航線，黃色線段代表起點B9到終點A8的優(yōu)化航線。從圖中較直觀地看出，優(yōu)化后的航線較優(yōu)化前的航線更接近大圓航線，飛行距離明顯縮短。幾個空域外起點到達空域外終點的優(yōu)化航線在圖中顯示忽略。

圖6 優(yōu)化后的航線與優(yōu)化前的航線對比圖

2.3 出入口數(shù)量的影響分析

通過設(shè)定不同數(shù)量的自由航路空域出入口，可以得出不同的航班加權(quán)距離偏差。出入口數(shù)量越多則航班加權(quán)距離偏差就越小，結(jié)果越優(yōu)異，但一味增加出入口數(shù)量是不現(xiàn)實的。圖7 為不同數(shù)量的出入口對應(yīng)的航班加權(quán)距離偏差和其占航班加權(quán)大圓航線距離的比重。

圖7 不同數(shù)量出入口的航班加權(quán)距離偏差和其占航班加權(quán)大圓航線的比重

由圖可知，當自由航路空域出入口數(shù)量為7 或者8 時，再通過增加出入口的個數(shù)來縮小航班加權(quán)距離偏差，其效果已不明顯。即對于空域外有n個起點、m個終點的情況下，F(xiàn)RA 的出入口數(shù)量達到(n×m×50%)時，優(yōu)化的效果即可接近于直線飛行。

3 結(jié)論

本文針對自由航路空域的劃設(shè)與出入口優(yōu)化問題，建立了以航班加權(quán)距離偏差為目標的優(yōu)化模型，并以典型空域為例進行優(yōu)化分析。

1）通過對現(xiàn)有空域出入口的位置進行優(yōu)化，能夠在原有實際航班加權(quán)距離偏差的基礎(chǔ)上減少5.412 6%。這說明優(yōu)化空域出入口的位置能夠有效的縮短航程，提高飛行效益。

2）雖然增加空域出入口數(shù)量，會使優(yōu)化效益提高，但是當超過空域外起點和終點數(shù)量乘積的50%時，優(yōu)化的效果已接近于直線飛行。