王莉莉,王航臣
(中國民航大學(xué) 天津市空管運(yùn)行規(guī)劃與安全技術(shù)重點(diǎn)實(shí)驗(yàn)室,天津 300300)
近年來,我國民航運(yùn)輸快速發(fā)展,空中交通網(wǎng)絡(luò)擁塞現(xiàn)象越發(fā)嚴(yán)重,有限的空域資源與持續(xù)增長的出行需求之間矛盾日益突出,造成了航班延誤增多、飛行沖突增加,給航空公司和空管部門造成了巨大壓力。據(jù)統(tǒng)計,2017年航班正常率僅為71.67%,比起2016年下降5.09%[1]。究其原因,一方面空中交通流量管理(air traffic flow management, ATFM)過于依賴管制員工作經(jīng)驗(yàn),在交通流量過大時缺乏量化的最優(yōu)化模型協(xié)助決策;另一方面由于空域利用率低、面對突發(fā)事件處理能力不足,如蘭州管制區(qū)全年九成以上時間都有軍航活動,大部分航班延誤均由軍航活動造成[2]。不同性能航空器尾流強(qiáng)度和跑道占用時間不同,機(jī)型組合間隔不同都會影響航路網(wǎng)絡(luò)通行能力。如何更加合理調(diào)配不同性能航空器,合理使用空域資源是學(xué)界亟待解決的問題。
現(xiàn)有的短期ATFM研究,多采用數(shù)學(xué)規(guī)劃方法。該方法多以網(wǎng)絡(luò)流理論為基礎(chǔ)進(jìn)行建模,但這些方法存在的不足是:① 運(yùn)算效率存在不足,傳統(tǒng)網(wǎng)絡(luò)流算法只能精確求解小規(guī)模的航路網(wǎng)絡(luò)流量分配問題[3];② 對于大規(guī)模流量分配,只能采用啟發(fā)式算法[3-4]或?qū)栴}分解簡化[5-7],從而減少問題的運(yùn)算時間。航路網(wǎng)絡(luò)運(yùn)行優(yōu)化,無論是以地面等待時間最短[6,8-9]、空中等待時間最短[6,9]還是航行時間最短[10]、飛行油耗與排放最低[11],其本質(zhì)都是有限時間與空間資源指派與分配的組合優(yōu)化問題。
雖如今計算機(jī)運(yùn)算能力已大幅提升,但ATFM問題的組合規(guī)模使得在實(shí)際管制運(yùn)行中,很多算法無法投入應(yīng)用;其次大多數(shù)文獻(xiàn)只考慮了少量航空器、少量交叉點(diǎn)的靜態(tài)分配問題,沒有上升到網(wǎng)絡(luò)層面。如文獻(xiàn)[12-14]僅討論了單個交叉點(diǎn)不同構(gòu)型、交叉角度、不同高度層與不同機(jī)型組合下航路交叉點(diǎn)通行能力與擁擠識別問題,在分析過程中著重討論了航空器之間相互影響,但沒有考慮到通行能力與延誤優(yōu)化為整個網(wǎng)絡(luò)系統(tǒng)優(yōu)化,并非單個交叉點(diǎn)的最優(yōu);文獻(xiàn)[15-18]將研究點(diǎn)從單個交叉點(diǎn)上升到扇區(qū)和空域,著重分析了諸如惡劣天氣、飛行受限區(qū)等突發(fā)情況對不同結(jié)構(gòu)空域容量的影響,以及空中交通流的改航措施,但只是分析了靜態(tài)流量分配,沒有考慮航路擁擠程度隨交通流量變化及隨時間變化的情況。
綜上所述,以往研究對航路網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計、固定結(jié)構(gòu)下的靜態(tài)交通流狀態(tài)、固定結(jié)構(gòu)下空中交通流的靜態(tài)分配已取得一定成果,但很少有研究考慮航路的費(fèi)用隨諸如流量、時間和航空器尾流強(qiáng)度不同造成的通行能力變化。故筆者針對大型機(jī)、中型機(jī)與小型機(jī)這3種交通流的分配展開研究,先對航路網(wǎng)上流量分配問題進(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é)模型;最后針對模型特點(diǎn),設(shè)計了一種階段式分配流量的近似算法,并在運(yùn)算效率上和傳統(tǒng)網(wǎng)絡(luò)流算法進(jìn)行對比。
對于執(zhí)行客、貨運(yùn)輸任務(wù)的民用飛機(jī),其起飛、爬升、續(xù)航和下降性能對飛行安全和經(jīng)濟(jì)性兩方面都有較大影響。跑道上前后機(jī)型的不同組合會對空域各要素容量和安全間隔產(chǎn)生影響,如將機(jī)型劃分為大型機(jī)(H)、中型機(jī)(M)和小型機(jī)(L)后,這3種機(jī)型尾流強(qiáng)度不同,為防止飛機(jī)進(jìn)入前機(jī)尾流渦場所引起的俯仰、滾轉(zhuǎn)和失速等危險情況,國際民航組織(ICAO)根據(jù)尾流強(qiáng)度對尾流間隔進(jìn)行了劃分,如表1。綜上所述,這3種機(jī)型對空中交通系統(tǒng)影響差別較大,有必要針對以前研究中將空中交通流視為一種流的假設(shè)做出改進(jìn),使用MCF分別描述這3種機(jī)型。
表1 ICAO尾流間隔標(biāo)準(zhǔn)Table 1 ICAO standard for wake separation
由于飛機(jī)尾流限制,任一時間航路網(wǎng)絡(luò)上飛機(jī)數(shù)量都有限制,機(jī)型分布對網(wǎng)絡(luò)通行能力有較大影響;為描述這種影響,建模時應(yīng)考慮機(jī)型分布影響。機(jī)型分布建模中,由于到達(dá)某機(jī)場的飛機(jī)機(jī)型隨機(jī)分布,可采用離散概率分布建模。用大型機(jī)、中型機(jī)和小型機(jī)占所有航班計劃的百分比,表示該機(jī)型到達(dá)概率,設(shè)空中交通流中大型機(jī)、中型機(jī)和小型機(jī)所占百分比分別為p1、p2、p3,且p1+p2+p3=1。
在流量分配問題中,常將待分配的交通網(wǎng)絡(luò)抽象為一個賦權(quán)有向連通圖G=[V,E,Ck(x)],記為:V={Vi,Vst}。對于航路網(wǎng)絡(luò):Vi表示航路交叉點(diǎn)與導(dǎo)航臺點(diǎn)的集合,Vst表示起點(diǎn)機(jī)場和目的機(jī)場的集合,s表示起點(diǎn)機(jī)場,t表示訖點(diǎn)機(jī)場;設(shè)m為該段航路的起點(diǎn),n為該段航路的終點(diǎn),則E={emn}表示網(wǎng)絡(luò)G中航路的集合;Ck(x)表示第k(k=1,2,3)種航空器關(guān)于流量的阻抗函數(shù),用來描述該條航路的擁擠程度,隨著交通流量增加,該條航路擁擠程度隨之增加,阻抗隨之增加,原本在零流量時費(fèi)用最低(最短)的航路,隨著流量增加可能不再是最“短”的。對于多起訖點(diǎn)航路網(wǎng)絡(luò),可設(shè)置虛擬頂點(diǎn)Vs和Vt,并以正向邊(航路)將其與航路網(wǎng)絡(luò)連接,轉(zhuǎn)化為單起訖點(diǎn)流量分配問題。
(1)
阻抗函數(shù)(或稱為費(fèi)用函數(shù))是道路交通流分配的基礎(chǔ),它對于交通流的路徑選擇與各路段流量的分配有直接影響。道路交通流分配中,常用的阻抗函數(shù)是美國道路局(Bureau of Public Road, BPR)開發(fā)的函數(shù)[19],但BRP函數(shù)是針對美國道路交通流的實(shí)際運(yùn)行狀態(tài)設(shè)計的,直接應(yīng)用于民航會產(chǎn)生很大誤差,故筆者借鑒道路交通流分配中阻抗函數(shù)的設(shè)計思想,定義了符合民航實(shí)際運(yùn)行的航路費(fèi)用函數(shù),即在航路結(jié)構(gòu)、天氣條件和管制措施相同情況下,空中交通流量與航行時間的關(guān)系。阻抗函數(shù)的大小直接影響到空管部門對于航路選擇。筆者依據(jù)空中交通流量特點(diǎn)定義了與傳統(tǒng)道路交通阻抗函數(shù)不同的模型。
無論是大型機(jī)、中型機(jī)還是小型機(jī)飛行,眾多因素中與ATFM關(guān)系最密切的是時間(飛行任務(wù)能否按照航班時刻表順利進(jìn)行、能否降低航班延誤次數(shù))、距離(是否能提升航路網(wǎng)絡(luò)運(yùn)行效率)與相關(guān)費(fèi)用(能否降低費(fèi)用使得效益最大化)。不同飛行類型對影響因素的關(guān)注程度有所不同。
航路網(wǎng)絡(luò)是由航路組成,整個航路網(wǎng)絡(luò)所花費(fèi)時間是各個航段上所耗費(fèi)的時間之和。一般單條航路上實(shí)際航行時間可根據(jù)航路上已存在的飛機(jī)流量與速度進(jìn)行計算,航路上飛機(jī)流量與速度也是在設(shè)計阻抗模型時的重要參數(shù)。根據(jù)以上分析,構(gòu)建航路阻抗函數(shù)如式(2):
(2)
在向網(wǎng)絡(luò)中各條航路分配流量時,由于各條航路阻抗隨流量變化,故可考慮將流量分為N份,再使用現(xiàn)有流量下各條航路的阻抗,根據(jù)“最小費(fèi)用最大流”的原則,將N份流量逐次分配到網(wǎng)絡(luò)上,從而達(dá)到整個航路網(wǎng)絡(luò)航行時間最小目標(biāo)。
交通流分配中的SO模型從系統(tǒng)的最優(yōu)的角度分配交通流量,其目標(biāo)是路網(wǎng)中總阻抗(總行駛時間)最小,這符合空中交通統(tǒng)一由管制員調(diào)度的特點(diǎn)。但SO模型是針對道路交通流分配設(shè)計的,其結(jié)構(gòu)也較為簡單,而空中交通與道路交通存在許多不同,需根據(jù)民航空管的實(shí)際運(yùn)行特點(diǎn)對其進(jìn)一步優(yōu)化。筆者的主要改進(jìn)如下:
1)SO模型沒有考慮航路網(wǎng)絡(luò)因危險天氣造成的連通性問題;故引入1.1節(jié)中的決策變量以衡量網(wǎng)絡(luò)連通性問題。
2)SO模型只考慮了流量守恒約束與非負(fù)約束。在實(shí)際管制運(yùn)行中,還需考慮管制員負(fù)荷約束、航空器在航路上的安全間距產(chǎn)生的容量約束;故筆者引入管制員負(fù)荷約束和考慮安全間隔的航路容量約束。
3)SO模型假定航路網(wǎng)絡(luò)中僅有1種交通流,不同航空器的飛機(jī)性能存在差別;故筆者將SO模型中的單流問題轉(zhuǎn)化成多流問題進(jìn)行建模求解。
為簡化問題,筆者在建立模型之前做出以下假設(shè):① 在交通流分配期間,航空器高度層不發(fā)生變化;② 在交通流分配期間,大型機(jī)交通流、中型機(jī)交通流與小型機(jī)交通流各自內(nèi)部速度一致,即一種交通流與其他交通流速度不同,但自己內(nèi)部速度一致;③ 這3種交通流各自內(nèi)部的機(jī)型不存在差別,即將不同類型的中型機(jī)機(jī)視為一種機(jī)型組成的交通流,大型機(jī)和小型機(jī)同理。
2.2.1 目標(biāo)函數(shù)
為區(qū)分飛行任務(wù)的重要程度,筆者引入權(quán)重系數(shù)λkst,大型機(jī)活動重要系數(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模型的形式較為簡單,只包括交通流量守恒約束和流量非負(fù)約束,如式(4)~(6):
(4)
(5)
(6)
由1.2節(jié)中的討論,可進(jìn)一步確定航路容量約束,如式(7):
(7)
以Cij表示航路i-j的容量,以E(T)表示航路的平均服務(wù)時間[7],可用式(8)~(10)表示:
(8)
(9)
Tmn=Tm-Tn
(10)
式中:pmn表示m(m∈k)種交通流尾隨第n(n∈k)種交通流的概率;Tmn表示m(m∈k)種交通流尾隨第n(n∈k)種交通流時兩者的要求時間間隔矩陣。
為保證空中交通安全,航空器飛行應(yīng)保持一定的安全間隔。在一般情況下,大型機(jī)、中型機(jī)與小型機(jī)的速度存在差別,即前后機(jī)速度存在差別。當(dāng)前機(jī)速度小于后機(jī),即Vm Tmn=Tm-Tn=εmn/Vn (11) 當(dāng)前機(jī)速度大于后機(jī)時,即Vm>Vn時,有式(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) 求解單一品種流的經(jīng)典算法是Ford-Fulkson算法,但在求解多品種流問題時,使用該算法構(gòu)造增廣鏈會使問題的時間復(fù)雜度過高,難以滿足空中交通管制中的時效性要求。針對這一問題,文獻(xiàn)[21-22]結(jié)合最短路算法與Ford-Fulkson算法構(gòu)建了具有復(fù)合指標(biāo)的流量分配算法,筆者稱之為多品種流的Ford-Fulkson算法,并將該算法引入所提的求解算法中。 由于航路阻抗隨空中交通流量的大小動態(tài)變化,所以可將配流分為多次進(jìn)行,采用逐步加載流量的方式來描述這種變化。另外,這種變化限制了問題的求解,需設(shè)計一種網(wǎng)絡(luò)逐步加載流量的求解算法。故文中設(shè)計的模型求解算法如下: Step 2:更新航路阻抗。將分配得到的流量加載進(jìn)入航路網(wǎng)絡(luò),得到新的航路阻抗; 圖1為從中國民用航空局公布的AIP(航行資料匯編)中截取的華北管制區(qū)部分空域。黑色線段為簡化后的航路圖,其中節(jié)點(diǎn)1(北京ZBAA)、節(jié)點(diǎn)2(天津ZBTJ)、節(jié)點(diǎn)3(濟(jì)南ZSTN)為起飛機(jī)場節(jié)點(diǎn),節(jié)點(diǎn)8(呼和浩特ZBHH)、節(jié)點(diǎn)9(太原ZBYN)和節(jié)點(diǎn)10(石家莊ZBSJ)為目標(biāo)機(jī)場,節(jié)點(diǎn)4~7表示導(dǎo)航臺點(diǎn),航路點(diǎn)間的連線表示算例仿真的主要航路。設(shè)管制員的工作負(fù)荷及各個航路的容量是定值且已知。 圖1 仿真空域Fig. 1 Simulation airspace 對模型與算法在航路網(wǎng)絡(luò)小流量情況下進(jìn)行初步驗(yàn)證,利用MATLAB對算例進(jìn)行仿真。設(shè)表2表示源點(diǎn)待分配流量和終點(diǎn)能容納的流量,航路容量與管制員負(fù)荷均為20??傻眠\(yùn)算結(jié)果見圖2。運(yùn)算時間為7.11 min,能在較短時間內(nèi)給出優(yōu)化方案。 在完成小流量情況下初步驗(yàn)證后,不再限制容量,逐步增加空中交通流量,在大流量條件下測試模型的可行性與算法性能,設(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ò)通行能力??梢娫跐M足大型機(jī)任務(wù)需求情況下,能準(zhǔn)確完成中型機(jī)交通流和小型機(jī)交通流的分配,能夠?qū)崟r的完成這3種交通流的協(xié)調(diào),從而減少空域沖突與擁擠。 3.2.2 計算時間 通過MATLAB軟件使用改進(jìn)的算法求解模型。以3.1節(jié)中的空域結(jié)構(gòu)和流量為例,短期ATFM要求模型與算法的運(yùn)行時間不能過長,需在限定時間內(nèi)求得可以接受的解。故可將總求解時間長度限制為120 min,也即將問題的時間窗設(shè)定為0~120 min,通過改變空中交通流量來分析算法的性能,運(yùn)算結(jié)果見表4。 表4 算法求解性能分析Table 4 Algorithm performance analysis 求解結(jié)果表明:隨著飛機(jī)架次的增多,問題的規(guī)模也逐漸增大。在飛機(jī)架次達(dá)到256架次時,所提算法能完成求解,且時間上滿足要求,而經(jīng)典的Ford-Fulkson算法在限制時間(120 min)內(nèi)不能完成求解(以“—”表示)。綜上所述,筆者針對模型的近似算法在運(yùn)算效率上具有一定優(yōu)勢。 根據(jù)我國民航管制運(yùn)行特點(diǎn),結(jié)合不同機(jī)型飛機(jī)性能的特點(diǎn),筆者對航路交通領(lǐng)域的系統(tǒng)最優(yōu)模型進(jìn)行了改進(jìn)。改進(jìn)主要體現(xiàn)在:① 考慮了由于危險天氣與軍航活動帶來的網(wǎng)絡(luò)連通性問題;② 考慮了實(shí)時管制運(yùn)行時的航路網(wǎng)絡(luò)容量問題;③ 從尾流間隔角度,說明了將不同機(jī)型轉(zhuǎn)化為多品種流的必要性,并建立了多品種流的通行能力優(yōu)化模型。 在模型建立方面,通過引入0-1變量衡量了航路網(wǎng)連通程度及航空器改航問題;考慮到大型機(jī)、中型機(jī)與小型機(jī)交通流性能差異,將飛機(jī)性能問題轉(zhuǎn)變?yōu)橐粋€多品種流問題,并對各品種流量引入權(quán)重系數(shù),從而在優(yōu)化中體現(xiàn)優(yōu)先大型機(jī)活動、保障中型機(jī)正常運(yùn)行的宗旨。在模型求解方面,針對經(jīng)典算法不能滿足短期ATFM時間約束的問題,提出一種網(wǎng)絡(luò)逐步加載交通流量的近似算法。 算例結(jié)果表明:所改進(jìn)的模型與提出的算法能高效求解多品種流下大規(guī)??罩薪煌髁糠峙鋯栴},相比于傳統(tǒng)算法在大流量下更具效率優(yōu)勢。在大流量下,傳統(tǒng)求解算法不能滿足短期ATFM對時間的要求,僅依靠管制員個人經(jīng)驗(yàn)易造成疲勞也缺乏定量依據(jù);而所提算法在256和512架次這種大流量條件下仍能在設(shè)定時間內(nèi)完成求解,優(yōu)化效率與結(jié)果更符合航路網(wǎng)絡(luò)的運(yùn)行特點(diǎn)。2.3 模型求解
3 算例分析
3.1 算例構(gòu)造
3.2 仿真結(jié)果
4 結(jié) 論