姚頔, 王瑛

(1.空軍工程大學(xué) 裝備管理與安全工程學(xué)院, 陜西 西安　710051; 2.國家飛行流量監(jiān)控中心, 北京　100094)

?

基于動(dòng)態(tài)扇區(qū)的空域與飛行流量兩階段協(xié)同規(guī)劃模型及算法

姚頔1,2, 王瑛1

(1.空軍工程大學(xué) 裝備管理與安全工程學(xué)院, 陜西 西安710051; 2.國家飛行流量監(jiān)控中心, 北京100094)

摘要：針對管制扇區(qū)動(dòng)態(tài)規(guī)劃與飛行流量時(shí)空調(diào)配的耦合問題，考慮運(yùn)行容量、效率等目標(biāo)，建立了兩階段協(xié)同規(guī)劃模型及求解框架。第一階段根據(jù)自然航路點(diǎn)和流量分布，結(jié)合Voronoi圖與圖論模型構(gòu)建有限元加權(quán)圖拓?fù)涑橄?，以均衡管制?fù)荷和減少協(xié)調(diào)移交負(fù)荷為目標(biāo)，基于遺傳算法適應(yīng)性生成扇區(qū)結(jié)構(gòu)；第二階段綜合等待和改航策略，以緩解區(qū)域總延誤和該區(qū)域造成的區(qū)域外延誤為目標(biāo)，同時(shí)兼顧均攤延誤和減少延誤架次，在區(qū)域內(nèi)容量約束和其他區(qū)域?qū)υ搮^(qū)域的流控約束下，基于NSGA-II進(jìn)行流量時(shí)空優(yōu)化。按照優(yōu)先級順序?qū)嵤┎呗粤鞒?，為緩解空中交通擁堵探索綜合施策框架。仿真結(jié)果表明，所提出的模型算法可為提升空管運(yùn)行品質(zhì)提供輔助決策支持。

關(guān)鍵詞：飛行流量管理；空域管理；空域動(dòng)態(tài)配置；動(dòng)態(tài)扇區(qū)；兩階段協(xié)同規(guī)劃

航空器在空域飛行形成空中交通，空管以保障航空運(yùn)行安全高效和空域使用科學(xué)精益為目標(biāo)，空中交通需求為基本輸入，服務(wù)容量為約束，符合間隔標(biāo)準(zhǔn)的有序交通流為輸出，在管制服務(wù)基礎(chǔ)上逐漸衍生出了空域管理和飛行流量管理功能，推動(dòng)空管從戰(zhàn)術(shù)性或被動(dòng)反應(yīng)式系統(tǒng)向戰(zhàn)略性或前攝式系統(tǒng)發(fā)展。為應(yīng)對日益突出的飛行效率與空域資源配置矛盾，歐美空管系統(tǒng)在流量管理(air traffic flow management,ATFM)實(shí)踐的同時(shí)，不斷探索空域動(dòng)態(tài)配置(dynamic airspace configuration,DAC)，占據(jù)著運(yùn)行概念與技術(shù)應(yīng)用的制高點(diǎn)。國際空管一體化趨勢與無縫運(yùn)行剛性需求與日俱增，對我國運(yùn)行方式與效能提出更高要求，研究DAC和ATFM的協(xié)同規(guī)劃框架方法，對空管運(yùn)行實(shí)踐具有重要指導(dǎo)意義。

1相關(guān)研究

DAC方面，歐美強(qiáng)調(diào)空域結(jié)構(gòu)動(dòng)態(tài)調(diào)整以適應(yīng)具體交通流的運(yùn)行理念，并進(jìn)一步設(shè)想在未來“自由飛行”條件下僅在不能滿足動(dòng)態(tài)航跡需求的區(qū)域建立固定航路結(jié)構(gòu)[1]。在不區(qū)分軍民航空域?qū)傩缘囊惑w化統(tǒng)籌統(tǒng)配模式下，管制扇區(qū)的動(dòng)態(tài)規(guī)劃是DAC的核心，現(xiàn)有研究主要集中在模型選擇上，包括基于區(qū)域元胞(region model/cell model)[2-3]、計(jì)算幾何Voronoi圖(Voronoi diagram model)[4-5]、圖論(graph model)[6-7]和軌跡(flight trajectory model)[8]等建模方法。區(qū)域建模將空域均勻分割為一組多邊形元胞(如文獻(xiàn)[2-3]采用正六邊形)并進(jìn)行管制負(fù)荷或空域復(fù)雜度測度，通過聚類算法[2]、生長算法[3]等將元胞網(wǎng)格組合成負(fù)荷相對均衡的扇區(qū)。與之類似，Voronoi圖建模也以平衡負(fù)荷為目標(biāo)，隨機(jī)生成節(jié)點(diǎn)[4]或繼承導(dǎo)航臺等航路點(diǎn)位置先驗(yàn)[5]作為空間目標(biāo)簇，以空間目標(biāo)的Voronoi多邊形為初始拓?fù)?，基于遺傳算法[4]、模擬退火算法[5]等組合生成扇區(qū)。圖論建模以機(jī)場、航路點(diǎn)為節(jié)點(diǎn)，航段為邊，管制負(fù)荷為點(diǎn)、邊權(quán)重構(gòu)建加權(quán)圖模型，基于遺傳算法[6]、譜聚類算法[7]等切分形成扇區(qū)邊界。軌跡建模比較典型的是以動(dòng)態(tài)密度為性能測度，通過k均值算法聚類航跡實(shí)現(xiàn)空域剖分[8]。Li Jinhua結(jié)合區(qū)域元胞和圖論建模[9]，將矩形元胞覆蓋航路，在繼承航路結(jié)構(gòu)同時(shí)，顯著降低了計(jì)算復(fù)雜度。

ATFM方面，按主要發(fā)展軌跡分為單機(jī)場地面等待模型(single airport ground holding problem, SAGHP)[10]、多機(jī)場地面等待模型(multi-airport ground holding problem, MAGHP)[11]和(使用改航策略的)流量網(wǎng)絡(luò)優(yōu)化模型(air traffic flow network optimization problem,ATFNOP/air traffic flow network optimization with rerouting problem,ATFNORP)[12-15]。早期聚焦機(jī)場交通擁堵，Odoni首先系統(tǒng)闡釋了SAGHP；Bertsimas和Odoni考慮機(jī)場間運(yùn)行關(guān)聯(lián)性和延誤傳播效應(yīng)，建立了MAGHP[11]。隨著研究從以機(jī)場為核心向空域全網(wǎng)演進(jìn)，Bertsimas和Stock將空域抽象為以機(jī)場、扇區(qū)為節(jié)點(diǎn)的扇區(qū)網(wǎng)絡(luò)，在機(jī)場和扇區(qū)容量約束下，優(yōu)化航班起降時(shí)間[12]，并對改航問題建立了動(dòng)態(tài)多任務(wù)網(wǎng)絡(luò)流模型[13]。Bertsimas、Lulli和Odoni進(jìn)一步提出了BLO模型[14]，以延誤代價(jià)最小構(gòu)造超線性目標(biāo)函數(shù)實(shí)現(xiàn)延誤公平分配，綜合地面等待、空中等待、改航、調(diào)速等運(yùn)行策略，并在約束中引入3類不等式，強(qiáng)化模型松弛的多面體結(jié)構(gòu)。受其啟發(fā)，Alonso等提出混合0-1整數(shù)規(guī)劃模型[15]，將扇區(qū)網(wǎng)絡(luò)變?yōu)楹铰肪W(wǎng)絡(luò)，使之更貼近于實(shí)際。此外，Dell′Olmo和Lulli針對航路網(wǎng)絡(luò)設(shè)計(jì)了一種層次迭代模型[16]，上下2層分別用于航路流量“粗粒度”分配和航路上具體航班四維航跡“細(xì)粒度”優(yōu)化。Daniel等考慮緩解空域擁堵程度與航班延誤雙目標(biāo)相互沖突，提出了最小化管制負(fù)荷和均勻降低延誤的多目標(biāo)優(yōu)化模型[17]。上述模型解法涵蓋線性規(guī)劃方法[10]、拉格朗日松弛算法[11-15]、啟發(fā)式算法[16]和進(jìn)化算法[17]。

總體看，兩方面研究自成體系，統(tǒng)籌耦合研究較少。本文主要研究扇區(qū)動(dòng)態(tài)調(diào)整與流量時(shí)空分配的協(xié)同規(guī)劃模型算法。

2問題描述與建模

2.1基本思想

DAC與ATFM以流量需求與空域容量的動(dòng)態(tài)協(xié)調(diào)平衡為紐帶，DAC負(fù)責(zé)科學(xué)設(shè)計(jì)并動(dòng)態(tài)調(diào)整空域容量，ATFM負(fù)責(zé)充分利用空域容量、優(yōu)化調(diào)配流量需求。

前瞻借鑒國際空管運(yùn)行理念，結(jié)合我國運(yùn)行實(shí)際，為降低求解難度，本文認(rèn)為協(xié)同規(guī)劃應(yīng)分階段實(shí)施，其策略手段具有以下優(yōu)先級：①空域是空管職能載體與核心資源，改變以固定劃分、靜態(tài)使用為特征的空域管理模式成為必然趨勢。靜態(tài)扇區(qū)結(jié)構(gòu)難以有效適配時(shí)變的飛行流分布，造成管制席位忙閑不均，制約了容量潛力挖掘，空管應(yīng)以適應(yīng)飛行流動(dòng)態(tài)調(diào)整扇區(qū)構(gòu)形為首要手段，盡量減少對航班運(yùn)行的控制與調(diào)整。因此，設(shè)定根據(jù)初始飛行計(jì)劃實(shí)施DAC的優(yōu)先級高于ATFM。②時(shí)空資源的相關(guān)性，決定了ATFM時(shí)隙路徑聯(lián)動(dòng)分配難分解。但在實(shí)際運(yùn)行中，改航受到嚴(yán)格控制；此外，除遇惡劣天氣、軍事活動(dòng)、突發(fā)事件等造成空域容量驟降，一般空域用戶希望按照原定計(jì)劃路徑飛行，改航可能導(dǎo)致繞飛，帶來額外飛行成本。因此，先以初始飛行計(jì)劃使用等待策略進(jìn)行時(shí)隙調(diào)整，如可改航再同時(shí)使用改航策略和等待策略。

2.2協(xié)同規(guī)劃框架

按照“模塊化分解”和“兩階段協(xié)同”思路，設(shè)計(jì)規(guī)劃基本流程示意如圖1所示。第一階段，根據(jù)目標(biāo)區(qū)域基礎(chǔ)數(shù)據(jù)建立以機(jī)場與導(dǎo)航臺等自然航路點(diǎn)為節(jié)點(diǎn)、航段為邊的無向圖，以無向圖節(jié)點(diǎn)為空間目標(biāo)簇生成Voronoi圖；將Voronoi有限元內(nèi)與有限元間管制負(fù)荷作為點(diǎn)、邊權(quán)重，構(gòu)建約簡加權(quán)圖；以均衡各扇區(qū)內(nèi)管制負(fù)荷和減少扇區(qū)間協(xié)調(diào)移交負(fù)荷為目標(biāo)，對有限元進(jìn)行組合優(yōu)化，適應(yīng)性生成扇區(qū)?？紤]時(shí)變扇區(qū)缺乏歷史數(shù)據(jù)，無法基于管制負(fù)荷歷史峰值的擬合準(zhǔn)確測度容量上限，利用國家飛行流量監(jiān)控中心系統(tǒng)空域仿真與評估子系統(tǒng)對第一階段生成扇區(qū)按間隔標(biāo)準(zhǔn)進(jìn)行航跡仿真，輸出扇區(qū)內(nèi)航段容量。第二階段在新扇區(qū)拓?fù)湎?，以緩解區(qū)域總延誤和該區(qū)域造成的區(qū)域外延誤為根本目的，綜合均攤延誤和控制延誤架次2種常用目標(biāo)策略，以機(jī)場、航路容量和其他區(qū)域?qū)υ搮^(qū)域施加的限流措施為約束，基于“時(shí)空分治”思想，按照時(shí)隙調(diào)整先于路徑調(diào)整的原則，首先調(diào)整初始飛行計(jì)劃的起降時(shí)隙，如容量驟降需避讓相關(guān)空域則啟動(dòng)改航調(diào)整路徑與起降時(shí)隙，對于改航觸發(fā)的流量時(shí)空分布變化，返回第一階段重新生成扇區(qū)劃分，吸收消解因容量不足導(dǎo)致的延誤。新扇區(qū)生成后，按間隔標(biāo)準(zhǔn)及受限航路限流標(biāo)準(zhǔn)仿真輸出各扇區(qū)航段容量，進(jìn)而重新分配起降時(shí)隙。

圖1　空域扇區(qū)與飛行流量協(xié)同規(guī)劃流程

2.3扇區(qū)優(yōu)化模型

Voronoi圖(亦稱Dirichlet剖分)作為一種以等距離原則確定鄰接空間邊界的圖結(jié)構(gòu)成為空域剖分的理想初始拓?fù)溥x擇，在自然繼承航路網(wǎng)結(jié)構(gòu)基礎(chǔ)上，利于管制負(fù)荷統(tǒng)計(jì)?？紤]基于管制操作計(jì)時(shí)、動(dòng)態(tài)密度和空中交通復(fù)雜度的負(fù)荷測度在實(shí)際應(yīng)用中的操作性問題，本文使用一種以管制架次-時(shí)間測度的負(fù)荷表達(dá)。

圖2給出了構(gòu)建空域網(wǎng)絡(luò)有限元加權(quán)圖模型的一個(gè)示例。首先建立航路網(wǎng)無向圖Groute=(V,E),如圖2a)所示。其中,V={v1,v2,…,vNV}為機(jī)場與航路點(diǎn)集,|V|=NV,E={e1,e2,…,eNE}為航段集,|E|=NE。然后加載以V為空間目標(biāo)簇的Voronoi圖Dvoronoi={D(v1),D(v2),…,D(vNV)},其中，D(vi)={x|d(x,vi)≤d(x,vi′),?vi′∈V},d為歐氏距離函數(shù),D(vi)為vi的Voronoi多邊形。為避免航路交叉點(diǎn)與扇區(qū)邊界小于規(guī)定距離,以及機(jī)場與其進(jìn)近導(dǎo)航臺劃分于不同扇區(qū),對于相距過近的節(jié)點(diǎn)移除兩點(diǎn)之間的Voronoi多邊形邊界使之合并于一個(gè)有限元內(nèi),如圖2b)所示。相鄰Voronoi多邊形之間可能存在不止一條航段穿越,為簡化圖形,將穿越的多條航段合并表示為一條邊,并以點(diǎn)表示Voronoi多邊形,形成圖2c)所示約簡圖模型。

圖2　空域網(wǎng)絡(luò)有限元加權(quán)圖模型構(gòu)建示意圖

D(vi)抽象的點(diǎn)權(quán)為

(1)

相鄰D(vi)與D(vi′)間邊權(quán)為

(2)

設(shè)扇區(qū)集S={sj},|S|=NS(sj、NS為變量),T時(shí)段內(nèi)NS可按下式確定

(3)

為方便分析,將管制負(fù)荷簡化分解為監(jiān)控負(fù)荷與協(xié)調(diào)移交負(fù)荷,基于上述約簡加權(quán)圖的點(diǎn)、邊權(quán)重測度方法,分別定義如下:

扇區(qū)sj的監(jiān)控負(fù)荷為

(4)

相鄰扇區(qū)sj與sj′間的協(xié)調(diào)移交負(fù)荷為

(5)

定義指派變量xij,xij=1表示第i個(gè)Voronoi多邊形屬于第j個(gè)扇區(qū),否則為0,則扇區(qū)sj監(jiān)控負(fù)荷與協(xié)調(diào)移交負(fù)荷可表達(dá)為

(6)

(7)

以平衡各扇區(qū)管制負(fù)荷、最小化扇區(qū)間總協(xié)調(diào)移交負(fù)荷為目標(biāo),則目標(biāo)函數(shù)為

(8)

從(8)式可明顯看出,扇區(qū)間總協(xié)調(diào)移交負(fù)荷越小,J越小;對于給定扇區(qū)間總協(xié)調(diào)移交負(fù)荷,各扇區(qū)管制負(fù)荷相等時(shí),J最小。

約束條件包括

(9)

(10)

(11)

其中,(9)式確保每個(gè)Voronoi多邊形只能屬于一個(gè)扇區(qū);(10)式確保每個(gè)扇區(qū)至少由一個(gè)Voronoi多邊形組成;(11)式為決策變量0-1整型約束。

此外,扇區(qū)構(gòu)形須在滿足幾何連通性約束基礎(chǔ)上,確保在航路方向上的凸形約束,防止同一次飛行過程中,同一架航空器2次進(jìn)入相同扇區(qū),增加不必要的協(xié)調(diào)移交負(fù)荷(凸約束可能需要在優(yōu)化后進(jìn)一步人工調(diào)整)。

2.4流量優(yōu)化模型

對于給定區(qū)域,在上述機(jī)場、航路、扇區(qū)(點(diǎn)、線、面)三位一體的拓?fù)浣Y(jié)構(gòu)下,建立開放式流量網(wǎng)絡(luò)優(yōu)化模型,相關(guān)參數(shù)及符號約定如下:

時(shí)隙集T={ti},ti為第i個(gè)等分時(shí)隙,|T|=NT+1,并假設(shè)tNT+1消化前NT個(gè)時(shí)隙內(nèi)未分配的流量需求,確保問題具有可行解;

機(jī)場集Q={qk},|Q|=NQ;

扇區(qū)集S={sj},|S|=NS;

航班集F=Fd∪Fa∪Fc,Fd為區(qū)域內(nèi)出港航班集,Fa為區(qū)域內(nèi)進(jìn)港航班集,Fc為區(qū)域內(nèi)穿越航班集,|F|=NF;聯(lián)程航班對集B={(f,f′)|f,f′∈F},f為前繼航班,f′為后續(xù)航班,|B|=NB;

df、af分別為初始計(jì)劃的進(jìn)入和離開區(qū)域時(shí)隙;

bff′為聯(lián)程航班的周轉(zhuǎn)時(shí)間;

Ak(t)、Dk(t)分別為機(jī)場qk在t時(shí)的進(jìn)離場容量,二者相互影響,可用凸?fàn)罘蔷€性函數(shù)曲線表示,如圖3所示；

圖3　基于歷史運(yùn)行數(shù)據(jù)的機(jī)場容量曲線示意圖

優(yōu)化區(qū)域的總延誤時(shí)間分為因本區(qū)域容量不足造成的區(qū)域內(nèi)地面等待、空中延誤時(shí)間(包括改航造成的飛行延誤和空中盤旋等待時(shí)間)和因本區(qū)域限流造成的區(qū)域外延誤時(shí)間(包括向上游區(qū)域前推的地面等待和改航造成的飛行延誤時(shí)間)2部分,具體包括:Fda內(nèi)航班的區(qū)域內(nèi)地面等待和空中延誤時(shí)間,Fad、Fc內(nèi)航班的區(qū)域外延誤和區(qū)域內(nèi)空中延誤時(shí)間,Fd∩a內(nèi)航班的區(qū)域內(nèi)地面等待和空中延誤時(shí)間。

對于f∈Fda∪Fd∩a,區(qū)域內(nèi)地面等待時(shí)間為

(12)

對于f∈Fad∪Fc,區(qū)域外延誤時(shí)間為

(13)

對于f∈Fda∪Fad∪Fd∩a∪Fc,區(qū)域內(nèi)空中延誤時(shí)間為

(14)

以總延誤代價(jià)最小為目標(biāo),則目標(biāo)函數(shù)為

(15)

加入e1、e2表示延誤代價(jià)的超線性增長,目標(biāo)函數(shù)將引導(dǎo)延誤均勻分配,避免個(gè)別航班延誤超長。例如,選擇2個(gè)航班均攤2個(gè)時(shí)隙的地面等待時(shí)間將優(yōu)于1個(gè)航班延誤2個(gè)時(shí)隙。同時(shí),由于空中延誤代價(jià)高于地面等待,令e2>e1。

則目標(biāo)函數(shù)為

(16)

由于飛行流系統(tǒng)區(qū)域流控波及效應(yīng)突出,為減少對上游區(qū)域的影響,以本區(qū)域造成的區(qū)域外延誤代價(jià)最小為目標(biāo),則目標(biāo)函數(shù)為

(17)

同樣,相對C3以執(zhí)行區(qū)域外地面等待最少為目標(biāo),則目標(biāo)函數(shù)為

(18)

約束條件包括

(19)

(20)

(21)

(22)

(23)

(24)

orinf,destf∈A

(25)

sj∈S,orinf,destf

(26)

sj∈S,orinf,destf

(27)

3兩階段求解方法

本文所建立的扇區(qū)與流量協(xié)同規(guī)劃模型具有兩階段、多目標(biāo)、非線性的特點(diǎn),適于智能優(yōu)化算法求解。

3.1基于Voronoi-加權(quán)圖的扇區(qū)優(yōu)化遺傳算法

步驟1構(gòu)造航路網(wǎng)無向圖的Voronoi圖,根據(jù)各有限元內(nèi)航路結(jié)構(gòu)及有限元鄰接關(guān)系,按(1)、(2)式計(jì)算有限元內(nèi)權(quán)重及相鄰邊權(quán),形成約簡加權(quán)圖,并按(3)式確定劃分扇區(qū)數(shù)m。

步驟2以m為圖的子集數(shù),隨機(jī)選取m個(gè)有限元的空間目標(biāo)進(jìn)行1～m的整數(shù)編碼形成m個(gè)子集,并將這m個(gè)空間目標(biāo)的鄰元?dú)w入m個(gè)子集賦以相同編碼,未被編碼的空間目標(biāo)歸入相鄰子集,生成初始種群,設(shè)定種群規(guī)模及終止代數(shù)τmax,進(jìn)化代數(shù)τ=0。

步驟3按(8)式取反計(jì)算種群個(gè)體適應(yīng)度。

步驟4進(jìn)行選擇、交叉和變異,并使用精英策略。選擇使用錦標(biāo)賽方式。交叉算子可能破壞幾何連通性,為此采用文獻(xiàn)[6]中修復(fù)策略及基于Hamming距離的交叉選擇。變異算子使負(fù)荷最小的子集奪取鄰近負(fù)荷最大子集的有限元。

步驟5τ=τ+1,當(dāng)τ<τmax時(shí),跳轉(zhuǎn)至步驟3,否則結(jié)束。

3.2基于NSGA-II的流量時(shí)空優(yōu)化算法

步驟1預(yù)處理以下航班信息:航班編號、航班類別、起飛機(jī)場、降落機(jī)場、飛行速度、計(jì)劃經(jīng)過扇區(qū)與航段、備選改航扇區(qū)與航段、計(jì)劃進(jìn)入本區(qū)域時(shí)間、計(jì)劃離開本區(qū)域時(shí)間、可行進(jìn)入本區(qū)域時(shí)間、可行離開本區(qū)域時(shí)間、MINIT受控航班標(biāo)志位、MINIT流量控制時(shí)間間隔、聯(lián)程航班標(biāo)志位、聯(lián)程航班周轉(zhuǎn)時(shí)間。

(28)

(29)

(30)

(31)

式中

(32)

步驟4根據(jù)個(gè)體序值與同一前端擁擠距離使用錦標(biāo)賽選擇,然后對f的時(shí)隙位基因使用多點(diǎn)交叉和隨機(jī)變異算子,生成子種群。

步驟5合并父子種群,重新計(jì)算序值與同一前端擁擠距離,通過錦標(biāo)賽選擇修剪至種群規(guī)模。

步驟6τ=τ+1,當(dāng)τ<τmax時(shí),跳轉(zhuǎn)至步驟9;否則結(jié)束。

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

以北京飛行情報(bào)區(qū)為例,選取區(qū)內(nèi)13個(gè)機(jī)場,202個(gè)導(dǎo)航臺及報(bào)告點(diǎn),71條航段構(gòu)成的拓?fù)渚W(wǎng)絡(luò)和2015年9月某日10:00～12:00區(qū)內(nèi)實(shí)際運(yùn)行的571架次航班為研究對象,應(yīng)用上述模型算法進(jìn)行優(yōu)化求解。在驗(yàn)證DAC-ATFNOP-(航段容量下降的)ATFNORP-DAC-ATFNOP協(xié)同規(guī)劃流程框架時(shí),歸并相似環(huán)節(jié)、簡化實(shí)驗(yàn)步驟,假設(shè)在現(xiàn)有靜態(tài)扇區(qū)拓?fù)湎?受區(qū)域內(nèi)天氣及其他區(qū)域限流影響,部分航段通行能力下降,以初始飛行計(jì)劃為基礎(chǔ)實(shí)施改航操作,然后進(jìn)行動(dòng)態(tài)扇區(qū)生成。

流量優(yōu)化階段,以Δ=5 min為一個(gè)時(shí)間片,|T|=25,e1=0.1,e2=0.3,種群大小取400,算法終止代數(shù)取500,交叉概率取0.7,變異概率取0.1,分別以C1～C4為主要目標(biāo)的前端解見表1;

表1　多目標(biāo)流量優(yōu)化方案結(jié)果

以C1為主要目標(biāo),選取方案1進(jìn)行優(yōu)化調(diào)控。若按先到先服務(wù)策略(first come first serve,FCFS),共需調(diào)整航班181架次,總延誤代價(jià)2 578 Δ。相較FCFS,總延誤時(shí)間減少了約31%,執(zhí)行地面/空中延誤策略減少了約50%。

扇區(qū)優(yōu)化階段,種群大小取200,算法終止代數(shù)取200,交叉概率取0.4,變異概率取0.2,Voronoi初始拓?fù)渑c最優(yōu)扇區(qū)劃分結(jié)果見圖4,扇區(qū)優(yōu)化前后性能指標(biāo)見表2。

圖4　10:00～12:00最優(yōu)扇區(qū)劃分結(jié)果

扇區(qū)μ/%σ/(架次·min)ω/%優(yōu)化前45.0458優(yōu)化后24.5216 40

表2中引入總負(fù)荷平衡系數(shù)μ、標(biāo)準(zhǔn)差σ和協(xié)調(diào)移交負(fù)荷減少率ω個(gè)性能指標(biāo),測度如下

(33)

式中,Wmax、Wmin分別為扇區(qū)最大和最小負(fù)荷。

(34)

(35)

在新扇區(qū)拓?fù)湎?按改航后的流量分布進(jìn)一步調(diào)整時(shí)隙后,相較在當(dāng)前扇區(qū)拓?fù)湎聠?dòng)改航策略,總延誤代價(jià)減少了約11%,執(zhí)行地面/空中延誤策略減少了約20%。綜合兩階段,運(yùn)行效能得到較大改觀。

5結(jié)論

本文旨在為空域與飛行流量協(xié)同規(guī)劃方法層面探索綜合施策框架提供初步思路,在機(jī)場、航路、扇區(qū)構(gòu)成的拓?fù)浣Y(jié)構(gòu)下,將機(jī)場、航路容量及扇區(qū)負(fù)荷有機(jī)整合,并系統(tǒng)考慮區(qū)域內(nèi)外影響,基于扇區(qū)動(dòng)態(tài)劃分與流量時(shí)空優(yōu)化,構(gòu)建了兩階段多目標(biāo)的協(xié)同規(guī)劃模型及算法,結(jié)合管制區(qū)實(shí)際運(yùn)行數(shù)據(jù)驗(yàn)證了有效性。從飛行流運(yùn)行特點(diǎn)和模型本身來看,本文既適用于區(qū)域性優(yōu)化調(diào)控,也適用于國家尺度的全局優(yōu)化。

鑒于研究側(cè)重確定條件建模,對惡劣天氣等隨機(jī)因素刻畫不足;同時(shí),需考慮高度層劃分,將空域結(jié)構(gòu)與流量調(diào)配由2D優(yōu)化向3D拓展,以便于實(shí)際應(yīng)用;在求解算法的性能改進(jìn)方面也尚有提升空間。這些也是下一步的研究重點(diǎn)。

參考文獻(xiàn)：

[1]ICAO Doc9854-AN/458. Gloabal Air Traffic Management Operational Concept[S]. Montreal: ICAO, 2005

[2]Yousfi A, Donohue G. Temporal and Spatial Distribution of Airspace Complexity for Air Traffic Controller Workload-Based Sectorization[C]∥Proceedings of the 4thAIAA Aviation Technology, Integration and Operations Conference, 2004: 1-14

[3]Klein A. An Efficient Method for Airspace Analysis and Partitioning Based on Equalized Traffic Mess[C]∥Proceedings of the 6thUSA/Europe Air Traffic Management Research and Development, 2005: 1-10

[4]Delahaye D, Schoenauer M, Alliot J M. Airspace Sectoring by Evolutionary Computation[C]∥Proceedings of the IEEE International Conference on Evolutionary Computation, 1998: 218-223

[5]韓松臣, 張明. 依據(jù)管制工作負(fù)荷的扇區(qū)優(yōu)化新方法[J]. 南京航空航天大學(xué)學(xué)報(bào), 2004, 36(1): 91-96

Han Songchen, Zhang Ming. Optimization Method for Sector Partition Based on Control Workload[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2004, 36(1): 91-96 (in Chinese)

[6]Chen Yangzhou, Bi Hong, Zhang Defu, Song Zhuoxi. Dynamic Airspace Sectorization via Improved Genetic Algorithm[J]. J Mod Transport, 2013, 21(2): 117-124

[7]Li Jinhua, Wang Tong, Savai M, Hwang I. Graph-Based Algorithm for Dynamic Airspace Configuration[J]. Journal of guidance, control, and dynamics, 2010, 33(4): 1082-1094

[8]Brinton C, Pledgie S. Airspace Partitioning Using Flight Clustering and Computational Geometry[C]∥Proceedings of the 27thDigital Avionics Systems Conference, 2008: 3-10

[9]Li Jinhua, Seah C E, Hwang I. An Algorithm for Dynamic Airspace Configuration Based on the Air Route Structure[C]∥AIAA Guidance, Navigation, and Control Conference, 2009

[10] Bianco L, Odoni A R. Large-Scale Computation and Information Processing in Air Traffic Control[M]. Berlin, Springer-Verlag, 1993

[11] Vranas P B, Bertsimas D J, Odoni A R. The Multi-Airport Ground-Holding Problem in Air Traffic Control[J]. Operations Research, 1994, 42(2): 249-261

[12] Bertsimas D, Stock S. The Air Traffic Flow Management Problem with Enroute Capacities[J]. Operations Research, 1998, 46: 406-422

[13] Bertsimas D, Stock S. The Traffic Flow Management Rerouting Problem in Air Traffic Control: A Dynamic Network Flow Approach[J]. Transportation Science, 2000, 34(3): 239-255

[14] Bertsimas D, Lulli G, Odoni A R. An Integer Optimization Approach to Large-Scale Air Traffic Flow Management[J]. Operations Research, 2011, 59(1): 211-227

[15] Agustín A, Alonso-Ayuso A, Escudero L F, Pizarro C. On Air Traffic Flow Management with Rerouting. Part Ⅰ: Deterministic Case[J]. European Journal of Operational Research, 2012, 219: 156-166

[16] Dell′Olmo P, Lulli G. A New Hierarchical Architecture for Air Traffic Management: Optimisation of Airway Capacity in a Free Flight Scenario[J]. European Journal of Operational Research, 2003, 144: 179-193

[17] Daniel D, Oussedik S, Stephane P. Airspace Congestion Smoothing by Multi-Objective Genetic Algorithm[C]∥Proceedings of the 2005 ACM Symposium on Applied Computing, Santa Fe, 2005: 907-912

[18] 胡一波. 求解約束優(yōu)化問題的幾種智能算法[D]. 西安:西安電子科技大學(xué), 2009

Hu Yibo. Several Intelligent Algorithms for Constrained Optimization Problems[D]. Xi′an: Xidian University, 2009 (in Chinese)

Two-Stage Model and Algorithm for Airspace and Traffic Flow Collaborative Programming Based on Dynamic Sectorization

Yao Di1,2, Wang Ying1

1.College of Equipment Management & Safety Engineering, Air Force Engineering University, Xi′an 710051, China 2.State Air Traffic Flow Management Center, Beijing 100094, China

Abstract:Aiming at the coupling interaction of dynamic airspace sectorization and the space-time allocation of air traffic flow, we establish a two-stage collaborative programming model and solution framework to maximize the operational capacity and efficiency. The first stage begins with the construction of a Voronoi cells based weighted graph model combined with Voronoi diagram and graph theory for the topological structure of given airspace and air traffic distribution. Then, the sector re-partitioning problem is solved based on genetic algorithm to balance the sector workloads and minimize the coordination workloads. In the second stage, we built air traffic flow network optimization model to reduce the total delay fairly, the ground delay out of the area fairly, the total number of delayed fights and the number of ground-delayed fights out of the area, with the airspace capacity constraint in the area and the minutes-in-trail restriction out of the area. Then, the multi-objective optimization problem is solved based on the non-dominated sorting genetic algorithm II (NSGA-II) for a combination of flow management actions, including ground holding, airborne holding, and rerouting. We explore the comprehensive framework for alleviating the traffic congestion according to the priority order of strategies described above. Simulation results show that: the proposed model can provide supporting decision-making for improving the operational quality of air traffic management.

Keywords:air traffic management; air traffic flow management; airspace management; algorithms; computer simulation; decision making; dynamic airspace configuration; dynamic airspace sectorization; efficiency; genetic algorithms; mathematical models; NSGA II (non-dominated sorting genetic algorithm II); optimization; topology; two-stage collaborative programming; Voronoi cells; Voronoi diagram

收稿日期：2015-12-01

基金項(xiàng)目：國家自然科學(xué)基金(71171199)與國家空管“十二五”科研專項(xiàng)課題(GKG201401003)資助

作者簡介：姚頔(1984—)，空軍工程大學(xué)博士研究生，主要從事信息系統(tǒng)工程與智能決策、空域與飛行流量管理的研究。

中圖分類號：V355.1

文獻(xiàn)標(biāo)志碼：A

文章編號:1000-2758(2016)04-0549-09