自由航路空域的出入口位置布局優(yōu)化

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

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

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

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

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

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

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

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

1.1 空域限制條件模型

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

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

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

1.2 優(yōu)化目標(biāo)計(jì)算模型

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

式中：dFiEk為空域外起點(diǎn)Fi到進(jìn)入邊界入口Ek的直線距離；dEkOl為進(jìn)入邊界入口Ek到離開(kāi)邊界出口Ol的距離；dOlGj為離開(kāi)邊界出口Ol到空域外終點(diǎn)Gj的距離；為空域外起點(diǎn)Fi到空域外終點(diǎn)Gj路線組合中的最短總距離。

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

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

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

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

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

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

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

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

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

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

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

2.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

根據(jù)上述航班信息，保持現(xiàn)有空域邊界的出入口分別為4 的數(shù)量不變，交叉概率為0.9，變異概率為0.1，對(duì)邊界出入口的位置布局進(jìn)行優(yōu)化。圖4為傳統(tǒng)遺傳算法進(jìn)化圖，航班加權(quán)距離偏差代表的算法曲線在600 代以內(nèi)逐漸下降，在800～1 200 代收斂，得出最優(yōu)結(jié)果。圖5 為精英保留的遺傳算法進(jìn)化圖，航班加權(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 對(duì)出入口位置分布優(yōu)化的傳統(tǒng)遺傳算法迭代圖

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

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

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

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

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

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

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

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

3 結(jié)論

本文針對(duì)自由航路空域的劃設(shè)與出入口優(yōu)化問(wèn)題，建立了以航班加權(quán)距離偏差為目標(biāo)的優(yōu)化模型，并以典型空域?yàn)槔M(jìn)行優(yōu)化分析。

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

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