改航路徑規(guī)劃問題研究綜述

王 瑛，周楚涵

(空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安，710051)

2019年我國(guó)民航旅客吞吐量達(dá)到13.51億人次，國(guó)內(nèi)航空比2018年增長(zhǎng)6.5%[1]。隨著我國(guó)經(jīng)濟(jì)的快速增長(zhǎng)，民航運(yùn)輸業(yè)得到了長(zhǎng)足發(fā)展，已成為改善國(guó)民生活、推動(dòng)現(xiàn)代化建設(shè)的重要產(chǎn)業(yè)。

隨著民航運(yùn)輸業(yè)的迅猛發(fā)展，由危險(xiǎn)天氣、機(jī)械故障、航天發(fā)射、軍事管制等不確定隨機(jī)因素造成的航班延誤、旅客滯留和空域堵塞等現(xiàn)象屢見不鮮，嚴(yán)重影響了民航運(yùn)輸?shù)陌踩c效率，造成了重大經(jīng)濟(jì)損失。

當(dāng)前，實(shí)戰(zhàn)化訓(xùn)練和演習(xí)的頻率與強(qiáng)度不斷提升，構(gòu)建安全、高效、靈活的空管運(yùn)行體系，既是提升我國(guó)空域資源使用效率的現(xiàn)實(shí)需要，也是滿足軍事需求的必由之路。軍事訓(xùn)練、軍事演習(xí)必將成為影響民航飛行的重要因素，主要表現(xiàn)在以下幾個(gè)方面：

1)空域使用需求增多導(dǎo)致空中交通復(fù)雜度不斷提升，飛行小時(shí)和起降架次持續(xù)增長(zhǎng)，飛行密度不斷增大。隨著軍民航對(duì)空域使用需求的增多，空中交通復(fù)雜度不斷提升，空域使用僵化、流量調(diào)控不力等制約效率提升的瓶頸效應(yīng)急劇放大，需求與容量、安全與效率等矛盾日益尖銳。

2)軍民航相互影響耦合效應(yīng)增強(qiáng)。由于空域資源的有限性和共享性，必然帶來軍民航之間相互影響和制約，耦合效應(yīng)增強(qiáng)。特別是軍事演訓(xùn)任務(wù)導(dǎo)致的臨時(shí)性空域管制，導(dǎo)致民航航班停飛、延誤、繞飛等，空域管理面臨較大的不確定性。

3)軍民航管理的要求和特點(diǎn)不同加大了空中交通管理的難度。軍民航在空域用戶多樣性、管控模式、管控原則等方面具有明顯不同，對(duì)空域管理協(xié)同化、精細(xì)化和實(shí)時(shí)性提出了更高的要求。

傳統(tǒng)的被動(dòng)地面等待策略(ground holding policy,GHP)僅能在一定程度上保證飛行安全性，然而無法根本解決空域利用率不高的問題。因此，人們將研究重心轉(zhuǎn)向改航路徑規(guī)劃(reroute planning,RP)，且已經(jīng)取得了大量的成果。

本文對(duì)改航路徑規(guī)劃領(lǐng)域現(xiàn)有研究成果進(jìn)行分析綜述，并在軍事訓(xùn)練和軍事演習(xí)頻率、強(qiáng)度大幅提升的背景下，對(duì)改航路徑規(guī)劃的重點(diǎn)研究方向進(jìn)行了預(yù)測(cè)和展望。

1 改航路徑規(guī)劃影響因素

危險(xiǎn)天氣是傳統(tǒng)領(lǐng)域內(nèi)影響改航路徑規(guī)劃的主要因素，由此造成的空域沖突等問題屢有發(fā)生[2]。同時(shí)，隨著我國(guó)軍民融合戰(zhàn)略的持續(xù)推進(jìn)，非戰(zhàn)爭(zhēng)軍事行動(dòng)和航天發(fā)射等活動(dòng)的強(qiáng)度和頻次逐年增高，給軍民航飛行安全和空域管理帶來新的風(fēng)險(xiǎn)與挑戰(zhàn)[3]。

1.1 危險(xiǎn)天氣

危險(xiǎn)天氣主要是指雷暴、湍流、颶風(fēng)、強(qiáng)對(duì)流和風(fēng)切變等中小規(guī)模天氣系統(tǒng)[3]。危險(xiǎn)天氣區(qū)域根據(jù)其分布差異分為：塊狀區(qū)域、帶狀區(qū)域和散點(diǎn)區(qū)域。目前，針對(duì)危險(xiǎn)天氣影響下的改航路徑規(guī)劃研究主要包括：空域劃設(shè)、單/多航班改航路徑規(guī)劃和空域流量分配等問題。

Dixon等人最早于1993年研究了危險(xiǎn)天氣影響下的改航路徑規(guī)劃問題[4]。1999年，Krozel等人發(fā)現(xiàn)航站樓附近的惡劣天氣是造成航空器延誤的主要原因，并對(duì)風(fēng)暴影響下的航路規(guī)劃問題展開研究[5]。孟令航等人在2012年將不同天氣場(chǎng)景劃分為16種狀態(tài)，研究了對(duì)流云團(tuán)狀態(tài)不確定下的改航規(guī)劃問題[6]。王瑛等人在2019年采用柵格法對(duì)危險(xiǎn)天氣環(huán)境進(jìn)行構(gòu)建，將受天氣因素影響的空域刻畫為由一系列網(wǎng)格構(gòu)成的復(fù)雜系統(tǒng)[7]。

對(duì)于危險(xiǎn)天氣的改航路徑規(guī)劃研究目前已經(jīng)比較成熟，但還存在一些問題亟待解決，主要表現(xiàn)為現(xiàn)有改航路徑規(guī)劃方法主要是針對(duì)常見情形建立一般模型，未能針對(duì)不同天氣類型和相應(yīng)分布形狀設(shè)計(jì)針對(duì)性模型，對(duì)復(fù)雜不確定因素影響下的改航路徑規(guī)劃研究較少。

1.2 非戰(zhàn)爭(zhēng)軍事行動(dòng)

隨著軍事科技的不斷發(fā)展和國(guó)際局勢(shì)的政治需求，非戰(zhàn)爭(zhēng)軍事行動(dòng)對(duì)空域資源的需求逐步提高。特別是近年來，自然災(zāi)害頻發(fā)，應(yīng)急救援給空域使用帶來大量的不確定性；隨著軍機(jī)的升級(jí)換代和數(shù)量激增，新型裝備的出現(xiàn)和愈發(fā)頻繁的軍事訓(xùn)練和演習(xí)造成了軍民航飛行沖突增多；同時(shí)軍事訓(xùn)練的空域范圍逐漸擴(kuò)展，訓(xùn)練時(shí)間大幅增加，使得民航可用資源變少，造成空中交通擁擠，最終導(dǎo)致空域資源分配不均等問題越來越突出。

在非戰(zhàn)爭(zhēng)軍事行動(dòng)過程中，對(duì)空域的優(yōu)先使用按任務(wù)進(jìn)行調(diào)配，即遵循“軍事優(yōu)先”的原則[8]，為保證任務(wù)的順利進(jìn)行，在非戰(zhàn)爭(zhēng)軍事行動(dòng)過程中，會(huì)適當(dāng)調(diào)整民航的起飛降落時(shí)間來保證軍事任務(wù)優(yōu)先執(zhí)行。如何實(shí)施改航路徑規(guī)劃，盡可能保證飛行安全和效率，實(shí)現(xiàn)雙贏成為當(dāng)前的研究熱點(diǎn)。

歐洲航行安全組織和歐洲民航委員會(huì)(european civil aviation commission，ECAC)的軍民雙方代表在1994年共同提出“靈活使用空域(flexible use of airspace，F(xiàn)UA)”概念，目的是使空域不再分為軍用或者民用，使空域資源高效利用[9-10]。和治偉在2012年將常規(guī)非戰(zhàn)爭(zhēng)軍事行動(dòng)對(duì)空域影響的形式概括為抗震救災(zāi)、打擊恐怖主義和演習(xí)等幾類，研究了在此影響因素下的空域管制問題[11]。郭方月在2018年研究了軍事演習(xí)背景下的空域飛行受限區(qū)劃分問題，提出針對(duì)軍事演習(xí)的改航路徑規(guī)劃策略[12]。

非戰(zhàn)爭(zhēng)軍事行動(dòng)對(duì)于飛行安全的影響相比天氣因素具有預(yù)測(cè)性更強(qiáng)的特點(diǎn)。因?yàn)榉菓?zhàn)爭(zhēng)軍事行動(dòng)的時(shí)間和空域位置等信息是明確的，因此可以定量對(duì)軍民航飛行活動(dòng)進(jìn)行預(yù)先精準(zhǔn)規(guī)劃。

1.3 航天發(fā)射活動(dòng)

航天發(fā)射活動(dòng)與非戰(zhàn)爭(zhēng)軍事行動(dòng)對(duì)飛行安全的影響具有相似性，主要表現(xiàn)為：出現(xiàn)和消失的突發(fā)性、狀態(tài)變化具有較大的不確定性。相比極端天氣因素，該類活動(dòng)的發(fā)射位置、占用空域和時(shí)間跨度等信息都是已知的，但因其自身運(yùn)行狀態(tài)具有一定的不確定性，其脫落物及殘骸的運(yùn)動(dòng)狀態(tài)也存在一定的隨機(jī)性，因此導(dǎo)致空域占用情況較為復(fù)雜。目前，針對(duì)航天發(fā)射活動(dòng)影響下的改航路徑規(guī)劃研究較少，但是其本質(zhì)屬于動(dòng)態(tài)改航路徑規(guī)劃問題。

當(dāng)前，改航路徑規(guī)劃研究主要是針對(duì)危險(xiǎn)天氣的影響而展開，但對(duì)于非戰(zhàn)爭(zhēng)軍事行動(dòng)和航天發(fā)射等活動(dòng)影響下的改航路徑規(guī)劃研究相對(duì)較少，特別是隨著軍民融合戰(zhàn)略的持續(xù)推進(jìn)，非傳統(tǒng)領(lǐng)域內(nèi)的復(fù)雜不確定因素和風(fēng)險(xiǎn)不斷加大，許多帶有明顯特征的非戰(zhàn)爭(zhēng)軍事行動(dòng)和航空航天活動(dòng)給軍民航飛行安全帶來新的挑戰(zhàn)。因此，如何從全局角度實(shí)現(xiàn)改航路徑的一體規(guī)劃，最大程度滿足各類航空器的飛行需求，兼顧航空器飛行安全和運(yùn)行成本將具有重大的現(xiàn)實(shí)意義。

2 飛行受限區(qū)劃設(shè)

飛行受限區(qū)指當(dāng)航路或空域受危險(xiǎn)天氣、導(dǎo)航設(shè)備故障、軍事活動(dòng)或流量控制等影響而無法正常使用時(shí)，為保障民航航班安全臨時(shí)劃定的空域[13]，根據(jù)飛行受限區(qū)所確定的區(qū)域是否隨時(shí)間變化或移動(dòng)，可將飛行受限區(qū)分為靜態(tài)飛行受限區(qū)(static flight forbidden area，SFFA)和動(dòng)態(tài)飛行受限區(qū) (dynamic flight forbidden area，DFFA)[5]。飛行受限區(qū)劃設(shè)是指綜合考慮相關(guān)空域內(nèi)危險(xiǎn)天氣、非戰(zhàn)爭(zhēng)軍事活動(dòng)、航天發(fā)射活動(dòng)等實(shí)際影響因素以及空中飛行流量、空域資源容量、突發(fā)特殊情況、承載飽和度等要素，對(duì)航班的流量加以一定限制[7]。飛行受限區(qū)的合理劃設(shè)是改航路徑規(guī)劃的關(guān)鍵和基礎(chǔ)。劃設(shè)方法包括直接劃設(shè)法、預(yù)測(cè)劃設(shè)法、軍事受限區(qū)劃設(shè)法，前兩種主要針對(duì)危險(xiǎn)天氣，后一種既可用于非戰(zhàn)爭(zhēng)軍事行動(dòng)，也可用于航天發(fā)射活動(dòng)。其中，直接劃設(shè)法屬于靜態(tài)飛行受限區(qū)劃設(shè)策略，通常運(yùn)用于靜態(tài)路徑規(guī)劃模型中，而預(yù)測(cè)劃設(shè)法和軍事受限區(qū)劃設(shè)法屬于動(dòng)態(tài)飛行受限區(qū)劃設(shè)方法范疇，一般運(yùn)用于動(dòng)態(tài)路徑規(guī)劃模型中。

2.1 直接劃設(shè)法

直接劃設(shè)法是指以多普勒回波效應(yīng)為基礎(chǔ)，通過實(shí)時(shí)探測(cè)和分析相關(guān)數(shù)據(jù)，進(jìn)行飛行受限區(qū)劃設(shè)的方法[14]。對(duì)于危險(xiǎn)天氣影響飛行受限區(qū)劃設(shè)的研究已取得一些成果，如美國(guó)聯(lián)邦航空管理局(federal aviation administration，F(xiàn)AA)空中交通管理單元(traffic management unit，TMU)系統(tǒng)以提供的氣象雷達(dá)回波圖和短期預(yù)報(bào)為基礎(chǔ)，對(duì)極端天氣影響范圍進(jìn)行分析和確定。McCrea等人提出根據(jù)美國(guó)國(guó)家環(huán)境預(yù)報(bào)中心(national centers for environmental prediction，NCEP)的預(yù)測(cè)模型得出相關(guān)數(shù)據(jù)，對(duì)影響飛行的各類危險(xiǎn)天氣離散化，建立概率網(wǎng)的概念[15]；王莉莉等則統(tǒng)一用橢圓來簡(jiǎn)化威脅區(qū)域邊界，建立了威脅概率模型[13]；還將現(xiàn)實(shí)空域場(chǎng)景抽象于柵格中，利用“柵格理論”進(jìn)行實(shí)時(shí)動(dòng)態(tài)環(huán)境建模，該方法主要適用于動(dòng)態(tài)路徑規(guī)劃[16]。

2.2 預(yù)測(cè)劃設(shè)法

預(yù)測(cè)劃設(shè)法主要是指根據(jù)天氣預(yù)報(bào)、起降時(shí)刻、空域流量等信息，對(duì)未來某飛行受限區(qū)域進(jìn)行預(yù)測(cè)劃設(shè)的方法[17]。該方法適用于不能直接獲取實(shí)時(shí)信息或要對(duì)未來進(jìn)行規(guī)劃等情況，具體可分為平移劃設(shè)法、外推劃設(shè)法、近似橢圓劃設(shè)法、Graham劃設(shè)法和馬爾科夫預(yù)測(cè)等。

2.2.1 平移劃設(shè)法

平移劃設(shè)法由美國(guó)學(xué)者Bokadia和Valasek于2001年提出[14]，是最早的動(dòng)態(tài)飛行受限區(qū)劃設(shè)法，考慮危險(xiǎn)天氣動(dòng)態(tài)移動(dòng)的情況下對(duì)受影響空域進(jìn)行劃設(shè)。

通常認(rèn)為雷達(dá)回波強(qiáng)度不小于41 dBZ的區(qū)域?yàn)槭苡绊懣沼颉＜僭O(shè)經(jīng)歷時(shí)間ΔT，由雷暴移動(dòng)速率v及方向計(jì)算t+ΔT時(shí)刻的區(qū)域范圍，其基本原理如圖1所示。該方法的意義在于將氣象回波雷達(dá)運(yùn)用于空域劃設(shè)，著重考慮雷暴天氣移動(dòng)方向，但未考慮速度的瞬時(shí)性和雷暴區(qū)域形狀的不確定性，不適用于長(zhǎng)時(shí)間或劇烈變化危險(xiǎn)天氣情況。

圖1 平移劃設(shè)法示意圖

2.2.2 外推劃設(shè)法

外推劃設(shè)法以美國(guó)對(duì)流天氣預(yù)報(bào)提供數(shù)據(jù)為基礎(chǔ)，將極端環(huán)境或危險(xiǎn)天氣影響區(qū)域邊界外推，得到未來某時(shí)刻的受影響區(qū)域邊界[18]。Prete等人將天氣系統(tǒng)表示為若干反射率測(cè)量或預(yù)測(cè)的網(wǎng)格，通過插值產(chǎn)生天氣的連續(xù)表示，建立隨時(shí)間變化的天氣系統(tǒng)[19]；Sauer以雷達(dá)圖像數(shù)據(jù)為基礎(chǔ)，提取危險(xiǎn)天氣相關(guān)信息，根據(jù)傳統(tǒng)凸包生成原理劃設(shè)飛行受限區(qū)[20]。謝春生等人假設(shè)危險(xiǎn)天氣以恒定速度移動(dòng)，從移動(dòng)方向、邊界形狀和不確定因素三方面進(jìn)行劃設(shè)[21]；孟令航等人根據(jù)云團(tuán)位置和移動(dòng)速度測(cè)量不確定性和客觀存在誤差，建立了雷暴云團(tuán)狀態(tài)轉(zhuǎn)移矩陣[6]。

外推劃設(shè)法充分利用了天氣預(yù)報(bào)結(jié)果，能夠及時(shí)準(zhǔn)確地預(yù)測(cè)短期影響飛行安全的危險(xiǎn)天氣區(qū)域邊界。但該方法受限于國(guó)家天氣預(yù)報(bào)系統(tǒng)，且外推距離具有較大的主觀性和不確定性，劃設(shè)精度較低。

2.2.3 近似橢圓劃設(shè)法

近似橢圓劃設(shè)法由宋柯和胡明華于2002年提出[22]，該方法將云團(tuán)形狀抽象為3個(gè)相互交疊的橢圓，通過對(duì)橢圓集合形態(tài)變化的研究來進(jìn)行危險(xiǎn)天氣影響區(qū)域劃設(shè)。之后，王莉莉等人提出了改進(jìn)的幾何圓切法，用其規(guī)劃出臨時(shí)航線，繞過危險(xiǎn)區(qū)[23]；王興隆等人利用最小面積橢圓方法進(jìn)行劃設(shè)，并設(shè)置了精確度、偏差度等4個(gè)評(píng)估指標(biāo)[24]；周娟等人考慮高度層的變化，提出基于橢圓的飛行受限區(qū)劃設(shè)方法[25]，更具有現(xiàn)實(shí)意義和實(shí)用性。

近似橢圓劃設(shè)法的優(yōu)點(diǎn)在于：應(yīng)用橢圓描述危險(xiǎn)區(qū)域邊界簡(jiǎn)單明了，可減少參數(shù)數(shù)量。其不足之處在于：未充分考慮受限區(qū)域的形狀變化，主觀性較強(qiáng)，天氣劃設(shè)類型較單一。

2.2.4 Graham算法劃設(shè)法

Graham算法最初用于求解平面點(diǎn)集的凸殼。該方法基于邊界點(diǎn)位置信息，通過循環(huán)和迭代淘汰非凸多邊形邊界點(diǎn)，同時(shí)更新區(qū)域邊界，最終得到凸多邊形靜態(tài)飛行受限區(qū)[26]。2010年，謝春生等以Graham多邊形求解算法為基礎(chǔ)，給出了初始飛行受限區(qū)劃設(shè)方法，并考慮邊界變化和不確定因素的影響，提出動(dòng)態(tài)飛行受限區(qū)的劃設(shè)方法[27]，其缺點(diǎn)是僅描述了某時(shí)刻的靜態(tài)受限區(qū)。

2.2.5 馬爾科夫預(yù)測(cè)

2001年，Nilim A等在馬爾科夫預(yù)測(cè)模型基礎(chǔ)上，將受危險(xiǎn)天氣影響區(qū)域像素化、離散化，以影響區(qū)域面積為依據(jù)進(jìn)行預(yù)測(cè)分析[28]。2007年，戴玲等人用馬爾科夫鏈對(duì)極端環(huán)境和危險(xiǎn)天氣建模，提出多航空器(多機(jī))改航路徑規(guī)劃模型[29]。馬爾科夫預(yù)測(cè)法僅僅適用于雷暴等危險(xiǎn)天氣，通用性較差?？梢钥闯觯壳把芯恐饕性跇O端環(huán)境或危險(xiǎn)天氣影響下的飛行受限區(qū)劃設(shè)，對(duì)軍事演習(xí)、訓(xùn)練等隨機(jī)因素影響下的飛行受限區(qū)劃設(shè)還沒有形成系統(tǒng)的方法。

2.3 軍事限飛區(qū)劃設(shè)法

近年來，軍事飛行訓(xùn)練呈現(xiàn)出高強(qiáng)度、高頻率、近實(shí)戰(zhàn)的特點(diǎn)，空域使用需求增強(qiáng)。傳統(tǒng)的軍事限飛區(qū)劃設(shè)法由于其改航策略使用率較低，已不再適應(yīng)新常態(tài)的發(fā)展，如何科學(xué)合理劃設(shè)軍事限飛區(qū)成為研究的熱點(diǎn)。軍事限飛區(qū)也稱“三區(qū)”空域(three areas airspace，TAA)，是指為了開展軍事訓(xùn)練、保證飛行安全而設(shè)置的危險(xiǎn)區(qū)、限制區(qū)和禁飛區(qū)，“三區(qū)”空域劃設(shè)示意圖如圖2所示。

圖2 “三區(qū)”空域劃設(shè)示意圖

Pi(i=1,2,…,n)為空管相關(guān)部門報(bào)告的邊界點(diǎn)，利用Graham迭代算法對(duì)其進(jìn)行掃描，求出凸多邊形的“三區(qū)”空域ZTAA，如圖中實(shí)線邊界區(qū)域所示。

郭方月等人研究了軍事演習(xí)下的航班動(dòng)態(tài)改航路徑，利用平移劃設(shè)法劃設(shè)“三區(qū)”空域[12]；陳金良等人則研究了非戰(zhàn)爭(zhēng)軍事行動(dòng)下的飛行受限區(qū)的劃設(shè)，利用Graham算法劃設(shè)“三區(qū)”空域[8]。

總的來說，針對(duì)危險(xiǎn)天氣等影響下的飛行受限區(qū)的劃設(shè)方法較多，研究已較為成熟，且逐漸由靜態(tài)飛行受限區(qū)向動(dòng)態(tài)飛行受限區(qū)發(fā)展，而對(duì)于軍事活動(dòng)等因素影響下的飛行受限區(qū)劃設(shè)則研究甚少。

3 改航路徑規(guī)劃模型

飛行受限區(qū)的劃設(shè)是改航路徑規(guī)劃模型建立的基礎(chǔ)，改航活動(dòng)通常在劃設(shè)空域范圍內(nèi)開展，而改航路徑規(guī)劃模型的建立是整個(gè)改航過程的核心。根據(jù)飛行受限區(qū)狀態(tài)和改航實(shí)施時(shí)機(jī)，改航路徑規(guī)劃模型通?？煞譃殪o態(tài)路徑規(guī)劃(飛行前改航)模型與動(dòng)態(tài)路徑規(guī)劃(實(shí)時(shí)改航)模型兩類。

3.1 靜態(tài)路徑規(guī)劃

靜態(tài)路徑規(guī)劃即飛行前路徑規(guī)劃，是指在航班起飛之前對(duì)劃靜態(tài)飛行受限區(qū)進(jìn)行預(yù)測(cè)劃設(shè)，并在環(huán)境信息和相關(guān)要素完全確定并事先已知的前提下進(jìn)行的路徑規(guī)劃[30]，通常劃設(shè)完成后航路相關(guān)信息不再改變。該方法主要從空間描述的角度切入，典型模型有可視圖模型和網(wǎng)格模型等。

3.1.1 可視圖模型

作為一種路徑規(guī)劃方法，可視圖法最早由Lozano等針對(duì)機(jī)器人路徑規(guī)劃問題提出[31]?？梢晥D法將飛機(jī)視為一點(diǎn)并將飛行受限區(qū)視為平面內(nèi)多邊形，然后連接起點(diǎn)、目標(biāo)點(diǎn)以及多邊形的各個(gè)頂點(diǎn)，要求所有連線與任何飛行受限區(qū)都不相交?？梢晥D法對(duì)改航路徑建模后，常用幾何方法規(guī)劃改航飛行路徑。Sridhar等對(duì)多邊形改航路徑規(guī)劃方法展開了研究[32]；王飛等又在多邊形飛行受限區(qū)的基礎(chǔ)上結(jié)合了Maklink圖和遺傳算法調(diào)整已有路徑規(guī)劃[33]，Maklink圖是基于蟻群算法進(jìn)行路徑規(guī)劃時(shí)用到的一種二維空間模型，其本質(zhì)是提供路徑規(guī)劃關(guān)鍵點(diǎn)，幫助優(yōu)化靜態(tài)改航路徑。

可視圖法便于實(shí)操、對(duì)簡(jiǎn)單問題處理快速，但在考慮飛行受限區(qū)動(dòng)態(tài)變化時(shí)，更新算法復(fù)雜。由于路徑通?？拷w行受限區(qū)頂點(diǎn)和邊緣，該模型缺乏靈活性。

3.1.2 網(wǎng)格模型

改航路徑規(guī)劃的網(wǎng)格模型是將飛行空間劃分為為互不重疊的網(wǎng)格單元，根據(jù)飛行受限區(qū)是否占據(jù)網(wǎng)格對(duì)網(wǎng)格進(jìn)行賦值，然后運(yùn)用搜索算法在起飛機(jī)場(chǎng)和目標(biāo)機(jī)場(chǎng)間搜索規(guī)避受限區(qū)的最短飛行路徑，其基本形式如圖3所示。其中，ZTAA表示“三區(qū)空域”，ZEA表示極端環(huán)境空域。

圖3 網(wǎng)格模型示意圖

該方法由Dixon等在1993年提出[4]，該模型一經(jīng)提出，便得到了廣泛的應(yīng)用。例如，Krozel等在網(wǎng)格法的基礎(chǔ)上，對(duì)相鄰網(wǎng)格的連接度進(jìn)行拓展，提高了航線規(guī)劃的靈活性和搜索范圍[17]；高政等在對(duì)天氣無規(guī)律變化引起的改航研究過程中，也采用了網(wǎng)格化方法，規(guī)劃臨時(shí)改航航線，能快速有效利用空域資源[34]。

網(wǎng)格模型可以方便的量化飛行受限區(qū)，但當(dāng)網(wǎng)格數(shù)量較大時(shí)，算法空間冗余度較大。另外，網(wǎng)格的單元大小衡量標(biāo)準(zhǔn)不好把握，網(wǎng)格單元大小選取關(guān)系著規(guī)劃路徑的精確程度，單元越小，模型精確度越高，但同時(shí)占用計(jì)算資源也越多。

3.2 動(dòng)態(tài)路徑規(guī)劃

現(xiàn)實(shí)中，飛行受限區(qū)受到多種突發(fā)情況的影響，以軍事行動(dòng)、極端氣象條件為代表的危險(xiǎn)因素是造成飛機(jī)改航的重要因素。動(dòng)態(tài)路徑規(guī)劃即實(shí)時(shí)路徑規(guī)劃，是指依托航班起飛后實(shí)時(shí)探測(cè)到的動(dòng)態(tài)飛行受限區(qū)，通過實(shí)時(shí)獲取環(huán)境隨機(jī)信息和空域要素并加以分析決策的即時(shí)路徑規(guī)劃[30]。在動(dòng)態(tài)路徑規(guī)劃中，航路可根據(jù)環(huán)境的變化實(shí)時(shí)加以調(diào)整，相比傳統(tǒng)靜態(tài)路徑規(guī)劃，更具靈活性、穩(wěn)定性和實(shí)用性，應(yīng)對(duì)突發(fā)或未知空情的能力更強(qiáng)。因此，動(dòng)態(tài)的實(shí)時(shí)路徑規(guī)劃模型長(zhǎng)期以來受到關(guān)注，其研究方向大致可以分為網(wǎng)絡(luò)流模型和Markov鏈模型兩類。

3.2.1 網(wǎng)絡(luò)流模型

網(wǎng)絡(luò)流模型是將航路點(diǎn)劃分到多個(gè)階段中，網(wǎng)絡(luò)中相鄰兩個(gè)節(jié)點(diǎn)之間的連線為航路，進(jìn)行動(dòng)態(tài)規(guī)劃各段航路的模型。航路的容量值會(huì)因惡劣天氣、導(dǎo)航設(shè)備失效、軍事事件等特殊情況時(shí)發(fā)生變化，當(dāng)航段容量為0時(shí)，航段不產(chǎn)生任何影響，節(jié)點(diǎn)之間的狀態(tài)實(shí)時(shí)動(dòng)態(tài)變化。

網(wǎng)絡(luò)流模型在改航路徑規(guī)劃中得到了廣泛應(yīng)用。宋柯以總損失最小為目標(biāo)提出了基于網(wǎng)絡(luò)流模型的動(dòng)態(tài)路徑規(guī)劃方法[27]；Taylor在傳統(tǒng)單一路徑改航規(guī)劃的基礎(chǔ)上，利用網(wǎng)絡(luò)優(yōu)化方法建立了能夠規(guī)避危險(xiǎn)天氣的改航路徑模型，改進(jìn)了動(dòng)態(tài)生成改航航路的方法[35]。Evans建立了若干動(dòng)態(tài)改航路徑網(wǎng)絡(luò)模型并利用現(xiàn)有路徑信息對(duì)其可行性進(jìn)行分析論證，使規(guī)劃結(jié)果更為精確[36]。網(wǎng)絡(luò)流模型將改航路徑規(guī)劃轉(zhuǎn)化為一般的動(dòng)態(tài)規(guī)劃問題，結(jié)合各種啟發(fā)式算法，在解決動(dòng)態(tài)飛行受限區(qū)情況下的問題時(shí)顯示出良好的適用性。

3.2.2 Markov鏈模型

受軍事行動(dòng)、天氣等時(shí)變不確定性因素影響，在實(shí)時(shí)改航路徑規(guī)劃時(shí)，飛行受限區(qū)的位置在不斷變化，為在飛行受限區(qū)的位置動(dòng)態(tài)變化下進(jìn)行路徑規(guī)劃，現(xiàn)有研究普遍采用Markov鏈模型。其基本思想是對(duì)飛行受限區(qū)變化建立Markov鏈模型，進(jìn)而通過狀態(tài)轉(zhuǎn)移概率，實(shí)時(shí)規(guī)劃改航路徑。Christine利用Markov鏈對(duì)雷暴云團(tuán)的時(shí)變特性進(jìn)行描述，建立了動(dòng)態(tài)改航模型[37]；孟令航等考慮了流云團(tuán)動(dòng)態(tài)邊界的外推誤差，針對(duì)在不確定氣象條件，構(gòu)造一種基于Markov鏈的單機(jī)動(dòng)態(tài)改航模型，結(jié)合遺傳算法求解，取得良好的改航效果[6]。

該模型對(duì)天氣因素造成的受限區(qū)的動(dòng)態(tài)建模效果很好，但也存在著轉(zhuǎn)移概率設(shè)定對(duì)結(jié)果影響較大的問題，尤其是對(duì)軍事行動(dòng)這種人為因素，目前的Markov鏈預(yù)測(cè)的準(zhǔn)確性難以保證，還需要進(jìn)一步深入研究。

4 改航路徑規(guī)劃求解方法

改航路徑規(guī)劃效果不僅與模型結(jié)構(gòu)有關(guān)，同時(shí)還和算法密切相關(guān)。合理選擇算法對(duì)上述改航路徑規(guī)劃模型進(jìn)行求解是實(shí)現(xiàn)有效改航的關(guān)鍵，穩(wěn)準(zhǔn)快的求解算法能夠使求解的結(jié)果更加符合改航路徑的現(xiàn)實(shí)需要。改航路徑規(guī)劃的求解算法主要可以分為三類典型的方法：幾何法、人工勢(shì)場(chǎng)法和智能優(yōu)化算法。

4.1 幾何法

幾何法是使用純粹幾何學(xué)理論求解改航路徑規(guī)劃，在求解改航路徑規(guī)劃過程中，不會(huì)涉及到使用編程技術(shù)求解，是求解改航路徑規(guī)劃早期的算法，幾何法改航示意圖如圖4所示。

圖4 幾何法改航示意圖

基本程序如下：

Step1確定航班原航線與受限區(qū)的交匯點(diǎn)，及兩者的交點(diǎn)rz。

Step2確定改航起點(diǎn)r0和改航終點(diǎn)rs。

Step3以直線r0rs為界對(duì)軍事限飛區(qū)邊界點(diǎn)進(jìn)行分區(qū)，形成點(diǎn)集Q1、Q2。

(1)

(2)

王鑫等通過擴(kuò)展危險(xiǎn)區(qū)范圍，基于改進(jìn)幾何算法設(shè)計(jì)改航策略[38]；李雄等考慮了改航飛行中的空中交通管制程序和航空器性能，基于幾何算法提出改航策略[39]；郭方月等針對(duì)民航飛機(jī)航路飛行過程中遇到重大軍事活動(dòng)而需要實(shí)時(shí)改航的情況，劃設(shè)軍事演習(xí)下的飛行受限區(qū)，基于幾何算法提出改航策略[12]。

4.2 人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法是一種虛擬勢(shì)場(chǎng)法，基本思想是將飛機(jī)的運(yùn)動(dòng)視作人造勢(shì)場(chǎng)中運(yùn)動(dòng)，目標(biāo)點(diǎn)對(duì)飛機(jī)施加引力，中間點(diǎn)對(duì)飛機(jī)施加斥力，通過求合力控制飛機(jī)的運(yùn)動(dòng)。徐肖豪等建立了基于人工勢(shì)場(chǎng)算法的單機(jī)動(dòng)態(tài)任務(wù)改航路徑規(guī)劃模型[40]。王興隆等針對(duì)多機(jī)執(zhí)行任務(wù)，提出基于改進(jìn)人工勢(shì)場(chǎng)法的多機(jī)改航路徑規(guī)劃[41]；張兆寧等將目標(biāo)點(diǎn)與障礙物的距離以及航空器與受限區(qū)的運(yùn)動(dòng)速度考慮在內(nèi)，分別建立了基于改進(jìn)人工勢(shì)場(chǎng)法和動(dòng)態(tài)人工勢(shì)場(chǎng)法的規(guī)劃模型[42-43]；王飛等將人工勢(shì)場(chǎng)發(fā)和人工魚群算法進(jìn)行結(jié)合，提出了基于人工勢(shì)場(chǎng)-人工魚群算法的改航路徑規(guī)劃[44]。

4.3 智能優(yōu)化方法

改航路徑規(guī)劃算法逐漸從簡(jiǎn)單幾何法發(fā)展到基于程序和機(jī)器計(jì)算的智能優(yōu)化算法求解，計(jì)算結(jié)果精度和收斂速度均有大幅度提升，同時(shí)改航路徑規(guī)劃所得結(jié)果和方案更加合理。典型改航路徑智能優(yōu)化算法包括粒子群算法(particle swarm optimization，PSO)、蟻群算法(ant colony optimization,ACO)、遺傳算法(genetic algorithm，GA)、第三代非支配排序遺傳算法(non-dominated sorting genetic algorithm，NSGA-III)等。

4.3.1 粒子群求解改航路徑規(guī)劃

粒子群算法模擬自然界鳥群的生物特性，用于處理實(shí)際優(yōu)化問題。崔莉薇等針對(duì)多機(jī)飛行沖突解脫問題，利用遺傳算法改進(jìn)粒子群提出基于遺傳粒子群改航算法[45]；杜實(shí)等針對(duì)改航中存在的多目標(biāo)問題，提出基于改進(jìn)多目標(biāo)粒子群算法的改航算法[46]；陳天培等針對(duì)三維路徑規(guī)劃問題，提出基于模糊邏輯粒子群改航算法[47]。

4.3.2 蟻群求解改航路徑規(guī)劃

蟻群算法通過螞蟻個(gè)體識(shí)別那些經(jīng)過路徑周圍螞蟻留下信息素濃度的強(qiáng)弱程度尋優(yōu)，達(dá)到目標(biāo)位置。吳文政等綜合改航偏離度和改航新增改點(diǎn)數(shù)目等改航因素，利用面積度量改進(jìn)蟻群算法[48]；陳世歡等在原有蟻群算法基礎(chǔ)上，對(duì)螞蟻移動(dòng)時(shí)采用約束規(guī)則建立個(gè)體解，最后得到蟻群算法優(yōu)化[49]；向征等引入人工勢(shì)場(chǎng)法，改進(jìn)啟發(fā)信息因子，以提高模型路徑搜索的有效性[50]。

4.3.3 遺傳算法求解改航路徑規(guī)劃

遺傳算法是根據(jù)大自然中生物體進(jìn)化規(guī)律而設(shè)計(jì)提出的。蔣昕等以最短改航距離、最小轉(zhuǎn)彎角、最少轉(zhuǎn)彎點(diǎn)為優(yōu)化目標(biāo)建立改航路徑規(guī)劃模型，采用遺傳算法求解[18]；王帝等以改航繞飛路徑長(zhǎng)度最短為目標(biāo)，利用遺傳算法進(jìn)行改航路徑規(guī)劃[51]。

4.3.4 NSGA-III求解改航路徑規(guī)劃

第三代非支配排序遺傳算法NSGA-III是根據(jù)印度Deb提出的基于自然選擇學(xué)說和遺傳生物學(xué)原理的智能化遺傳算法，這兩者也是各類遺傳算法的思想基礎(chǔ)。NSGA-III算法保留和延續(xù)了NSGA算法的非支配排序思想和NSGA-II算法的精英策略，在這個(gè)基礎(chǔ)上提出了基于參考點(diǎn)距離的選擇策略，通過求解個(gè)體到參考點(diǎn)之間的距離來進(jìn)行選擇種群的更新。王瑛等針對(duì)現(xiàn)有改航路徑規(guī)劃模型未考慮多機(jī)改航時(shí)的關(guān)聯(lián)效應(yīng)等問題，提出了基于兩階段分析的改航路徑規(guī)劃模型，并利用NSGA算法完成模型求解[7]；鄭煜坤等建立基于節(jié)點(diǎn)移動(dòng)、融合、分解的航路點(diǎn)布局策略，并利用NSGA算法完成模型求解[52]。

綜上所述，幾何法求解改航路徑規(guī)劃屬于早期改航算法，其計(jì)算速度、求解精度、自適應(yīng)性均較差。人工勢(shì)場(chǎng)法具有快速實(shí)時(shí)的運(yùn)動(dòng)控制的優(yōu)點(diǎn)，規(guī)劃出的路徑比較平滑且安全。智能優(yōu)化算法的規(guī)劃效率更高，其中粒子群算法(PSO)和遺傳算法(GA)相比，其收斂速度快，但規(guī)劃路徑容易陷入局部最優(yōu)；蟻群算法(ACO)收斂速度較慢，但自適應(yīng)性好；遺傳算法求解精度相對(duì)較高；NSGA-III算法屬于當(dāng)前智能改航算法研究前沿和熱點(diǎn)，與傳統(tǒng)遺傳算法相比，規(guī)劃結(jié)果更精確，自適應(yīng)性好，且收斂速度較快。各改航路徑規(guī)劃優(yōu)化算法對(duì)比結(jié)果如表1所示。

表1 改航路徑規(guī)劃算法對(duì)比

5 研究展望

飛行訓(xùn)練和演習(xí)等軍事活動(dòng)日漸頻繁，軍民航飛行沖突將成為改航路徑規(guī)劃的重要影響因素。同時(shí)空中交通復(fù)雜度提升、軍民航影響耦合效應(yīng)增強(qiáng)、空中交通管理難度加大。未來可圍繞以下4個(gè)方面對(duì)改航路徑規(guī)劃開展研究：

5.1 建立集中統(tǒng)一的協(xié)調(diào)和管理中心

當(dāng)前民航和軍航空管體系處于相對(duì)獨(dú)立的狀態(tài)，缺乏相互之間的統(tǒng)籌和協(xié)調(diào)，這種模式無疑降低了體系運(yùn)行效率和空域資源利用率。

未來可考慮在軍民航之間建立集中統(tǒng)一的協(xié)調(diào)和管理中心，對(duì)空管機(jī)構(gòu)進(jìn)行結(jié)構(gòu)和系統(tǒng)調(diào)整，對(duì)軍民航具有一致性的部門實(shí)行垂直管理運(yùn)行一體化，統(tǒng)一管理、統(tǒng)一調(diào)度、協(xié)同運(yùn)行。目前，軍民航發(fā)生飛行沖突，需要分別向軍民雙方空管部門協(xié)調(diào)，這種解決機(jī)制效率低下，而通過集中統(tǒng)一的協(xié)調(diào)和管理中心進(jìn)行調(diào)度規(guī)劃則只需要由該中心集中統(tǒng)籌，打破傳統(tǒng)空管機(jī)制，克服運(yùn)行管理分散問題，優(yōu)化資源配置和整合，減小軍民航之間的“隔閡”和運(yùn)行機(jī)制差異，增強(qiáng)軍民航的兼容性和協(xié)調(diào)性。

5.2 非獨(dú)立多航班改航路徑規(guī)劃問題

目前，改航路徑規(guī)劃建模大多圍繞單航班進(jìn)行，主要做法是通過增設(shè)單航班改航點(diǎn)(除起始機(jī)場(chǎng)外的航路點(diǎn))，實(shí)現(xiàn)各航班的改航路徑規(guī)劃。其假設(shè)和前提是空域中的各航班之間是相互獨(dú)立、互不影響的。

在空域使用需求增多、空中交通復(fù)雜度提升的背景下，航班間相關(guān)性越來越強(qiáng)。若將終端區(qū)、扇區(qū)、航路點(diǎn)等視作節(jié)點(diǎn)，航路、航線等視作連邊，可以組成空域運(yùn)行的空中交通網(wǎng)絡(luò)，單個(gè)航班的改航很有可能通過空中交通網(wǎng)絡(luò)傳導(dǎo)至其他航班，影響其他航班的路徑計(jì)劃。因此，未來應(yīng)圍繞非獨(dú)立多航班情況下的改航路徑規(guī)劃問題，重點(diǎn)對(duì)耦合機(jī)理、延遲影響規(guī)模、規(guī)劃模型、優(yōu)化算法等開展研究。

5.3 不確定條件下的改航路徑動(dòng)態(tài)規(guī)劃問題

改航路徑規(guī)劃面臨較大的不確定性，現(xiàn)階段的研究主要圍繞“預(yù)先”或“事前”處理機(jī)制進(jìn)行，即在發(fā)生飛行沖突或進(jìn)入威脅區(qū)域之前，就提前做好航路的重新選擇。臨時(shí)空域管制或突發(fā)狀況下的改航路徑規(guī)劃研究較少。

當(dāng)前，空中實(shí)戰(zhàn)化、實(shí)彈化軍事演訓(xùn)活動(dòng)不斷增多，除例行性任務(wù)外，還存在臨時(shí)性、突發(fā)性等訓(xùn)練或空情處置任務(wù)，軍民航之間的影響耦合效應(yīng)增強(qiáng)。在緊急情況或突發(fā)空情等不確定條件下動(dòng)態(tài)規(guī)劃改航路徑，實(shí)施改航策略，也是未來改航路徑規(guī)劃的研究重點(diǎn)。

5.4 智能化改航路徑規(guī)劃方法研究

航班改航路徑規(guī)劃向協(xié)同化、精細(xì)化方向發(fā)展，對(duì)改航路徑規(guī)劃的實(shí)時(shí)性要求很高。改航路徑規(guī)劃的協(xié)同化和精細(xì)化必然導(dǎo)致模型參數(shù)增多、規(guī)模增大，呈現(xiàn)多目標(biāo)、多層次、非線性等特征，模型求解面臨“維數(shù)爆炸”困難，模型推廣和應(yīng)用面臨很大的困難。

近年來，深度強(qiáng)化學(xué)習(xí)、機(jī)器學(xué)習(xí)等最新智能優(yōu)化算法和思想層出不窮，為實(shí)時(shí)改航路徑規(guī)劃問題的“又快又好”求解提供了可能，未來應(yīng)加快最新優(yōu)化算法在改航路徑規(guī)劃問題中的應(yīng)用，為模型推廣應(yīng)用奠定基礎(chǔ)。

隨著改航路徑規(guī)劃問題研究的不斷深入，理論和方法體系將不斷建立和完善，作為空域管理的重要技術(shù)手段，智能化改航路徑規(guī)劃必將推動(dòng)軍民空域管理水平持續(xù)改進(jìn)提升。