王莉莉，王航臣

(中國(guó)民航大學(xué) 天津市空管運(yùn)行規(guī)劃與安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津 300300)

0 引 言

近年來(lái)，我國(guó)民航運(yùn)輸快速發(fā)展，空中交通網(wǎng)絡(luò)擁塞現(xiàn)象越發(fā)嚴(yán)重，有限的空域資源與持續(xù)增長(zhǎng)的出行需求之間矛盾日益突出，造成了航班延誤增多、飛行沖突增加，給航空公司和空管部門(mén)造成了巨大壓力。據(jù)統(tǒng)計(jì)，2017年航班正常率僅為71.67%，比起2016年下降5.09%[1]。究其原因，一方面空中交通流量管理(air traffic flow management, ATFM)過(guò)于依賴管制員工作經(jīng)驗(yàn)，在交通流量過(guò)大時(shí)缺乏量化的最優(yōu)化模型協(xié)助決策；另一方面由于空域利用率低、面對(duì)突發(fā)事件處理能力不足，如蘭州管制區(qū)全年九成以上時(shí)間都有軍航活動(dòng)，大部分航班延誤均由軍航活動(dòng)造成[2]。不同性能航空器尾流強(qiáng)度和跑道占用時(shí)間不同，機(jī)型組合間隔不同都會(huì)影響航路網(wǎng)絡(luò)通行能力。如何更加合理調(diào)配不同性能航空器，合理使用空域資源是學(xué)界亟待解決的問(wèn)題。

現(xiàn)有的短期ATFM研究，多采用數(shù)學(xué)規(guī)劃方法。該方法多以網(wǎng)絡(luò)流理論為基礎(chǔ)進(jìn)行建模，但這些方法存在的不足是：① 運(yùn)算效率存在不足，傳統(tǒng)網(wǎng)絡(luò)流算法只能精確求解小規(guī)模的航路網(wǎng)絡(luò)流量分配問(wèn)題[3]；② 對(duì)于大規(guī)模流量分配，只能采用啟發(fā)式算法[3-4]或?qū)?wèn)題分解簡(jiǎn)化[5-7]，從而減少問(wèn)題的運(yùn)算時(shí)間。航路網(wǎng)絡(luò)運(yùn)行優(yōu)化，無(wú)論是以地面等待時(shí)間最短[6,8-9]、空中等待時(shí)間最短[6,9]還是航行時(shí)間最短[10]、飛行油耗與排放最低[11]，其本質(zhì)都是有限時(shí)間與空間資源指派與分配的組合優(yōu)化問(wèn)題。

雖如今計(jì)算機(jī)運(yùn)算能力已大幅提升，但ATFM問(wèn)題的組合規(guī)模使得在實(shí)際管制運(yùn)行中，很多算法無(wú)法投入應(yīng)用；其次大多數(shù)文獻(xiàn)只考慮了少量航空器、少量交叉點(diǎn)的靜態(tài)分配問(wèn)題，沒(méi)有上升到網(wǎng)絡(luò)層面。如文獻(xiàn)[12-14]僅討論了單個(gè)交叉點(diǎn)不同構(gòu)型、交叉角度、不同高度層與不同機(jī)型組合下航路交叉點(diǎn)通行能力與擁擠識(shí)別問(wèn)題，在分析過(guò)程中著重討論了航空器之間相互影響，但沒(méi)有考慮到通行能力與延誤優(yōu)化為整個(gè)網(wǎng)絡(luò)系統(tǒng)優(yōu)化，并非單個(gè)交叉點(diǎn)的最優(yōu)；文獻(xiàn)[15-18]將研究點(diǎn)從單個(gè)交叉點(diǎn)上升到扇區(qū)和空域，著重分析了諸如惡劣天氣、飛行受限區(qū)等突發(fā)情況對(duì)不同結(jié)構(gòu)空域容量的影響，以及空中交通流的改航措施，但只是分析了靜態(tài)流量分配，沒(méi)有考慮航路擁擠程度隨交通流量變化及隨時(shí)間變化的情況。

綜上所述，以往研究對(duì)航路網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)、固定結(jié)構(gòu)下的靜態(tài)交通流狀態(tài)、固定結(jié)構(gòu)下空中交通流的靜態(tài)分配已取得一定成果，但很少有研究考慮航路的費(fèi)用隨諸如流量、時(shí)間和航空器尾流強(qiáng)度不同造成的通行能力變化。故筆者針對(duì)大型機(jī)、中型機(jī)與小型機(jī)這3種交通流的分配展開(kāi)研究，先對(duì)航路網(wǎng)上流量分配問(wèn)題進(jìn)行分析，定義了航路費(fèi)用函數(shù)；再基于多品種流理論(multi commodity flows, MCF)和改進(jìn)的系統(tǒng)最優(yōu)分配模型(system optimum assignment, SO)，根據(jù)三流的特點(diǎn)，建立了可分配的3種交通流數(shù)學(xué)模型；最后針對(duì)模型特點(diǎn)，設(shè)計(jì)了一種階段式分配流量的近似算法，并在運(yùn)算效率上和傳統(tǒng)網(wǎng)絡(luò)流算法進(jìn)行對(duì)比。

1 問(wèn)題描述

1.1 飛機(jī)性能對(duì)網(wǎng)絡(luò)通行能力的影響

對(duì)于執(zhí)行客、貨運(yùn)輸任務(wù)的民用飛機(jī)，其起飛、爬升、續(xù)航和下降性能對(duì)飛行安全和經(jīng)濟(jì)性兩方面都有較大影響。跑道上前后機(jī)型的不同組合會(huì)對(duì)空域各要素容量和安全間隔產(chǎn)生影響，如將機(jī)型劃分為大型機(jī)(H)、中型機(jī)(M)和小型機(jī)(L)后，這3種機(jī)型尾流強(qiáng)度不同，為防止飛機(jī)進(jìn)入前機(jī)尾流渦場(chǎng)所引起的俯仰、滾轉(zhuǎn)和失速等危險(xiǎn)情況，國(guó)際民航組織(ICAO)根據(jù)尾流強(qiáng)度對(duì)尾流間隔進(jìn)行了劃分，如表1。綜上所述，這3種機(jī)型對(duì)空中交通系統(tǒng)影響差別較大，有必要針對(duì)以前研究中將空中交通流視為一種流的假設(shè)做出改進(jìn)，使用MCF分別描述這3種機(jī)型。

表1 ICAO尾流間隔標(biāo)準(zhǔn)Table 1 ICAO standard for wake separation

由于飛機(jī)尾流限制，任一時(shí)間航路網(wǎng)絡(luò)上飛機(jī)數(shù)量都有限制，機(jī)型分布對(duì)網(wǎng)絡(luò)通行能力有較大影響；為描述這種影響，建模時(shí)應(yīng)考慮機(jī)型分布影響。機(jī)型分布建模中，由于到達(dá)某機(jī)場(chǎng)的飛機(jī)機(jī)型隨機(jī)分布，可采用離散概率分布建模。用大型機(jī)、中型機(jī)和小型機(jī)占所有航班計(jì)劃的百分比，表示該機(jī)型到達(dá)概率，設(shè)空中交通流中大型機(jī)、中型機(jī)和小型機(jī)所占百分比分別為p1、p2、p3，且p1+p2+p3=1。

1.2 航路網(wǎng)的數(shù)學(xué)表示與費(fèi)用函數(shù)

在流量分配問(wèn)題中，常將待分配的交通網(wǎng)絡(luò)抽象為一個(gè)賦權(quán)有向連通圖G=[V,E,Ck(x)]，記為：V={Vi,Vst}。對(duì)于航路網(wǎng)絡(luò)：Vi表示航路交叉點(diǎn)與導(dǎo)航臺(tái)點(diǎn)的集合，Vst表示起點(diǎn)機(jī)場(chǎng)和目的機(jī)場(chǎng)的集合，s表示起點(diǎn)機(jī)場(chǎng)，t表示訖點(diǎn)機(jī)場(chǎng)；設(shè)m為該段航路的起點(diǎn)，n為該段航路的終點(diǎn)，則E={emn}表示網(wǎng)絡(luò)G中航路的集合；Ck(x)表示第k(k=1,2,3)種航空器關(guān)于流量的阻抗函數(shù)，用來(lái)描述該條航路的擁擠程度，隨著交通流量增加，該條航路擁擠程度隨之增加，阻抗隨之增加，原本在零流量時(shí)費(fèi)用最低(最短)的航路，隨著流量增加可能不再是最“短”的。對(duì)于多起訖點(diǎn)航路網(wǎng)絡(luò)，可設(shè)置虛擬頂點(diǎn)Vs和Vt，并以正向邊(航路)將其與航路網(wǎng)絡(luò)連接，轉(zhuǎn)化為單起訖點(diǎn)流量分配問(wèn)題。

(1)

阻抗函數(shù)(或稱為費(fèi)用函數(shù))是道路交通流分配的基礎(chǔ)，它對(duì)于交通流的路徑選擇與各路段流量的分配有直接影響。道路交通流分配中，常用的阻抗函數(shù)是美國(guó)道路局(Bureau of Public Road, BPR)開(kāi)發(fā)的函數(shù)[19]，但BRP函數(shù)是針對(duì)美國(guó)道路交通流的實(shí)際運(yùn)行狀態(tài)設(shè)計(jì)的，直接應(yīng)用于民航會(huì)產(chǎn)生很大誤差，故筆者借鑒道路交通流分配中阻抗函數(shù)的設(shè)計(jì)思想，定義了符合民航實(shí)際運(yùn)行的航路費(fèi)用函數(shù)，即在航路結(jié)構(gòu)、天氣條件和管制措施相同情況下，空中交通流量與航行時(shí)間的關(guān)系。阻抗函數(shù)的大小直接影響到空管部門(mén)對(duì)于航路選擇。筆者依據(jù)空中交通流量特點(diǎn)定義了與傳統(tǒng)道路交通阻抗函數(shù)不同的模型。

無(wú)論是大型機(jī)、中型機(jī)還是小型機(jī)飛行，眾多因素中與ATFM關(guān)系最密切的是時(shí)間(飛行任務(wù)能否按照航班時(shí)刻表順利進(jìn)行、能否降低航班延誤次數(shù))、距離(是否能提升航路網(wǎng)絡(luò)運(yùn)行效率)與相關(guān)費(fèi)用(能否降低費(fèi)用使得效益最大化)。不同飛行類型對(duì)影響因素的關(guān)注程度有所不同。

航路網(wǎng)絡(luò)是由航路組成，整個(gè)航路網(wǎng)絡(luò)所花費(fèi)時(shí)間是各個(gè)航段上所耗費(fèi)的時(shí)間之和。一般單條航路上實(shí)際航行時(shí)間可根據(jù)航路上已存在的飛機(jī)流量與速度進(jìn)行計(jì)算，航路上飛機(jī)流量與速度也是在設(shè)計(jì)阻抗模型時(shí)的重要參數(shù)。根據(jù)以上分析，構(gòu)建航路阻抗函數(shù)如式(2)：

(2)

1.3 流量分配原則

在向網(wǎng)絡(luò)中各條航路分配流量時(shí)，由于各條航路阻抗隨流量變化，故可考慮將流量分為N份，再使用現(xiàn)有流量下各條航路的阻抗，根據(jù)“最小費(fèi)用最大流”的原則，將N份流量逐次分配到網(wǎng)絡(luò)上，從而達(dá)到整個(gè)航路網(wǎng)絡(luò)航行時(shí)間最小目標(biāo)。

交通流分配中的SO模型從系統(tǒng)的最優(yōu)的角度分配交通流量，其目標(biāo)是路網(wǎng)中總阻抗(總行駛時(shí)間)最小，這符合空中交通統(tǒng)一由管制員調(diào)度的特點(diǎn)。但SO模型是針對(duì)道路交通流分配設(shè)計(jì)的，其結(jié)構(gòu)也較為簡(jiǎn)單，而空中交通與道路交通存在許多不同，需根據(jù)民航空管的實(shí)際運(yùn)行特點(diǎn)對(duì)其進(jìn)一步優(yōu)化。筆者的主要改進(jìn)如下：

1)SO模型沒(méi)有考慮航路網(wǎng)絡(luò)因危險(xiǎn)天氣造成的連通性問(wèn)題；故引入1.1節(jié)中的決策變量以衡量網(wǎng)絡(luò)連通性問(wèn)題。

2)SO模型只考慮了流量守恒約束與非負(fù)約束。在實(shí)際管制運(yùn)行中，還需考慮管制員負(fù)荷約束、航空器在航路上的安全間距產(chǎn)生的容量約束；故筆者引入管制員負(fù)荷約束和考慮安全間隔的航路容量約束。

3)SO模型假定航路網(wǎng)絡(luò)中僅有1種交通流，不同航空器的飛機(jī)性能存在差別；故筆者將SO模型中的單流問(wèn)題轉(zhuǎn)化成多流問(wèn)題進(jìn)行建模求解。

2 模型建立

2.1 模型假設(shè)

為簡(jiǎn)化問(wèn)題，筆者在建立模型之前做出以下假設(shè)：① 在交通流分配期間，航空器高度層不發(fā)生變化；② 在交通流分配期間，大型機(jī)交通流、中型機(jī)交通流與小型機(jī)交通流各自內(nèi)部速度一致，即一種交通流與其他交通流速度不同，但自己內(nèi)部速度一致；③ 這3種交通流各自內(nèi)部的機(jī)型不存在差別，即將不同類型的中型機(jī)機(jī)視為一種機(jī)型組成的交通流，大型機(jī)和小型機(jī)同理。

2.2 通行能力優(yōu)化模型

2.2.1 目標(biāo)函數(shù)

為區(qū)分飛行任務(wù)的重要程度，筆者引入權(quán)重系數(shù)λkst，大型機(jī)活動(dòng)重要系數(shù)大于1，中型機(jī)和小型機(jī)重要系數(shù)小于1。

結(jié)合前文分析，短期ATFM目標(biāo)是使航路網(wǎng)絡(luò)上所有飛機(jī)的航行費(fèi)用最小，改進(jìn)SO模型目標(biāo)函數(shù)如式(3)：

(3)

2.2.2 約束條件

SO模型的形式較為簡(jiǎn)單，只包括交通流量守恒約束和流量非負(fù)約束，如式(4)～(6)：

(4)

(5)

(6)

由1.2節(jié)中的討論，可進(jìn)一步確定航路容量約束，如式(7)：

(7)

以Cij表示航路i-j的容量，以E(T)表示航路的平均服務(wù)時(shí)間[7]，可用式(8)～(10)表示：

(8)

(9)

Tmn=Tm-Tn

(10)

式中：pmn表示m(m∈k)種交通流尾隨第n(n∈k)種交通流的概率；Tmn表示m(m∈k)種交通流尾隨第n(n∈k)種交通流時(shí)兩者的要求時(shí)間間隔矩陣。

為保證空中交通安全，航空器飛行應(yīng)保持一定的安全間隔。在一般情況下，大型機(jī)、中型機(jī)與小型機(jī)的速度存在差別，即前后機(jī)速度存在差別。當(dāng)前機(jī)速度小于后機(jī)，即Vm

Tmn=Tm-Tn=εmn/Vn

(11)

當(dāng)前機(jī)速度大于后機(jī)時(shí)，即Vm>Vn時(shí)，有式(12)：

Tmn=Tm-Tn=εmn/Vn+η(1/Vn-1/Vm)

(12)

此外，與道路交通不同，隨著空中交通流量增加，影響配流的因素還有管制員工作負(fù)荷。設(shè)WLmax為管制員最大工作負(fù)荷，故可建立管制員工作負(fù)荷約束，如式(13)～(14)：

(13)

WLmax=ω1nco+ω2nh+Wxt

(14)

綜上所述，可將模型表述如式(15)：

(15)

2.3 模型求解

求解單一品種流的經(jīng)典算法是Ford-Fulkson算法，但在求解多品種流問(wèn)題時(shí)，使用該算法構(gòu)造增廣鏈會(huì)使問(wèn)題的時(shí)間復(fù)雜度過(guò)高，難以滿足空中交通管制中的時(shí)效性要求。針對(duì)這一問(wèn)題，文獻(xiàn)[21-22]結(jié)合最短路算法與Ford-Fulkson算法構(gòu)建了具有復(fù)合指標(biāo)的流量分配算法，筆者稱之為多品種流的Ford-Fulkson算法，并將該算法引入所提的求解算法中。

由于航路阻抗隨空中交通流量的大小動(dòng)態(tài)變化，所以可將配流分為多次進(jìn)行，采用逐步加載流量的方式來(lái)描述這種變化。另外，這種變化限制了問(wèn)題的求解，需設(shè)計(jì)一種網(wǎng)絡(luò)逐步加載流量的求解算法。故文中設(shè)計(jì)的模型求解算法如下：

Step 2：更新航路阻抗。將分配得到的流量加載進(jìn)入航路網(wǎng)絡(luò)，得到新的航路阻抗；

3 算例分析

3.1 算例構(gòu)造

圖1為從中國(guó)民用航空局公布的AIP(航行資料匯編)中截取的華北管制區(qū)部分空域。黑色線段為簡(jiǎn)化后的航路圖，其中節(jié)點(diǎn)1(北京ZBAA)、節(jié)點(diǎn)2(天津ZBTJ)、節(jié)點(diǎn)3(濟(jì)南ZSTN)為起飛機(jī)場(chǎng)節(jié)點(diǎn)，節(jié)點(diǎn)8(呼和浩特ZBHH)、節(jié)點(diǎn)9(太原ZBYN)和節(jié)點(diǎn)10(石家莊ZBSJ)為目標(biāo)機(jī)場(chǎng)，節(jié)點(diǎn)4～7表示導(dǎo)航臺(tái)點(diǎn)，航路點(diǎn)間的連線表示算例仿真的主要航路。設(shè)管制員的工作負(fù)荷及各個(gè)航路的容量是定值且已知。

圖1 仿真空域Fig. 1 Simulation airspace

3.2 仿真結(jié)果

對(duì)模型與算法在航路網(wǎng)絡(luò)小流量情況下進(jìn)行初步驗(yàn)證，利用MATLAB對(duì)算例進(jìn)行仿真。設(shè)表2表示源點(diǎn)待分配流量和終點(diǎn)能容納的流量，航路容量與管制員負(fù)荷均為20。可得運(yùn)算結(jié)果見(jiàn)圖2。運(yùn)算時(shí)間為7.11 min，能在較短時(shí)間內(nèi)給出優(yōu)化方案。

在完成小流量情況下初步驗(yàn)證后，不再限制容量，逐步增加空中交通流量，在大流量條件下測(cè)試模型的可行性與算法性能，設(shè)3種機(jī)型進(jìn)近著陸所占比例分別為40%、 35%、 25%。

表2 源點(diǎn)需分配的和節(jié)點(diǎn)能容納的交通流Table 2 Flows to be allocated and airport capacity 架次

圖2 分配結(jié)果Fig. 2 Assignment results

3.2.1 流量分配

設(shè)置不同流量條件，其仿真結(jié)果如表3。

表3 流量分配Table 3 Results of the assignment 架次

由運(yùn)算結(jié)果可知：模型與算法在各條航路在約束條件下，取得總費(fèi)用最小流量分配優(yōu)化方案，從而得到最優(yōu)航路網(wǎng)絡(luò)通行能力。可見(jiàn)在滿足大型機(jī)任務(wù)需求情況下，能準(zhǔn)確完成中型機(jī)交通流和小型機(jī)交通流的分配，能夠?qū)崟r(shí)的完成這3種交通流的協(xié)調(diào)，從而減少空域沖突與擁擠。

3.2.2 計(jì)算時(shí)間

通過(guò)MATLAB軟件使用改進(jìn)的算法求解模型。以3.1節(jié)中的空域結(jié)構(gòu)和流量為例，短期ATFM要求模型與算法的運(yùn)行時(shí)間不能過(guò)長(zhǎng)，需在限定時(shí)間內(nèi)求得可以接受的解。故可將總求解時(shí)間長(zhǎng)度限制為120 min，也即將問(wèn)題的時(shí)間窗設(shè)定為0～120 min，通過(guò)改變空中交通流量來(lái)分析算法的性能，運(yùn)算結(jié)果見(jiàn)表4。

表4 算法求解性能分析Table 4 Algorithm performance analysis

求解結(jié)果表明：隨著飛機(jī)架次的增多，問(wèn)題的規(guī)模也逐漸增大。在飛機(jī)架次達(dá)到256架次時(shí)，所提算法能完成求解，且時(shí)間上滿足要求，而經(jīng)典的Ford-Fulkson算法在限制時(shí)間(120 min)內(nèi)不能完成求解(以“—”表示)。綜上所述，筆者針對(duì)模型的近似算法在運(yùn)算效率上具有一定優(yōu)勢(shì)。

4 結(jié) 論

根據(jù)我國(guó)民航管制運(yùn)行特點(diǎn)，結(jié)合不同機(jī)型飛機(jī)性能的特點(diǎn)，筆者對(duì)航路交通領(lǐng)域的系統(tǒng)最優(yōu)模型進(jìn)行了改進(jìn)。改進(jìn)主要體現(xiàn)在：① 考慮了由于危險(xiǎn)天氣與軍航活動(dòng)帶來(lái)的網(wǎng)絡(luò)連通性問(wèn)題；② 考慮了實(shí)時(shí)管制運(yùn)行時(shí)的航路網(wǎng)絡(luò)容量問(wèn)題；③ 從尾流間隔角度，說(shuō)明了將不同機(jī)型轉(zhuǎn)化為多品種流的必要性，并建立了多品種流的通行能力優(yōu)化模型。

在模型建立方面，通過(guò)引入0-1變量衡量了航路網(wǎng)連通程度及航空器改航問(wèn)題；考慮到大型機(jī)、中型機(jī)與小型機(jī)交通流性能差異，將飛機(jī)性能問(wèn)題轉(zhuǎn)變?yōu)橐粋€(gè)多品種流問(wèn)題，并對(duì)各品種流量引入權(quán)重系數(shù)，從而在優(yōu)化中體現(xiàn)優(yōu)先大型機(jī)活動(dòng)、保障中型機(jī)正常運(yùn)行的宗旨。在模型求解方面，針對(duì)經(jīng)典算法不能滿足短期ATFM時(shí)間約束的問(wèn)題，提出一種網(wǎng)絡(luò)逐步加載交通流量的近似算法。

算例結(jié)果表明：所改進(jìn)的模型與提出的算法能高效求解多品種流下大規(guī)模空中交通流量分配問(wèn)題，相比于傳統(tǒng)算法在大流量下更具效率優(yōu)勢(shì)。在大流量下，傳統(tǒng)求解算法不能滿足短期ATFM對(duì)時(shí)間的要求，僅依靠管制員個(gè)人經(jīng)驗(yàn)易造成疲勞也缺乏定量依據(jù)；而所提算法在256和512架次這種大流量條件下仍能在設(shè)定時(shí)間內(nèi)完成求解，優(yōu)化效率與結(jié)果更符合航路網(wǎng)絡(luò)的運(yùn)行特點(diǎn)。