鄭煜坤， 王瑛， 李超， 亓堯， 李正欣

(1. 空軍工程大學 研究生院， 西安 710051； 2. 空軍工程大學 裝備管理與無人機工程學院， 西安 710051)

中國空域呈現(xiàn)碎片化、多元化特征，且部分區(qū)域航路網(wǎng)絡(luò)結(jié)構(gòu)與飛行流量分布的矛盾十分突出[1]。為了規(guī)避障礙空域，同時避免因節(jié)點失效而導致的網(wǎng)絡(luò)崩潰，需進行航路網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化。

航路網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化指通過調(diào)整航路點及航段的數(shù)量和位置以改變原有網(wǎng)絡(luò)的性質(zhì)和布局，從而實現(xiàn)優(yōu)化目標[2]。根據(jù)規(guī)模大小，航路網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化分為全局性優(yōu)化和區(qū)域性優(yōu)化[3]。全局性優(yōu)化針對主干航路進行，其優(yōu)化過程復(fù)雜，改造成本較大；區(qū)域性優(yōu)化則是在已有航路網(wǎng)的基礎(chǔ)上，針對一定范圍內(nèi)的支線航路進行，改造成本較小，應(yīng)用更為廣泛。

目前，國內(nèi)外學者針對區(qū)域航路網(wǎng)絡(luò)的優(yōu)化模型和算法進行了大量研究。王世錦和公言會[4]根據(jù)中國空域?qū)嶋H情況，建立了多目標優(yōu)化模型，并利用蟻群算法[5]和元胞自動機[6]完成了模型求解。Dunn和Wilkinson[7]針對自然災(zāi)害造成的部分航段失效，提出了基于節(jié)點重分布的自適應(yīng)重構(gòu)策略和永久改航策略?？到鹣糩8]利用復(fù)雜網(wǎng)絡(luò)建模方法對航路網(wǎng)絡(luò)抗毀性進行分析，提出了單航路點失效時的改航方法。嚴偉等[9]以網(wǎng)絡(luò)經(jīng)濟性與安全性為基礎(chǔ)建立多目標優(yōu)化模型，并采用煙花算法進行求解。然而，傳統(tǒng)規(guī)劃方法采用的目標函數(shù)及約束條件較少，規(guī)劃策略單一，且未能將網(wǎng)絡(luò)拓撲設(shè)計與飛行流量大小相結(jié)合，難以滿足實際需要。

本文在對兩航路、多航路交叉點容量進行細致討論的基礎(chǔ)上，以網(wǎng)絡(luò)的最小運行費用、最小飛行沖突系數(shù)、最小非直線系數(shù)和最小航路角度改變量為優(yōu)化目標，以“三區(qū)”約束、容量約束和優(yōu)化范圍約束為限制條件，建立了區(qū)域航路網(wǎng)絡(luò)優(yōu)化模型。進而提出移動、融合、分解等航路點優(yōu)化策略和優(yōu)化步驟，并使用更為精確的NSGA-Ⅲ算法完成模型求解。實現(xiàn)了網(wǎng)絡(luò)細節(jié)與整體性能的統(tǒng)籌規(guī)劃，有效提升了區(qū)域航路網(wǎng)絡(luò)的安全性、精確性和綜合性，彌補了傳統(tǒng)規(guī)劃方法的不足。

1 區(qū)域航路網(wǎng)絡(luò)建立

1.1 組成要素

區(qū)域航路網(wǎng)絡(luò)由航路點和航路構(gòu)成，且包含了節(jié)點連接關(guān)系、飛行流量和飛行容量等要素。其中，航路分為境內(nèi)航路、過境航路和出境航路，它們由多條依次相連的航段組成；航路點分為固定航路點和移動航路點，前者指機場及區(qū)域邊境點，能夠產(chǎn)生和吸收飛行流量，后者指航路交叉點及轉(zhuǎn)向點，能夠傳遞飛行流量[10]。

1.2 表達形式

為了反映區(qū)域航路網(wǎng)絡(luò)特性，對各組成要素進行數(shù)學描述，可表示為N(P,D,f,C)，具體含義如下：

1)P(N)={P1,P2，…,Pn,Pn+1,…,Pn+m}為航路點集，前n項為固定航路點，后m項為移動航路點。

2)D(N)為航路連接距離矩陣，可表示為

D(N)=(dij)(n+m)×(n+m)i,j∈[1,m+n]

(1)

(2)

式中：(xi,yi)為Pi坐標；L(Pi,Pj)用來判斷航路點Pi與Pj是否相連，若是，值為1，若否，值為0。

3)f(N)為網(wǎng)絡(luò)流量參數(shù)，指單位時間內(nèi)通過某航段或某航路點的航空器數(shù)目，包括航段PiPj的流量fij和航路點Pi的流量fi。

4)C(N)為網(wǎng)絡(luò)容量參數(shù)，包括航段PiPj的容量Cij和航路點Pi的容量Ci。

1.3 容量分析

區(qū)域航路網(wǎng)絡(luò)容量是衡量網(wǎng)絡(luò)容納性的參數(shù)，分為航段容量和航路點容量。

航段容量指單位時間內(nèi)航段上某點允許通過的最大飛行架次[11]。令航空器巡航速度為v，最小管制距離為Lmin，可得

(3)

航路點容量指在特定航路結(jié)構(gòu)中的交叉點單位時間內(nèi)允許通過的最大飛行架次[6]，如圖1所示。PA′PO、PB′PO為匯聚航段，POPD′、POPH′為離散航段，α、β、φ、φ為航段夾角。

若t=0時，前繼航班位于PB′PO上的O點，后續(xù)航班位于PA′PO上的Y1點，L=|Y1O|，相鄰航班間距為F，則存在以下3種情況：

圖1 航路點容量示意圖Fig.1 Schematic of waypoint capacity

1) 當t∈(0,L/v)時，前繼航班運行至G1點，后續(xù)航班運行至E1點，有

F={(2v2+2v2cosβ)[t-L/(2v)]2+

(L2/2)(1-cosβ)}1/2

(4)

(5)

2) 當t∈[L/v,+∞)時，前繼航班運行至G2點，后續(xù)航班運行至E2點，有

F={(2v2+2v2cosφ)[t-L/(2v)]2+

(L2/2)(1-cosφ)}1/2

(6)

(7)

則航路點O能正常運行時，其容量為v/Lmin。

3) 當t∈(-∞,0]時，前繼航班運行至G3點，后續(xù)航班運行至E3點，有

F={(2v2-2v2cosα)[t-L/(2v)]2+

(L2/2)(1+cosα)}1/2

(8)

(9)

則航路點O能正常運行時，其容量為v/Lmin。

綜上所述，當兩航路交叉且來流方向固定時，O點的容量取值有6種情況。在實際運行過程中，為保證O點的安全運行，應(yīng)使其容量取最小值，則有

(10)

(11)

根據(jù)上述思路，當多條航路發(fā)生交叉時(見圖1(b))，可將其劃分為若干個兩航路交叉的情況進行處理，則交叉點O的容量為

CO=min(CO1,CO2,…,COω)

(12)

(13)

式中：COi(i=1,2,…,ω)和δi(i=1,2,…,ω)分別為第i種兩航路交叉情況下對應(yīng)的點容量和相應(yīng)航段夾角。

2 區(qū)域航路網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化模型

2.1 模型假設(shè)

區(qū)域航路網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，為了模擬實際運行環(huán)境，構(gòu)建網(wǎng)絡(luò)優(yōu)化模型，做出以下假設(shè)：

1) 網(wǎng)絡(luò)中的航空器均位于同一高度層，其真航線角為[0,π]或[π,2π]。

2) 航路點之間的連接關(guān)系和飛行流量保持不變，“三區(qū)”空域不可穿越。

3) 航空器巡航速度為800 km/h，規(guī)定的最小雷達管制間隔為20 km，航路點的優(yōu)化范圍為±50 km。

4) 不考慮進近管制區(qū)的飛行沖突。

5) 不考慮網(wǎng)絡(luò)優(yōu)化過程中的成本。

2.2 特性指標及約束

在區(qū)域航路網(wǎng)絡(luò)優(yōu)化過程中，需要設(shè)定若干特性指標以提升網(wǎng)絡(luò)經(jīng)濟性、安全性和可行性，促進網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化合理。

1) 運行費用

(14)

式中：T(N)為運行費用；dij為航段PiPj的長度。

2) 飛行沖突系數(shù)

(15)

式中：ci(i=1,2,…,m+n)為交叉航路點Pi的飛行沖突系數(shù)；αjik為航段PjPi和航段PkPi的夾角。

3) 非直線系數(shù)

(16)

Iij=dij/Gij

(17)

4) 航路角度改變量

(18)

式中：Δθij為航路Pi-Pj中相鄰航段之間的角度改變量。

為了保證網(wǎng)絡(luò)優(yōu)化后滿足實際需求，必須制定相應(yīng)約束對航路走向、航路點分布做出限制。

1) “三區(qū)”約束

line(Pi,Pj)∩U(N)=?

(19)

式中：line(Pi,Pj)為航段PiPj穿越的空域范圍；U(N)為網(wǎng)絡(luò)中的“三區(qū)”空域。

2) 容量約束

(20)

式中：λi、λij為裕度因子，表示由于管制員、流量增長等因素帶來的影響?？杀苊夂蕉位蚝铰伏c陷入失效狀態(tài)，保持網(wǎng)絡(luò)的運行能力。

3) 優(yōu)化范圍約束

(21)

2.3 模型建立

區(qū)域航路網(wǎng)絡(luò)的高效運轉(zhuǎn)不僅取決于其結(jié)構(gòu)的安全合理，還取決于飛行流量與網(wǎng)絡(luò)容量的匹配關(guān)系，結(jié)合區(qū)域航路網(wǎng)絡(luò)的特性指標及約束條件，建立以下多目標網(wǎng)絡(luò)優(yōu)化模型：

(22)

arccos(αjik/2)/(fji+fki)]+M

(23)

(24)

(25)

(26)

式(22)～式(25)分別表示區(qū)域航路網(wǎng)絡(luò)的最小運行費用、最小飛行沖突系數(shù)、最小非直線系數(shù)和最小航路角度改變量。式(26)表示“三區(qū)”約束、容量約束和優(yōu)化范圍約束。式中：c為總飛行沖突系數(shù)，表征網(wǎng)絡(luò)風險水平；M為罰函數(shù)，可將部分約束條件轉(zhuǎn)化為目標函數(shù)的一部分，表示如下：

(27)

(28)

(29)

其中：σ為罰因子，可取σ=1 000[12]；m′為航路交叉點個數(shù)；Ω(PiPj)用來判斷航段PiPj是否經(jīng)過“三區(qū)”；Ψ(Pi)用來判斷航路點Pi的容量是否符合條件。

3 區(qū)域航路網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化模型求解

3.1 優(yōu)化策略

區(qū)域航路網(wǎng)絡(luò)的具體結(jié)構(gòu)取決于移動航路點的布局[10]。在優(yōu)化過程中，為滿足實際情況，提高區(qū)域航路網(wǎng)絡(luò)的性能，需制定以下優(yōu)化策略。

1) 構(gòu)建空域環(huán)境

利用柵格法將空域劃分為若干個單位長度為l′的柵格以表示初始區(qū)域航路網(wǎng)絡(luò)的基本結(jié)構(gòu)。

2) 增加改航轉(zhuǎn)向點

由于經(jīng)濟發(fā)展、歷史遺留等客觀原因，現(xiàn)有航路布局可能存在缺陷。當航路穿越“三區(qū)”時，可采用幾何法確定新增改航轉(zhuǎn)向點的初步位置，使飛行器沿“三區(qū)”邊緣通過[13]。

3) 移動航路點

當交叉點或改航點位置不合理，造成局部節(jié)點失效或影響網(wǎng)絡(luò)整體性能時，可利用NSGA-Ⅲ算法對其布局進行改進，保證區(qū)域航路網(wǎng)絡(luò)正常運轉(zhuǎn)。

4) 融合航路點

當航路交叉點分布密集且飛行流量較小時，空域安全度高，可將一定范圍內(nèi)的多個交叉點融合成單個交叉點，如圖2所示，融合后有

圖2 航路點融合、分解示意圖Fig.2 Schematic diagram of waypoint integration and separation

(30)

5) 分解航路點

當航路交叉點流量較大，出現(xiàn)容流沖突，影響空域安全時，可將單個交叉點分解為多個交叉點，如圖2所示，其關(guān)系如下：

(31)

3.2 優(yōu)化步驟

區(qū)域航路網(wǎng)絡(luò)優(yōu)化需綜合考慮網(wǎng)絡(luò)外在結(jié)構(gòu)的合理性和內(nèi)在運行的穩(wěn)定性。因此，必須全面系統(tǒng)地統(tǒng)籌優(yōu)化策略，設(shè)計優(yōu)化方法。根據(jù)區(qū)域航路網(wǎng)絡(luò)的結(jié)構(gòu)特征及運行規(guī)律，制定以下優(yōu)化步驟(見圖3)：

步驟1確定初始區(qū)域航路網(wǎng)絡(luò)。

步驟2判斷是否滿足“三區(qū)”約束。

步驟3若不滿足，則根據(jù)幾何法增加改航轉(zhuǎn)向點，連接轉(zhuǎn)向點生成新航路并利用多目標網(wǎng)絡(luò)優(yōu)化模型求解航路點最優(yōu)布局，執(zhí)行步驟2。

步驟4若滿足，則判斷是否符合其他約束。

步驟5若不符合，則采取融合、分解航路點策略，進而利用多目標網(wǎng)絡(luò)優(yōu)化模型求解航路點最優(yōu)布局，執(zhí)行步驟2。

圖3 區(qū)域航路網(wǎng)絡(luò)優(yōu)化步驟Fig.3 Optimization steps of regional air route network

步驟6若符合，取其中最優(yōu)解集，網(wǎng)絡(luò)優(yōu)化完畢。

3.3 NSGA-Ⅲ算法

基于參考點的非支配排序遺傳算法，即NSGA-Ⅲ是Kalyanmoy和Himanshu[14]提出的第三代多目標規(guī)劃算法。該算法在繼承NSGA-Ⅱ非支配排序的基礎(chǔ)上，利用關(guān)聯(lián)操作求解參考距離的方法代替了原來的擁擠度算子，提高了種群多樣性。當目標函數(shù)較多時，其規(guī)劃效果明顯優(yōu)于傳統(tǒng)多目標規(guī)劃方法。

1) 染色體構(gòu)建

區(qū)域航路網(wǎng)絡(luò)結(jié)構(gòu)取決于移動航路點的分布情況，因此可采用實數(shù)編碼方式構(gòu)建染色體，如x11x12…xα1xα2…xk1xk2，k為移動航路點個數(shù)，2k為染色體長度，xα1、xα2分別為航路點Pα的橫、縱坐標。

2) 操作算子

為了改進算法性能，提高運算效率，NSGA-Ⅲ算法在采取選擇、變異、交叉3種傳統(tǒng)操作算子的同時，引入刪除算子，其表述如下：

① 選擇算子。計算復(fù)合種群所有個體的目標函數(shù)值并根據(jù)結(jié)果進行快速非支配排序，當序號為N′的個體位于第l層時，采取關(guān)聯(lián)操作計算第l層個體到其對應(yīng)參考線的垂直距離，根據(jù)距離篩選符合條件的個體進入子代種群。

② 變異算子。采用基本變異方式，先確定變異個體及位置，進而由變異概率確定是否變異及變異后個體值。

③ 交叉算子。采取模擬二進制交叉算子，先確定交叉?zhèn)€體及位置，進而由交叉概率判斷是否發(fā)生交叉。

④ 刪除算子。對航路點坐標超出規(guī)劃范圍的染色體執(zhí)行刪除操作，重新生成染色體。

3) 算法步驟

NSGA-Ⅲ算法的基本步驟與傳統(tǒng)遺傳算法相似[15]，但在選擇機制上有所創(chuàng)新，如圖4所示。

其中，選擇操作的具體步驟可描述如下：

步驟1非支配排序。將種群個體按照非支配規(guī)則分為m層，其中前l(fā)層個體記為Πl(fā)，數(shù)目為|Πl(fā)|，且|Πl(fā)|>N′。前l(fā)-1層個體記為Πl(fā)-1，數(shù)目為|Πl(fā)-1|，且|Πl(fā)-1|

步驟3歸一化目標函數(shù)。計算理想點和極值點，轉(zhuǎn)換目標函數(shù)，最終完成歸一化操作。

步驟4關(guān)聯(lián)操作。連接參考點和原點構(gòu)成參考線，計算所有個體到與之最近的參考線的距離，將個體與對應(yīng)參考點進行關(guān)聯(lián)。

4 實例分析

以北京飛行情報區(qū)二連浩特P11、土木爾臺P12和錫林浩特P19組成的區(qū)域航路網(wǎng)絡(luò)為例進行結(jié)構(gòu)優(yōu)化仿真，令航空器的真航線角范圍為[0,π]，柵格邊長l′為23.58 km，其示意圖如圖5所示。其中，空心圓代表邊境點和機場，實心圓代表航路交叉點，ZTi為“三區(qū)”，箭頭指向表示流量運行方向。航段容量為40 架次/h，令λi=λij=0.75，圖5所示的區(qū)域航路網(wǎng)絡(luò)的相關(guān)數(shù)據(jù)見表1和表2[16-17]。

圖5 初始區(qū)域航路網(wǎng)絡(luò)Fig.5 Initial regional air route network

航路點匯聚航段交叉角航路點流量/(架次·h-1)航路點容量/(架次·h-1)P13∠P11P13P1211.420.96P14∠P13P14P1212.532.31P15∠P12P15P1412.938.03P16∠P15P16P1816.634.77P17∠P16P17P614.927.04P18∠P9P18P1414.926.92

表2 航段信息

由表1和表2可知，航路交叉點均符合容量約束，但航段P12P15和航段P17P19穿越“三區(qū)”，需要增加部分改航點，則經(jīng)過初步規(guī)劃后的區(qū)域航路網(wǎng)絡(luò)如圖6所示。

圖6中，區(qū)域航路網(wǎng)絡(luò)的總運行費用為5.424×103，飛行沖突系數(shù)為1.151，非直線系數(shù)為1.248，角度改變量為215.9°。根據(jù)區(qū)域航路網(wǎng)絡(luò)優(yōu)化步驟，分別采用NSGA-Ⅲ算法、NSGA-Ⅱ算法和粒子群算法對圖6中移動航路點的布局進行優(yōu)化。設(shè)置種群大小為100，進化代數(shù)為800，變異率為0.1，雜交率為0.15，可得如圖7所示的優(yōu)化結(jié)果。

圖7中，(a)～(d)為利用NSGA-Ⅲ算法得到的區(qū)域航路網(wǎng)絡(luò)；(e)、(f)為利用NSGA-Ⅱ算法和粒子群算法得到的區(qū)域航路網(wǎng)絡(luò)，各網(wǎng)絡(luò)具體特征值如表3所示。

表3中，⑦為初步規(guī)劃后的網(wǎng)絡(luò)，⑧為初始區(qū)域航路網(wǎng)絡(luò)。通過對比可知，各優(yōu)化網(wǎng)絡(luò)的運行費用、非直線系數(shù)和角度改變量相比于初始網(wǎng)絡(luò)均有所增加，但是這些網(wǎng)絡(luò)的飛行沖突系數(shù)下降顯著，同時實現(xiàn)了對障礙區(qū)域的規(guī)避，從而使得空域安全性得以提高。其中，網(wǎng)絡(luò)③、④的運行費用、非直線系數(shù)和角度改變量較優(yōu)，其改進效果較佳；網(wǎng)絡(luò)①、②的各項指標較為均衡，改進效果良好；網(wǎng)絡(luò)⑤、⑥的飛行沖突系數(shù)較小，但是其多項指標排名靠后，整體性能一般。為突出差異，對各優(yōu)化網(wǎng)絡(luò)指標與網(wǎng)絡(luò)⑦指標的比值進行分析，如圖8所示。

不難看出，優(yōu)化網(wǎng)絡(luò)②～④的綜合性能優(yōu)于優(yōu)化網(wǎng)絡(luò)⑤、⑥，其中優(yōu)化網(wǎng)絡(luò)④的改進效果最佳。相比于初步規(guī)劃后的網(wǎng)絡(luò)，優(yōu)化網(wǎng)絡(luò)④的運行費用減少了0.11%，飛行沖突系數(shù)減少了15.6%，非直線系數(shù)減少了0.16%，僅角度改變量略有增加；相比于初始網(wǎng)絡(luò)，優(yōu)化網(wǎng)絡(luò)④符合全部約束條件，同時其飛行沖突系數(shù)減少了10.8%，運行費用與非直線系數(shù)略有增加，僅角度改變量變化較大。

圖6 初步規(guī)劃結(jié)果Fig.6 Preliminary planning result

圖7 區(qū)域航路網(wǎng)絡(luò)優(yōu)化結(jié)果示意圖Fig.7 Schematic of regional air route network optimization results

網(wǎng)絡(luò)序號運行費用飛行沖突系數(shù)非直線系數(shù)角度改變量/(°)①5.409×1031.0921.244266.5②5.425×1030.9541.251268.1③5.413×1030.9721.245238.7④5.418×1030.9711.246216.5⑤5.437×1030.9691.257282.3⑥5.495×1030.8791.276330.2⑦5.424×1031.1511.248215.9⑧5.405×1031.0891.22763.34

圖8 優(yōu)化網(wǎng)絡(luò)對比Fig.8 Contrast diagram of optimization network

因此，NSGA-Ⅲ算法能夠有效求解基于航路點布局的網(wǎng)絡(luò)優(yōu)化模型，且單次運算可提供多種屬性各異的優(yōu)化網(wǎng)絡(luò)，方便規(guī)劃人員在不同任務(wù)目標和約束條件下進行選擇。

5 結(jié) 論

本文建立了基于航路點布局的多目標網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化模型，并利用NSGA-Ⅲ算法對模型進行求解，驗證了區(qū)域航路網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化方法在解決航路避障和網(wǎng)絡(luò)節(jié)點失效時的可行性。從仿真分析中可以得出：

1) 優(yōu)化后的網(wǎng)絡(luò)符合相應(yīng)約束條件，且飛行沖突系數(shù)改進明顯，空域安全性顯著提升。

2) 利用航路點的移動、融合、分解策略可有效解決容流匹配問題和“三區(qū)”避讓問題。

3) 利用NSGA-Ⅲ算法求解多目標優(yōu)化問題的效果較優(yōu)，且能為規(guī)劃者提供多種備選方案。

4) 優(yōu)化后的網(wǎng)絡(luò)契合中國空域“碎片化”特點和飛行流量日益增長的實際情況，可有效彌補現(xiàn)有網(wǎng)絡(luò)缺陷。

區(qū)域航路網(wǎng)絡(luò)與全局航路網(wǎng)絡(luò)是局部與整體的關(guān)系，今后將考慮其關(guān)聯(lián)作用對網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化的影響。