基于航路點布局的多目標網絡結構優化方法

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

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

中國空域呈現碎片化、多元化特征，且部分區域航路網絡結構與飛行流量分布的矛盾十分突出[1]。為了規避障礙空域，同時避免因節點失效而導致的網絡崩潰，需進行航路網絡結構優化。

航路網絡結構優化指通過調整航路點及航段的數量和位置以改變原有網絡的性質和布局，從而實現優化目標[2]。根據規模大小，航路網絡結構優化分為全局性優化和區域性優化[3]。全局性優化針對主干航路進行，其優化過程復雜，改造成本較大；區域性優化則是在已有航路網的基礎上，針對一定范圍內的支線航路進行，改造成本較小，應用更為廣泛。

目前，國內外學者針對區域航路網絡的優化模型和算法進行了大量研究。王世錦和公言會[4]根據中國空域實際情況，建立了多目標優化模型，并利用蟻群算法[5]和元胞自動機[6]完成了模型求解。Dunn和Wilkinson[7]針對自然災害造成的部分航段失效，提出了基于節點重分布的自適應重構策略和永久改航策略。康金霞[8]利用復雜網絡建模方法對航路網絡抗毀性進行分析，提出了單航路點失效時的改航方法。嚴偉等[9]以網絡經濟性與安全性為基礎建立多目標優化模型，并采用煙花算法進行求解。然而，傳統規劃方法采用的目標函數及約束條件較少，規劃策略單一，且未能將網絡拓撲設計與飛行流量大小相結合，難以滿足實際需要。

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

1 區域航路網絡建立

1.1 組成要素

區域航路網絡由航路點和航路構成，且包含了節點連接關系、飛行流量和飛行容量等要素。其中，航路分為境內航路、過境航路和出境航路，它們由多條依次相連的航段組成；航路點分為固定航路點和移動航路點，前者指機場及區域邊境點，能夠產生和吸收飛行流量，后者指航路交叉點及轉向點，能夠傳遞飛行流量[10]。

1.2 表達形式

為了反映區域航路網絡特性，對各組成要素進行數學描述，可表示為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)為網絡流量參數，指單位時間內通過某航段或某航路點的航空器數目，包括航段PiPj的流量fij和航路點Pi的流量fi。

4)C(N)為網絡容量參數，包括航段PiPj的容量Cij和航路點Pi的容量Ci。

1.3 容量分析

區域航路網絡容量是衡量網絡容納性的參數，分為航段容量和航路點容量。

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

(3)

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

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

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

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

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

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

(4)

(5)

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

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

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

(6)

(7)

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

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

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

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

(8)

(9)

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

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

(10)

(11)

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

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

(12)

(13)

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

2 區域航路網絡結構優化模型

2.1 模型假設

區域航路網絡結構復雜，為了模擬實際運行環境，構建網絡優化模型，做出以下假設：

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

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

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

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

5) 不考慮網絡優化過程中的成本。

2.2 特性指標及約束

在區域航路網絡優化過程中，需要設定若干特性指標以提升網絡經濟性、安全性和可行性，促進網絡結構優化合理。

1) 運行費用

(14)

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

2) 飛行沖突系數

(15)

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

3) 非直線系數

(16)

Iij=dij/Gij

(17)

4) 航路角度改變量

(18)

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

為了保證網絡優化后滿足實際需求，必須制定相應約束對航路走向、航路點分布做出限制。

1) “三區”約束

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

(19)

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

2) 容量約束

(20)

式中：λi、λij為裕度因子，表示由于管制員、流量增長等因素帶來的影響。可避免航段或航路點陷入失效狀態，保持網絡的運行能力。

3) 優化范圍約束

(21)

2.3 模型建立

區域航路網絡的高效運轉不僅取決于其結構的安全合理，還取決于飛行流量與網絡容量的匹配關系，結合區域航路網絡的特性指標及約束條件，建立以下多目標網絡優化模型：

(22)

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

(23)

(24)

(25)

(26)

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

(27)

(28)

(29)

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

3 區域航路網絡結構優化模型求解

3.1 優化策略

區域航路網絡的具體結構取決于移動航路點的布局[10]。在優化過程中，為滿足實際情況，提高區域航路網絡的性能，需制定以下優化策略。

1) 構建空域環境

利用柵格法將空域劃分為若干個單位長度為l′的柵格以表示初始區域航路網絡的基本結構。

2) 增加改航轉向點

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

3) 移動航路點

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

4) 融合航路點

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

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

(30)

5) 分解航路點

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

(31)

3.2 優化步驟

區域航路網絡優化需綜合考慮網絡外在結構的合理性和內在運行的穩定性。因此，必須全面系統地統籌優化策略，設計優化方法。根據區域航路網絡的結構特征及運行規律，制定以下優化步驟(見圖3)：

步驟1確定初始區域航路網絡。

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

步驟3若不滿足，則根據幾何法增加改航轉向點，連接轉向點生成新航路并利用多目標網絡優化模型求解航路點最優布局，執行步驟2。

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

步驟5若不符合，則采取融合、分解航路點策略，進而利用多目標網絡優化模型求解航路點最優布局，執行步驟2。

圖3 區域航路網絡優化步驟Fig.3 Optimization steps of regional air route network

步驟6若符合，取其中最優解集，網絡優化完畢。

3.3 NSGA-Ⅲ算法

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

1) 染色體構建

區域航路網絡結構取決于移動航路點的分布情況，因此可采用實數編碼方式構建染色體，如x11x12…xα1xα2…xk1xk2，k為移動航路點個數，2k為染色體長度，xα1、xα2分別為航路點Pα的橫、縱坐標。

2) 操作算子

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

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

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

③ 交叉算子。采取模擬二進制交叉算子，先確定交叉個體及位置，進而由交叉概率判斷是否發生交叉。

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

3) 算法步驟

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

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

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

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

步驟4關聯操作。連接參考點和原點構成參考線，計算所有個體到與之最近的參考線的距離，將個體與對應參考點進行關聯。

4 實例分析

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

圖5 初始區域航路網絡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穿越“三區”，需要增加部分改航點，則經過初步規劃后的區域航路網絡如圖6所示。

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

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

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

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

圖6 初步規劃結果Fig.6 Preliminary planning result

圖7 區域航路網絡優化結果示意圖Fig.7 Schematic of regional air route network optimization results

網絡序號運行費用飛行沖突系數非直線系數角度改變量/(°)①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 優化網絡對比Fig.8 Contrast diagram of optimization network

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

5 結 論

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

1) 優化后的網絡符合相應約束條件，且飛行沖突系數改進明顯，空域安全性顯著提升。

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

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

4) 優化后的網絡契合中國空域“碎片化”特點和飛行流量日益增長的實際情況，可有效彌補現有網絡缺陷。

區域航路網絡與全局航路網絡是局部與整體的關系，今后將考慮其關聯作用對網絡結構優化的影響。