惡劣天氣條件下航路網(wǎng)絡(luò)修復(fù)優(yōu)化

隋東，邢婭萍，涂詩(shī)晨

南京航空航天大學(xué) 民航學(xué)院，南京 211106

由中國(guó)民用航空局官方統(tǒng)計(jì)數(shù)據(jù)[1]可知，2014—2018年間天氣原因?qū)е碌暮桨嗖徽Ｂ蕪?4.30%增長(zhǎng)到47.46%，在2016年和2017年甚至超過(guò)了50%，相比空管、航空公司和其他因素，天氣已成為影響航路網(wǎng)絡(luò)正常運(yùn)行的第一因素。惡劣天氣導(dǎo)致航路網(wǎng)絡(luò)部分拓?fù)浣Y(jié)構(gòu)失效時(shí)，預(yù)計(jì)經(jīng)過(guò)失效結(jié)構(gòu)的航班運(yùn)行受到影響，極易造成大面積的航班延誤。通常采用兩種策略應(yīng)對(duì)航班不正常運(yùn)行問(wèn)題：一是調(diào)整航班的飛行路徑，以改航為主，該策略雖能有效緩解航班延誤，但臨時(shí)航線的啟用往往需要多方密切協(xié)調(diào)和及時(shí)的信息傳遞，且改航路徑一般較長(zhǎng)，會(huì)使航班的飛行成本大幅度增加；二是調(diào)整航班離場(chǎng)時(shí)間，以地面等待為主，該策略將空中延誤轉(zhuǎn)為地面延誤，能夠有效降低航班延誤總成本，卻不利于降低航班延誤率。

國(guó)內(nèi)外許多學(xué)者已經(jīng)從各個(gè)角度對(duì)惡劣天氣下的航班延誤問(wèn)題進(jìn)行了深入研究，本文試圖從航路網(wǎng)絡(luò)修復(fù)這一角度入手研究航班延誤緩解問(wèn)題。航路網(wǎng)絡(luò)修復(fù)是航班原有計(jì)劃路徑因突發(fā)事件影響而失效時(shí)，尋找一條避開(kāi)流量受限區(qū)的修復(fù)路徑，使航班在修復(fù)路徑上運(yùn)行以緩解航班延誤。傳統(tǒng)導(dǎo)航方式下，航空器沿著導(dǎo)航臺(tái)運(yùn)行，導(dǎo)航臺(tái)位置和其他相關(guān)設(shè)備會(huì)影響航路的布局，2008年國(guó)際民航組織提出的基于性能的導(dǎo)航(Performance-Based Navigation，PBN)能夠?qū)w機(jī)先進(jìn)的機(jī)載設(shè)備與衛(wèi)星導(dǎo)航及其他先進(jìn)技術(shù)結(jié)合起來(lái)，覆蓋航路、終端區(qū)到進(jìn)近著陸的所有飛行階段，使航班可以沿任意期望的航跡運(yùn)行[2]。未來(lái)星基導(dǎo)航和其他先進(jìn)技術(shù)的逐漸成熟將大大促進(jìn)PBN技術(shù)的廣泛應(yīng)用，從而為航路網(wǎng)絡(luò)修復(fù)策略的實(shí)施奠定基礎(chǔ)應(yīng)用環(huán)境。目前針對(duì)航路網(wǎng)絡(luò)修復(fù)的研究較少，但是針對(duì)復(fù)雜網(wǎng)絡(luò)修復(fù)的研究已經(jīng)比較廣泛，而航空運(yùn)輸事業(yè)的發(fā)展使航路網(wǎng)絡(luò)逐漸呈現(xiàn)出復(fù)雜網(wǎng)絡(luò)的特性，因此航路網(wǎng)絡(luò)修復(fù)研究可借鑒復(fù)雜網(wǎng)絡(luò)領(lǐng)域的相關(guān)研究。2000年Kodialam和Lakshman提出了一種局部信息修復(fù)策略，以工作路徑上的鏈路帶寬最大值為基礎(chǔ)建立鏈路共享權(quán)重函數(shù)，選擇一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間權(quán)值和最小的路徑代替故障路徑，該修復(fù)策略相比最短路徑算法具有一定的共享性[3]。2003年Li等提出了一種全局信息修復(fù)策略，該策略相比Kodialam和Lakshman的研究將最大帶寬值替換成了帶寬矩陣，彌補(bǔ)了局部信息修復(fù)策略容易陷入局部最優(yōu)的不足[4]。許多學(xué)者在此基礎(chǔ)上進(jìn)行拓展和延伸，繆志敏等將基于拓?fù)鋱D論的修復(fù)策略總結(jié)分為3類：基于拓?fù)浞指钭泳W(wǎng)的網(wǎng)絡(luò)修復(fù)算法、基于拓?fù)浣Y(jié)構(gòu)的路徑修復(fù)算法和基于鏈路的修復(fù)算法[5]。以上修復(fù)策略都是基于網(wǎng)絡(luò)原有拓?fù)浣Y(jié)構(gòu)進(jìn)行研究的，也有很多研究通過(guò)在網(wǎng)絡(luò)中增加邊的方式修復(fù)受損網(wǎng)絡(luò)。按照是否與受損節(jié)點(diǎn)的鄰接節(jié)點(diǎn)相關(guān)將增邊策略分為兩類：一是在重要度比較高的節(jié)點(diǎn)之間增加連邊；二是在受損節(jié)點(diǎn)的鄰接節(jié)點(diǎn)上增加連邊。關(guān)于在重要度高的節(jié)點(diǎn)之間增邊修復(fù)的研究最初有2005年Beygelzimer等提出的通過(guò)隨機(jī)加邊、偏好加邊、隨機(jī)邊重新布線、隨機(jī)鄰邊重新布線、優(yōu)先布線和優(yōu)先隨機(jī)邊重布線6種添加邊的方法改善網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)[6]。后續(xù)很多網(wǎng)絡(luò)修復(fù)研究都是在文獻(xiàn)[6]研究基礎(chǔ)上展開(kāi)的，如2014年Zhang等將任意一對(duì)沒(méi)有連接的節(jié)點(diǎn)i、j的權(quán)值設(shè)為介短函數(shù)(BiBj/Lij)，其中Bi為節(jié)點(diǎn)i的介數(shù)值，Lij為節(jié)點(diǎn)對(duì)i、j的最短距離，選擇在權(quán)值最小的節(jié)點(diǎn)對(duì)增加連邊來(lái)對(duì)受損網(wǎng)絡(luò)進(jìn)行修復(fù)[7]。2018年齊小剛等提出了一種最大化網(wǎng)絡(luò)平均效率的加邊策略，節(jié)點(diǎn)受攻擊后，每一次添加的鏈路都使得網(wǎng)絡(luò)平均效率值增加值最大，直到添加鏈路數(shù)達(dá)到指定數(shù)量[8]。關(guān)于在鄰接節(jié)點(diǎn)上增邊修復(fù)的研究有2005年Hayashi和Miyazaki介紹的兩種基于鄰接節(jié)點(diǎn)互連的網(wǎng)絡(luò)修復(fù)策略，解決了節(jié)點(diǎn)受損導(dǎo)致的連邊受損問(wèn)題[9]。而后不少學(xué)者從連邊補(bǔ)償角度研究網(wǎng)絡(luò)修復(fù)策略，如2016年Ma和Han將新增邊的權(quán)值從節(jié)點(diǎn)度值和變?yōu)榭紤]受損節(jié)點(diǎn)鄰接節(jié)點(diǎn)的權(quán)值函數(shù)wiwj/L′ij，其中wi為節(jié)點(diǎn)i與其鄰接節(jié)點(diǎn)的度值乘積之和，L′ij為節(jié)點(diǎn)i的局部度值，選擇權(quán)值最小的節(jié)點(diǎn)連邊加入網(wǎng)絡(luò)中[10]?？傮w而言，可將復(fù)雜網(wǎng)絡(luò)修復(fù)策略按照是否調(diào)整網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分為兩類：① 網(wǎng)絡(luò)受損后，在原有拓?fù)浣Y(jié)構(gòu)中尋找修復(fù)路徑，使資源在修復(fù)路徑上運(yùn)輸，稱為原有拓?fù)浣Y(jié)構(gòu)修復(fù)策略(Repair Strategy based on Original Topology，RSOT)；② 網(wǎng)絡(luò)受損后在網(wǎng)絡(luò)中增加新連邊，使資源在帶有新邊的修復(fù)路徑上傳輸，稱為拓?fù)浣Y(jié)構(gòu)調(diào)整修復(fù)策略(Repair Strategy based on Adjustment Topology，RSAT)。RSOT的修復(fù)成本較低，但其修復(fù)效果極其依賴網(wǎng)絡(luò)未受損結(jié)構(gòu)，因此該策略不一定使網(wǎng)絡(luò)整體達(dá)到最優(yōu)修復(fù)效果。RSAT能夠在優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的同時(shí)有效提升網(wǎng)絡(luò)性能，然而新路段的引入往往伴隨著協(xié)調(diào)難度大、信息發(fā)布反饋不及時(shí)等問(wèn)題，可能導(dǎo)致修復(fù)成本成倍增大。

惡劣天氣條件下的航路網(wǎng)絡(luò)受損，往往受損面積和影響范圍較大，RSOT可能很難在未受損的結(jié)構(gòu)中找到最優(yōu)的修復(fù)路徑；RSAT引入新的航段對(duì)整個(gè)航路運(yùn)行會(huì)產(chǎn)生一定的影響，所以無(wú)論是單獨(dú)利用RSOT策略或RSAT策略求解，對(duì)于受惡劣天氣影響的航路網(wǎng)絡(luò)的修復(fù)效果并不理想。

本文將結(jié)合兩類復(fù)雜網(wǎng)絡(luò)修復(fù)策略，借鑒離散網(wǎng)絡(luò)設(shè)計(jì)理論，提出航路網(wǎng)絡(luò)修復(fù)優(yōu)化策略。該策略下部分航班采用RSOT，在已有航段構(gòu)成的修復(fù)路徑上運(yùn)行；剩余受影響航班則采用RSAT，在帶有新航段的分流路徑上運(yùn)行。該修復(fù)優(yōu)化策略將：① 考慮航段距離、轉(zhuǎn)彎角度和容量均衡等多重約束對(duì)同一受損路徑上的航班進(jìn)行分批修復(fù)；② 在網(wǎng)絡(luò)中引入少量新航段，建立以最低修復(fù)成本為目標(biāo)函數(shù)的雙層修復(fù)優(yōu)化模型，修復(fù)成本包含飛行成本增量和協(xié)調(diào)成本，分別表示對(duì)正常運(yùn)行航班的干擾程度和新航段的啟用難度，最低修復(fù)成本意味著修復(fù)策略對(duì)正常運(yùn)行航班干擾足夠小且航路網(wǎng)絡(luò)調(diào)整盡可能?。虎?有利于增大理想路徑的搜索效率，且能夠有效剔除距離較長(zhǎng)的分流路徑。

1 航路網(wǎng)絡(luò)修復(fù)場(chǎng)景

1.1 惡劣天氣飛行受限區(qū)

在航空領(lǐng)域，惡劣天氣包含雷暴、積冰、閃電、冰雹、下?lián)舯┝?、低空風(fēng)切變和暴雨等會(huì)影響航空器安全飛行的天氣。以雷暴為惡劣天氣的典型代表展開(kāi)研究，原因如下：① 在諸多惡劣天氣中，對(duì)航路飛行造成嚴(yán)重影響的主要天氣是雷暴；② 雷暴強(qiáng)度可以用雷達(dá)基本反射率量化表示[11]，這一氣象產(chǎn)品可由多普勒氣象雷達(dá)獲取，其他惡劣天氣如積冰、顛簸和風(fēng)切變等很難量化。

所以惡劣天氣飛行受限區(qū)可以用雷暴的范圍來(lái)表示，由于雷暴的范圍通常呈現(xiàn)不規(guī)則的形狀，通常使用規(guī)則的圖形規(guī)劃雷暴的邊界，常用的方法包括外接法[12]和凸多邊形算法[13]，并且根據(jù)雷達(dá)反射率的大小來(lái)判斷雷暴的惡劣程度，雷達(dá)反射率大于等于41 dBZ的區(qū)域是禁止航班穿越飛行的[14]，即為惡劣天氣飛行受限區(qū)。本文采用Graham算法[15]對(duì)不規(guī)則的惡劣天氣受限區(qū)進(jìn)行規(guī)則化界定。

1.2 航路網(wǎng)絡(luò)修復(fù)范圍

惡劣天氣發(fā)生具有局部性和隨機(jī)性，航路網(wǎng)絡(luò)修復(fù)在局部范圍進(jìn)行。航段和航路點(diǎn)失效后，假定當(dāng)前航段和航路點(diǎn)都不可直接修復(fù)，尤其是航路點(diǎn)失效后，與之連接的航段因無(wú)法完成運(yùn)輸任務(wù)而自動(dòng)失效。惡劣天氣對(duì)航路網(wǎng)絡(luò)攻擊形成3種失效狀態(tài)，如圖1所示，多邊形區(qū)域是惡劣天氣飛行受限區(qū)。

第1類修復(fù)范圍：惡劣天氣發(fā)生在某一航段上，航段連接的航路點(diǎn)沒(méi)有受到影響，如圖1(a)所示，此時(shí)航段AB失效，經(jīng)過(guò)該航段的航班在航路點(diǎn)AB之間尋找修復(fù)路徑。

圖1 航路網(wǎng)絡(luò)的3種受損模式Fig.1 Three disrupted modes of air route network

第2類修復(fù)范圍：惡劣天氣發(fā)生在某一航路點(diǎn)及其周圍的航段上，鄰接節(jié)點(diǎn)未受影響，如圖1(b)所示，此時(shí)航路點(diǎn)C失效，航段CD、CE、CF和CG都失效，經(jīng)過(guò)航路點(diǎn)C的航班在其鄰接節(jié)點(diǎn)之間尋找修復(fù)路徑。

第3類修復(fù)范圍：惡劣天氣同時(shí)發(fā)生在多個(gè)航路點(diǎn)和航段上，如圖1(c)所示；此時(shí)航路點(diǎn)C和D失效，與兩個(gè)航路點(diǎn)相連的航段也失效，經(jīng)過(guò)航路點(diǎn)C和D的航班在其周圍完好的節(jié)點(diǎn)對(duì)之間尋找修復(fù)路徑。

為了有效搜索受影響航班的修復(fù)路徑，將修復(fù)路徑的起終點(diǎn)定義為有效起訖節(jié)點(diǎn)對(duì)。對(duì)受損航段而言，優(yōu)先選擇當(dāng)前航段的兩端航路點(diǎn)作為有效起訖節(jié)點(diǎn)對(duì)；對(duì)受損航路點(diǎn)而言，優(yōu)先選擇故障節(jié)點(diǎn)周圍未受損的鄰接節(jié)點(diǎn)作為有效起訖節(jié)點(diǎn)對(duì)。

1.3 修復(fù)路徑備用航段

同一個(gè)有效起訖節(jié)點(diǎn)對(duì)在采用不同修復(fù)策略時(shí)對(duì)應(yīng)的備用航段集是不同的。RSOT中備用航段集由原有航路網(wǎng)絡(luò)中未受惡劣天氣影響的航段組成。RSAT將航路網(wǎng)絡(luò)變成全聯(lián)通網(wǎng)絡(luò)，刪除經(jīng)過(guò)惡劣天氣飛行受限區(qū)的航段、航路點(diǎn)以及受損航路點(diǎn)連接的航段后，剩余航段組成備用航段集。

2 航路網(wǎng)絡(luò)修復(fù)優(yōu)化策略

離散網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題(Discrete Network Design Problem，DNDP)主要是從備選路段方案中選擇一個(gè)最優(yōu)的路段添加方案添加到現(xiàn)有網(wǎng)絡(luò)中，使得網(wǎng)絡(luò)系統(tǒng)性能更優(yōu)，以某一路段為例，將其添加到現(xiàn)有網(wǎng)絡(luò)時(shí)，決策變量為1，反之決策變量為0[16]。將其思想應(yīng)用于航路網(wǎng)絡(luò)修復(fù)問(wèn)題，假設(shè)有n個(gè)有效起訖節(jié)點(diǎn)對(duì)之間的航班需要進(jìn)行重分配，每個(gè)有效起訖節(jié)點(diǎn)對(duì)有兩種選擇方式，選擇RSOT時(shí)，決策變量值取0；選擇RSAT時(shí)，決策變量值取1。n個(gè)有效起訖節(jié)點(diǎn)對(duì)的選擇對(duì)應(yīng)2n種決策方案，不同決策方案用Uy(y= 1,2,3,…,2n)表示。

航路網(wǎng)絡(luò)修復(fù)優(yōu)化策略(Repair Optimization Strategy，ROS)是從2n個(gè)決策方案中選擇最優(yōu)的方案，使得總修復(fù)成本最低。假設(shè)受損網(wǎng)絡(luò)為G0，原有航段集為A0，航班重分配的有效起訖節(jié)點(diǎn)對(duì)集合為Pnode。假設(shè)有x對(duì)選擇RSOT，對(duì)應(yīng)有效起訖節(jié)點(diǎn)對(duì)集合為Nx，對(duì)應(yīng)修復(fù)路徑上的航段集合為A1。剩余l(xiāng)(l=n-x)對(duì)起訖節(jié)點(diǎn)選擇RSAT，對(duì)應(yīng)有效起訖節(jié)點(diǎn)對(duì)集合為Nl，對(duì)應(yīng)修復(fù)路徑上的航段集合為A2，Nx∪Nl=Pnode。航路網(wǎng)絡(luò)的修復(fù)優(yōu)化模型可描述為雙層整數(shù)規(guī)劃模型。

2.1 模型搭建

2.1.1 上層模型

上層模型以航路網(wǎng)絡(luò)修復(fù)成本最小為目標(biāo)。修復(fù)成本共包含兩部分：一部分是航空器相比原有飛行路徑在分流路徑上運(yùn)行增加的飛行成本費(fèi)用，飛行成本費(fèi)用越小，對(duì)原有未受影響航班的干擾越?。涣硪徊糠质切略龊蕉螏?lái)的空域協(xié)調(diào)、通信等的綜合協(xié)調(diào)費(fèi)用。

上層模型用公式表達(dá)為

(1)

(2)

2.1.2 下層模型

下層模型為多約束非均衡分配模型，以有效起訖節(jié)點(diǎn)對(duì)上的修復(fù)路徑距離和最小為目標(biāo)，在容流平衡約束、流量重分配約束、角度約束和轉(zhuǎn)彎約束等多重約束下，尋找修復(fù)路徑完成交通流分配。

(3)

(4)

(5)

θ≥ 90°

(6)

dij≥ 7.4 km

(7)

(8)

(9)

式(4)為容流平衡約束。有效起訖節(jié)點(diǎn)對(duì)s,t之間任意一條路經(jīng)上的交通流量應(yīng)小于等于路徑上的最小航路點(diǎn)容量，在這里容量為航路點(diǎn)通行能力。

式(5)為流量重分配約束。有效節(jié)點(diǎn)對(duì)s,t之間共有M條路徑用于交通流重分配，前M-1條路徑上的重分配流量等于當(dāng)前路徑的冗余容量，最后一條路徑上的重分配流量小于等于該路徑的冗余容量。

式(6)為角度約束。出于航路安全飛行角度考慮，航段之間的夾角θ應(yīng)大于等于90°，即航空器航向的最大改變量應(yīng)小于等于90°[17]。

式(7)為轉(zhuǎn)彎約束。為滿足轉(zhuǎn)彎安全性要求，航段長(zhǎng)度應(yīng)大于7.4 km[18]。

式(8)為航段流量。

式(9)為非負(fù)約束，即模型中所有變量都非負(fù)。

2.2 模型求解

粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法屬于啟發(fā)優(yōu)化算法，因概念簡(jiǎn)單、參數(shù)少，求解簡(jiǎn)單快速，計(jì)算結(jié)果精度高偏差小，應(yīng)用十分廣泛，因此采用PSO算法求解修復(fù)優(yōu)化模型。

2.2.1 PSO算法求解

粒子的速度、位置和權(quán)重因子按照式(10)～式(12)進(jìn)行更新[19]：

(10)

(11)

(12)

基于IPSO的修復(fù)優(yōu)化模型的求解步驟如下：

Step 1初始化設(shè)置。設(shè)置最大速度Vmax，最小速度Vmin，最大慣性權(quán)因子wmax，最小慣性權(quán)因子wmin，加速常數(shù)c1、c2，初始粒子數(shù)為m，最大迭代次數(shù)T，位置最大值Zmax，位置最小值Zmin，粒子的初始位置z0和初始速度v0。

Step 5重復(fù)Step 2～Step 4，直到達(dá)到指定迭代次數(shù)，輸出群體最優(yōu)適應(yīng)度和最優(yōu)位置。

2.2.2 下層模型求解

下層模型為多約束交通流分配模型，采用K最短路徑算法在多重約束下尋找兩節(jié)點(diǎn)之間的多條較短路徑，常用Yen’s算法求解[21]。在找到兩節(jié)點(diǎn)對(duì)之間的m條路徑后，將有效起訖節(jié)點(diǎn)對(duì)之間的交通量按照每個(gè)路徑的冗余容量大小分為m份分配，在分流路徑不足或者找不到分流路徑時(shí)，對(duì)應(yīng)航班選擇地面等待策略。計(jì)算步驟如下：

Step 1根據(jù)惡劣天氣影響范圍尋找所有的有效起訖節(jié)點(diǎn)對(duì)，將其存于集合Pnode中，假設(shè)共有num個(gè)有效起訖節(jié)點(diǎn)對(duì)。

Step 2根據(jù)轉(zhuǎn)彎約束，刪除備用航段集中長(zhǎng)度小于7.4 km的航段，構(gòu)建可用備用航段集合。

Step 3基于可用備用航段集，采用Yen’s算法計(jì)算有效起訖節(jié)點(diǎn)之間的前K條最短路徑，存儲(chǔ)于集合Path中。

Step 4根據(jù)角度約束，刪除Path中存在航段夾角小于90°的路徑，更新集合Path。

Step 5根據(jù)流量重分配約束，判斷有效起訖節(jié)點(diǎn)對(duì)流量重分配需要的可用路徑數(shù)。

Step 6對(duì)于有效起訖節(jié)點(diǎn)對(duì)，若可用路徑數(shù)不足，適當(dāng)增大K值，令K=rK，其中r為增大系數(shù)，取值隨實(shí)際情況而定，重復(fù)Step 4～Step 6，若可用路徑數(shù)仍然不足，該節(jié)點(diǎn)對(duì)之間的部分航班選擇地面等待策略。

Step 7可用路徑足夠時(shí)，將有效起訖節(jié)點(diǎn)對(duì)之間的所有受損航班按照每條可用路徑的冗余容量值進(jìn)行分批重分配，重復(fù)Step 4～Step 7，直到num個(gè)有效起訖節(jié)點(diǎn)對(duì)都結(jié)束運(yùn)算。

需要注意的是，在RSAT中，將航路網(wǎng)絡(luò)變成全聯(lián)通網(wǎng)絡(luò)只是為了增大備用航段集，在對(duì)受損航班重分配后，受損航路網(wǎng)絡(luò)中增加的航段只有修復(fù)路徑上的新航段，而非RSAT下備用航段集中的所有航段。

3 仿真實(shí)驗(yàn)

3.1 案例航路網(wǎng)絡(luò)描述

航路網(wǎng)絡(luò)由航路點(diǎn)和使得網(wǎng)絡(luò)連通的航路組成。航路點(diǎn)包含各類導(dǎo)航臺(tái)和多種交叉點(diǎn)，航路點(diǎn)兩兩連接構(gòu)成航段，多個(gè)航段連接形成航路。在構(gòu)建航路網(wǎng)絡(luò)模型時(shí)將航路點(diǎn)和航段簡(jiǎn)化在二維平面中，忽略孤立航路點(diǎn)。根據(jù)復(fù)雜網(wǎng)絡(luò)理論，假設(shè)航路點(diǎn)是網(wǎng)絡(luò)中的節(jié)點(diǎn)vi，航段是網(wǎng)絡(luò)中的邊或者鏈接eij。將航路網(wǎng)絡(luò)記為G={vi,eij,n}，其中n取值為0或1(若任何兩個(gè)航路點(diǎn)vi、vj間存在航段，則n=1；反之n= 0)。

3.1.1 案例網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

根據(jù)2018年中國(guó)民航國(guó)內(nèi)航空資料匯編更新的航行信息，統(tǒng)計(jì)上海市、江蘇省、安徽省、江西省、浙江省和福建省6個(gè)地區(qū)范圍中的航路點(diǎn)和航段，構(gòu)建成案例航路網(wǎng)絡(luò)。案例航路網(wǎng)絡(luò)由246個(gè)航路點(diǎn)、361條航段構(gòu)成。

3.1.2 運(yùn)行數(shù)據(jù)

為深入研究惡劣天氣對(duì)航路網(wǎng)絡(luò)運(yùn)行的具體影響，需要對(duì)航路網(wǎng)絡(luò)上的交通流分布進(jìn)行統(tǒng)計(jì)。7、8月份是一年中雷暴發(fā)生比較頻繁的時(shí)段，選取2018年8月份的案例航路網(wǎng)絡(luò)上的航班飛行計(jì)劃數(shù)據(jù)作為仿真運(yùn)行數(shù)據(jù)。

流量高峰時(shí)段的航路網(wǎng)絡(luò)運(yùn)行狀態(tài)相比其他時(shí)段更加復(fù)雜，對(duì)繁忙時(shí)段的航路網(wǎng)絡(luò)受損修復(fù)進(jìn)行深入研究，將更有利于受損航路網(wǎng)絡(luò)的快速恢復(fù)。選取2018年8月16日交通流高峰時(shí)段的案例航路網(wǎng)絡(luò)運(yùn)行數(shù)據(jù)為仿真數(shù)據(jù)。統(tǒng)計(jì)當(dāng)天00:00～24:00之間的小時(shí)航班總量，發(fā)現(xiàn)8:00～10:00之間的交通量是最多的，共有752個(gè)航班正在運(yùn)行。故后續(xù)仿真實(shí)驗(yàn)以8:00～10:00之間的航班運(yùn)行數(shù)據(jù)為基礎(chǔ)數(shù)據(jù)。

3.1.3 仿真環(huán)境

利用Windows 10操作系統(tǒng)中的MATLAB2017a軟件進(jìn)行編程，在處理器為Intel?CoreTMi7-7700、內(nèi)存為16 G的PC機(jī)上進(jìn)行仿真，仿真采用2018年8月的歷史雷達(dá)軌跡數(shù)據(jù)、氣象數(shù)據(jù)以及全國(guó)航路網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)構(gòu)建惡劣天氣條件下的受損航路網(wǎng)絡(luò)。

在確定空域中惡劣天氣飛行受限區(qū)后，計(jì)算案例航路網(wǎng)絡(luò)的受損航段和航路點(diǎn)，圖2為案例航路網(wǎng)絡(luò)的受損狀況，圖中紅色多邊形覆蓋的區(qū)域是惡劣天氣發(fā)生的區(qū)域，其具體信息如表1所示，航路網(wǎng)絡(luò)小面積受損會(huì)導(dǎo)致將近1/3的航班不正常運(yùn)行，也反映了惡劣天氣對(duì)航路網(wǎng)絡(luò)運(yùn)行的影響程度。

圖2 案例航路網(wǎng)絡(luò)的受損狀態(tài)Fig.2 Disrupted state of typical air route network

表1 航路網(wǎng)絡(luò)受損信息Table 1 Information of disrupted air route network

3.2 航路網(wǎng)絡(luò)修復(fù)優(yōu)化仿真

3.2.1 修復(fù)成本系數(shù)設(shè)置

飛行成本系數(shù)α為單架航空器單位距離上的飛行成本，用航路使用費(fèi)計(jì)算。2012年中國(guó)民用航空局聯(lián)合國(guó)家發(fā)展改革委發(fā)布了《關(guān)于調(diào)整民航進(jìn)近指揮費(fèi)和航路費(fèi)有關(guān)問(wèn)題的通知(民航發(fā)[2012]59號(hào))》，其中規(guī)定了內(nèi)地航空公司國(guó)際及港澳航班航路收費(fèi)標(biāo)準(zhǔn)。本文按照最高收費(fèi)標(biāo)準(zhǔn)取α= 1.5 元·km-1·架次-1。

以飛行成本系數(shù)為基礎(chǔ)，假設(shè)協(xié)調(diào)成本系數(shù)β= 2.0 元·km-1·架次-1。在協(xié)調(diào)成本系數(shù)的基礎(chǔ)上，考慮到交通流密度對(duì)航班飛行的影響，認(rèn)為協(xié)調(diào)難度系數(shù)γ與航段交通量f相關(guān)，交通量區(qū)間不同，協(xié)調(diào)難度系數(shù)不同。修復(fù)成本系數(shù)設(shè)置如表2所示。

表2 修復(fù)成本系數(shù)設(shè)置Table 2 Settings of repair cost coefficient

3.2.2 有效起訖節(jié)點(diǎn)對(duì)和備用航段集

1) 有效起訖節(jié)點(diǎn)對(duì)

根據(jù)1.2節(jié)的定義，計(jì)算案例網(wǎng)絡(luò)受損后的有效起訖節(jié)點(diǎn)對(duì)，共有15對(duì)，相關(guān)信息如表3所示。分別采用RSOT和RSAT尋找所有有效起訖節(jié)點(diǎn)對(duì)的修復(fù)路徑，發(fā)現(xiàn)有效起訖節(jié)點(diǎn)對(duì)“ADGOL-KIKEG-HFE”和“ADGOL-VILID”在采用RSOT時(shí)，找不到分流路徑，而在RSAT下，這兩個(gè)節(jié)點(diǎn)對(duì)都能找到對(duì)應(yīng)的分流路徑，故這兩個(gè)節(jié)點(diǎn)對(duì)默認(rèn)采用RSAT，不參與修復(fù)優(yōu)化。RSAT中有效起訖節(jié)點(diǎn)對(duì)“SHZ-BK”之間的分流路徑與RSOT相同，默認(rèn)該節(jié)點(diǎn)對(duì)采用RSOT，不參與修復(fù)優(yōu)化。故修復(fù)優(yōu)化仿真實(shí)驗(yàn)中有12個(gè)有效起訖節(jié)點(diǎn)對(duì)，對(duì)應(yīng)著4 096種決策方案。

表3 有效起訖節(jié)點(diǎn)對(duì)信息Table 3 Information of valid origin-destination nodes

2) 修復(fù)備用航段集

根據(jù)2.2節(jié)計(jì)算不同修復(fù)策略下的修復(fù)路徑備用航段，RSOT下的可用航段數(shù)為325條，RSAT下的可用航段數(shù)為19 818條。

3.2.3 航路網(wǎng)絡(luò)修復(fù)優(yōu)化結(jié)果

隨機(jī)生成20個(gè)粒子，初始化粒子速度，將每個(gè)粒子的位置代入下層模型求解航段交通量和路徑距離，反饋到上層計(jì)算適應(yīng)度值，根據(jù)式(10)～式(12)更新各粒子的速度和位置，迭代1 000次后得到最低修復(fù)成本，運(yùn)算耗時(shí)3 763 s。

IPSO參數(shù)設(shè)置如表4所示。

表4 IPSO參數(shù)初始化設(shè)置Table 4 Initial settings for IPSO parameter

圖3為粒子適應(yīng)度曲線，可以發(fā)現(xiàn)IPSO求解該模型時(shí)收斂較快，在第63次計(jì)算時(shí)群體適應(yīng)度達(dá)到最優(yōu)，在圖中用實(shí)心三角形標(biāo)注，此時(shí)修復(fù)成本為75 016.65元，適應(yīng)度對(duì)應(yīng)位置為‘705’，對(duì)應(yīng)決策方案為U=‘001011000001’。

圖3 IPSO迭代適應(yīng)度曲線Fig.3 Iterative fitness curves of IPSO

將不參與修復(fù)優(yōu)化決策的3個(gè)節(jié)點(diǎn)對(duì)對(duì)應(yīng)的決策變量并入最終的決策方案中，最優(yōu)修復(fù)決策方案變更為U*= ‘001101101000001’。將最優(yōu)決策方案的具體情況列入表5。

表5 最優(yōu)決策方案Table 5 Optimal decision scheme

3.3 結(jié)果分析

以“PANBO-OSONO-REMAX/KHN”有效起訖節(jié)點(diǎn)對(duì)為例，對(duì)修復(fù)策略進(jìn)行詳細(xì)說(shuō)明。由于OSONO航路點(diǎn)受到較大面積的惡劣天氣的影響，導(dǎo)致OSONO航路點(diǎn)連接的航路也受到影響。有廣州飛往南昌以及廣州飛往南京的兩個(gè)航班，其原本飛行路徑分別為“PANBO-OSONO-REMAX”和“PANBO-OSONO-KHN”，3種修復(fù)策略得到的修復(fù)路徑如表6所示，詳細(xì)路徑如圖4所示，從不同策略生成的修復(fù)路徑可以很直觀地看出，ROS修復(fù)策略相比于其他兩種修復(fù)策略對(duì)惡劣天氣影響下航路網(wǎng)絡(luò)修復(fù)更有效，飛行距離更短，如在廣州飛往南京的飛行路徑選擇上，RSAT比RSOT和ROS修復(fù)策略更長(zhǎng)，而在廣州飛往南昌的飛行路徑選擇上，RSOT比RSAT和ROS修復(fù)策略更長(zhǎng)，相比之下，ROS修復(fù)策略的經(jīng)濟(jì)性更好。

分別采用兩類基礎(chǔ)修復(fù)策略對(duì)受損后的航路網(wǎng)絡(luò)進(jìn)行修復(fù)，將修復(fù)結(jié)果與修復(fù)優(yōu)化策略結(jié)果進(jìn)行對(duì)比分析，同時(shí)還將計(jì)算結(jié)果與真實(shí)運(yùn)行情況進(jìn)行對(duì)比，以驗(yàn)證修復(fù)優(yōu)化策略的有效性。從局部和全局兩個(gè)角度出發(fā)，評(píng)估不同修復(fù)策略下航路網(wǎng)絡(luò)的運(yùn)行狀態(tài)。

從局部角度來(lái)看，能夠直接反映不同修復(fù)策略有效性的指標(biāo)為受損航班恢復(fù)比例。修復(fù)成本反映了修復(fù)策略下航路網(wǎng)絡(luò)運(yùn)行增加的額外成本，但其不能反映修復(fù)策略對(duì)整個(gè)航路網(wǎng)絡(luò)運(yùn)行性能的影響，其和受損航班恢復(fù)比例屬于評(píng)估網(wǎng)絡(luò)局部變化的指標(biāo)。

表6 3類修復(fù)策略的案例分析Table 6 Case analysis of three types of repair strategies

圖4 3類修復(fù)策略案例Fig.4 Case of three types of repair strategies

從全局角度來(lái)看，通過(guò)運(yùn)算耗時(shí)評(píng)估不同修復(fù)策略的計(jì)算速度和實(shí)效性。通過(guò)計(jì)算整體運(yùn)行環(huán)境的延誤時(shí)間對(duì)比反映不同修復(fù)策略對(duì)惡劣天氣的應(yīng)對(duì)能力。網(wǎng)絡(luò)運(yùn)行效率[22]反映不同情況下網(wǎng)絡(luò)性能的變化，可反映修復(fù)策略對(duì)航路網(wǎng)絡(luò)整體運(yùn)行的影響。計(jì)算公式為

(13)

式中：Ef為網(wǎng)絡(luò)運(yùn)行效率；fx,y為節(jié)點(diǎn)x、y之間最短路徑上的運(yùn)行航班量。

表7中詳細(xì)列入了3類修復(fù)策略與實(shí)際運(yùn)行情況對(duì)應(yīng)的指標(biāo)值。

從航班恢復(fù)比例來(lái)看，ROS和RSAT下航班恢復(fù)比例相同且大于RSOT對(duì)應(yīng)的值。RSOT下航路網(wǎng)絡(luò)備用航段數(shù)較少，部分航班找不到分流路徑，無(wú)法恢復(fù)正常運(yùn)行；RSAT和ROS中新航段的引入增大了搜索范圍，加快了搜索效率，使得所有受天氣影響的航班都能找到有效分流路徑。

從修復(fù)成本來(lái)看，ROS下航路網(wǎng)絡(luò)修復(fù)成本最低，其次是RSOT，RSAT下航路網(wǎng)絡(luò)修復(fù)成本最高。有效起訖節(jié)點(diǎn)對(duì)之間的交通量是固定的，RSOT基于原有網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行修復(fù)，生成的分流路徑大多長(zhǎng)于計(jì)劃飛行路徑，航班飛行成本也對(duì)應(yīng)增大；RSAT引入了部分新航段，分流路徑相比RSOT大多較短，然而新航段帶來(lái)了高額的協(xié)調(diào)費(fèi)用。ROS采用離散網(wǎng)絡(luò)設(shè)計(jì)思想將兩類基礎(chǔ)修復(fù)策略結(jié)合在一起，避免了使用距離較長(zhǎng)的航段，也減少了新航段的數(shù)量，修復(fù)成本相比RSOT和RSAT都低。

從總延誤時(shí)間來(lái)看，RSAT下的總延誤時(shí)間最短，其次是ROS，RSOT下總延誤時(shí)間最長(zhǎng)。總延誤時(shí)間能夠反映出在不同修復(fù)策略下的航路網(wǎng)絡(luò)對(duì)于特殊情況的應(yīng)對(duì)能力，總延誤時(shí)間越短，應(yīng)對(duì)能力越強(qiáng)，遭遇惡劣天氣時(shí)，RSAT引入部分新航段，能夠立即做出反應(yīng)，而RSOT只能針對(duì)未受損網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行修復(fù)，相比之下應(yīng)對(duì)能力較弱。ROS將兩種策略結(jié)合，一定程度上提高了對(duì)特殊情況的應(yīng)對(duì)能力。但無(wú)論哪種修復(fù)策略，相比于實(shí)際運(yùn)行情況，航路網(wǎng)絡(luò)的應(yīng)對(duì)能力均得到了改善。

從網(wǎng)絡(luò)運(yùn)行效率來(lái)看，RSOT下航路網(wǎng)絡(luò)的運(yùn)行效率最高，其次是ROS，RSAT下航路網(wǎng)絡(luò)的運(yùn)行效率最低。運(yùn)行效率反映了航路網(wǎng)絡(luò)中交通流分布的聚集特征，也反映了修復(fù)策略對(duì)受損航路網(wǎng)絡(luò)運(yùn)行水平的影響?？梢园l(fā)現(xiàn)，采取RSOT后，航路網(wǎng)絡(luò)流量分布有很強(qiáng)的聚集性，ROS次之，RSAT集聚性特征是最弱的。交通量分布的聚集性高意味著對(duì)應(yīng)管制扇區(qū)內(nèi)管制員工作負(fù)荷較大且容易過(guò)載，航路擁堵風(fēng)險(xiǎn)大和航空器沖突概率高。修復(fù)策略RSAT和ROS能夠?qū)⒔煌鞣稚⒌搅髁肯鄬?duì)少的航段，有利于降低航空器沖突和航路擁堵概率，從而減緩航班延誤程度。

綜合考慮認(rèn)為ROS是適用性最好、經(jīng)濟(jì)性最佳的修復(fù)策略，其在使用最低修復(fù)成本使所有受到影響的航班都恢復(fù)正常運(yùn)行的情況下，保證了整個(gè)航路網(wǎng)絡(luò)的高效暢通運(yùn)行。

4 結(jié) 論

1) 針對(duì)惡劣天氣條件下的航路網(wǎng)絡(luò)修復(fù)問(wèn)題，將RSOT和RSAT兩種修復(fù)策略結(jié)合，避免了RSOT過(guò)于依賴網(wǎng)絡(luò)未受損結(jié)構(gòu)以及RSAT由于協(xié)調(diào)難度大而導(dǎo)致的修復(fù)成本增加的問(wèn)題，有效地綜合兩種修復(fù)策略的優(yōu)勢(shì)，提高了網(wǎng)絡(luò)性能。

2) 航路網(wǎng)絡(luò)修復(fù)優(yōu)化策略不再簡(jiǎn)單以路徑最短或者風(fēng)險(xiǎn)最低為修復(fù)目標(biāo)，而是考慮到航班運(yùn)行經(jīng)濟(jì)成本，基于DNDP思想建立了雙層規(guī)劃優(yōu)化模型，上層以修復(fù)成本最低為目標(biāo)，下層以滿足多重約束的路徑最短為目標(biāo)，充分考慮了航班恢復(fù)運(yùn)行的安全性、經(jīng)濟(jì)性、可行性和暢通性，同時(shí)該模型在滿足“四性”的基礎(chǔ)上，相比兩類基礎(chǔ)修復(fù)策略，既能合理利用原有拓?fù)浣Y(jié)構(gòu)，又能解決新航段產(chǎn)生巨額協(xié)調(diào)費(fèi)用的難題，在網(wǎng)絡(luò)修復(fù)成本最低的情況下，有效地提高了網(wǎng)絡(luò)的運(yùn)行性能。

3) 應(yīng)用IPSO求解修復(fù)優(yōu)化模型的優(yōu)點(diǎn)有：作為啟發(fā)式算法，IPSO中需要設(shè)置的參數(shù)很少，減小了因參數(shù)設(shè)置不合理導(dǎo)致求解結(jié)果不準(zhǔn)確的可能性；解編碼的存在解決了傳統(tǒng)PSO算法很難求解離散網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題的難點(diǎn)；IPSO解決了枚舉法只能求解小規(guī)模問(wèn)題的局限性。

4) 從局部和全局兩個(gè)角度評(píng)估了修復(fù)優(yōu)化策略的有效性和優(yōu)越性。局部指標(biāo)包含航班恢復(fù)比例和修復(fù)成本，這兩個(gè)指標(biāo)反映了修復(fù)優(yōu)化策略對(duì)受損航班運(yùn)行的修復(fù)效果，也體現(xiàn)了修復(fù)優(yōu)化相比兩類基礎(chǔ)修復(fù)策略的優(yōu)越性；全局指標(biāo)為運(yùn)算耗時(shí)、總延誤時(shí)長(zhǎng)和運(yùn)行效率，反映了修復(fù)優(yōu)化策略對(duì)航路網(wǎng)絡(luò)運(yùn)行的整體作用。相比于其他修復(fù)策略，該策略下航路網(wǎng)絡(luò)上交通流的聚集性一般，對(duì)于減緩航路擁堵和航班延誤、減輕航空器延誤都十分有效，提高了航路網(wǎng)絡(luò)對(duì)特殊情況的應(yīng)對(duì)能力。

5) 研究給未來(lái)惡劣天氣下航路網(wǎng)絡(luò)的暢通運(yùn)行提供了修復(fù)技術(shù)支持，對(duì)于減緩航路擁堵和航班延誤有極大的意義。但本文僅針對(duì)惡劣天氣條件下航路網(wǎng)絡(luò)修復(fù)這一問(wèn)題的解決策略開(kāi)展研究，尚未涉及運(yùn)行層面的相關(guān)細(xì)節(jié)。在對(duì)修復(fù)策略的實(shí)際應(yīng)用方面，需要針對(duì)運(yùn)行中的相關(guān)問(wèn)題，如氣象的動(dòng)態(tài)變化趨勢(shì)、扇區(qū)邊界約束以及航路運(yùn)行限制等等，開(kāi)展更深入的研究和分析，進(jìn)一步提高航路網(wǎng)絡(luò)修復(fù)優(yōu)化策略的實(shí)用性。

[21] YEN J Y. Finding theKshortest loopless paths in a network[J]. Management Science, 1971, 17: 712-716.