王建忠，丁小芹，王樹偉

(1.中國(guó)民航大學(xué)，空中交通管理學(xué)院，天津 300300；2.民航天津空中交通管理分局，天津 300300)

0 引言

雖然近年航空業(yè)受到了前所未有的沖擊，但空中交通流量的增長(zhǎng)勢(shì)頭依舊十分迅猛。美國(guó)聯(lián)邦航空局(FAA)和航空工業(yè)預(yù)測(cè)未來20 年的增長(zhǎng)率將在150%～250%之間[1]，預(yù)計(jì)到2025 年，全球航班的乘客將至少比2012 年增加50%[2]，到2037 年，全球機(jī)場(chǎng)處理的航空乘客數(shù)量預(yù)計(jì)將翻一番，達(dá)到約82億人次。隨著不斷增長(zhǎng)的交通量，空中交通擁堵愈發(fā)嚴(yán)重，終端區(qū)內(nèi)航班出現(xiàn)大面積延誤的概率大大提高，這不僅將對(duì)航空公司的運(yùn)營(yíng)成本產(chǎn)生不利影響，而且當(dāng)頻繁的延誤在航空運(yùn)輸網(wǎng)絡(luò)上蔓延時(shí)，將導(dǎo)致整個(gè)網(wǎng)絡(luò)變得脆弱，使得乘客對(duì)航空運(yùn)輸?shù)臐M意度日趨下降，同時(shí)給環(huán)境造成的不利影響也更加嚴(yán)重。

在確保航空器運(yùn)行安全的前提下，為提高終端區(qū)運(yùn)行效率以及跑道資源利用率，緩解航空運(yùn)輸網(wǎng)絡(luò)上的延誤問題，國(guó)內(nèi)外專家針對(duì)進(jìn)離場(chǎng)航空器的排序問題展開一系列研究。王菲等[3]實(shí)現(xiàn)對(duì)離場(chǎng)航空器的實(shí)時(shí)動(dòng)態(tài)排序，確定允許開車時(shí)間為管制員提供決策支持；Faye 等[4]使用間隔時(shí)間矩陣和時(shí)間離散化來研究單跑道和多跑道飛機(jī)著陸問題；Mur?a等[5]開發(fā)了用于飛機(jī)著陸排序和調(diào)度的混合整數(shù)線性規(guī)劃模型，通過特定航站樓到達(dá)路線控制機(jī)場(chǎng)交通流的問題，并結(jié)合著陸時(shí)間窗和優(yōu)先權(quán)的操作約束，實(shí)現(xiàn)動(dòng)態(tài)環(huán)境下的優(yōu)化；Díaz等[6]依據(jù)噪聲對(duì)人群的影響將噪音指標(biāo)與飛機(jī)排序結(jié)合起來，并使用西班牙馬德里機(jī)場(chǎng)的真實(shí)數(shù)據(jù)，比較取不同的最大位移約束值對(duì)模型產(chǎn)生的影響；張啟錢等[7]以管制負(fù)荷與航班延誤總成本最小為目標(biāo)，采用滾動(dòng)時(shí)域控制策略建立進(jìn)離場(chǎng)航班多目標(biāo)動(dòng)態(tài)優(yōu)化模型；王寧等[8]考慮點(diǎn)融合程序下終端區(qū)航空器排序問題，提出以0-1 整數(shù)規(guī)劃為基礎(chǔ)的多跑道進(jìn)場(chǎng)航班優(yōu)化排序模型；Oren等[9]提出多到達(dá)路線點(diǎn)融合系統(tǒng)，基于每架飛機(jī)的航路分配和航路點(diǎn)分配實(shí)現(xiàn)最優(yōu)排序；馬園園等[10]從時(shí)空維度引入“航班滿意度”的概念，探索多機(jī)場(chǎng)交通流排序方法；張軍峰等[11]引入“外圍航班流”的概念，以最小化航班延誤為目標(biāo)，建立多機(jī)場(chǎng)進(jìn)離場(chǎng)協(xié)同排序模型。

目前國(guó)內(nèi)外對(duì)于航空器進(jìn)離場(chǎng)排序優(yōu)化的研究成果頗多，但現(xiàn)有研究仍存在以下不足：(1)在進(jìn)離場(chǎng)排序優(yōu)化過程中，對(duì)于管制員負(fù)荷的問題，通常僅從航空器位置轉(zhuǎn)換次數(shù)或發(fā)生延誤的航空器數(shù)量等方面作簡(jiǎn)單處理。(2)常使用的各種優(yōu)化策略均為航空器著陸、起飛提供一個(gè)具體的時(shí)間點(diǎn)，但在實(shí)際運(yùn)行過程中時(shí)常會(huì)出現(xiàn)干擾或誤差，此時(shí)模型的優(yōu)化結(jié)果將很可能不再具有可操作性。針對(duì)上述問題，本文以進(jìn)離場(chǎng)航班為對(duì)象，通過具體分析進(jìn)離場(chǎng)航班間潛在沖突，考慮管制員在實(shí)際指揮過程中需要花費(fèi)時(shí)間精力發(fā)布指令(加速、減速、改變飛行角度等)對(duì)飛機(jī)間存在的潛在沖突問題進(jìn)行解脫，從時(shí)間維度利用潛在沖突發(fā)生時(shí)長(zhǎng)刻畫管制員解決沖突的負(fù)荷，建立多目標(biāo)時(shí)間索引模型，在為每架航空器分配著陸、起飛時(shí)隙，提高模型優(yōu)化結(jié)果抗干擾能力的同時(shí)盡可能減少進(jìn)離場(chǎng)航班潛在沖突，以最大程度降低由排序引起的管制員負(fù)荷增加，達(dá)到提高終端區(qū)運(yùn)行效率和安全的目標(biāo)。

1 進(jìn)場(chǎng)和離場(chǎng)航班潛在沖突分析

1.1 進(jìn)場(chǎng)-離場(chǎng)沖突分析

設(shè)t=0 時(shí)第一架航班到達(dá)下降頂點(diǎn)或抬輪離地，此時(shí)進(jìn)場(chǎng)航班g所在高度為h，下降率為b，水平速度為vg，到航線交叉點(diǎn)o的距離為dg；離場(chǎng)航班f的上升率為a，水平速度為vf，到航線交叉點(diǎn)o的距離為df；航班最小垂直間隔為sfg，最小水平間隔為；航線間夾角為α、β、λ、γ，具體如圖1所示。t時(shí)刻航班的所在位置詳見下文。

圖1 進(jìn)離場(chǎng)航班潛在沖突示意圖Fig.1 Schematic diagram of potential conflicts on arrival and departure aircraft

1.1.1 垂直方向分析

離場(chǎng)航班f所在高度hf=at，進(jìn)場(chǎng)航班g所在高度hg=h-bt，則兩航班之間的高度差為Δh=|h-(a+b)t|。

情形1 Δh∈[sfg,+∞)，航班f和航班g在垂直方向上無沖突。

情形2 Δh∈[ 0,sfg)，航班f和航班g垂直間隔不滿足，垂直方向上存在沖突，且在管制員無干預(yù)的情形下，航班f和航班g之間的垂直間隔先減小后增大。令Δh=sfg可得，則垂直方向上的沖突時(shí)間為[t1,t2] 。

1.1.2 水平方向分析

情形1 離場(chǎng)航班f為前序航班，在tf=時(shí)刻到達(dá)航線交叉點(diǎn)o，設(shè)此時(shí)進(jìn)場(chǎng)航班g到航線交叉點(diǎn)o的距離為L(zhǎng)，則到達(dá)航路交叉點(diǎn)o的時(shí)間tg=tf+Lvg。

(1)當(dāng)t∈(-∞,tf)時(shí)，兩架航班之間的距離平方為

(2) 當(dāng)t∈[tf,tg] 時(shí)，兩架航班之間的距離平方為

(3)當(dāng)t∈(tg,+∞)時(shí)，兩架航班之間的距離平方為

同理可得情形2，當(dāng)進(jìn)場(chǎng)航班g為前序航班，航班g到達(dá)航路交叉點(diǎn)o的時(shí)間tg=dgvg，進(jìn)場(chǎng)航班f距離航線交叉點(diǎn)o為L(zhǎng)，到達(dá)航路交叉點(diǎn)o的時(shí)間tf=tg+Lvf時(shí)，可得到如下沖突臨界時(shí)刻：

綜上所述，通過計(jì)算可得航班f和航班g之間所有可能發(fā)生水平?jīng)_突的臨界時(shí)刻，再結(jié)合具體航班速度、航線夾角分布等情況，便可獲得水平方向上沖突持續(xù)時(shí)間區(qū)間。當(dāng)離場(chǎng)航班f為前序航班時(shí)，[t3,t4]=[min{ta,tf,tb,tc,tg},max{ta,tf,tb,tc,tg} ]；當(dāng)進(jìn)場(chǎng)航班g為前序航班時(shí)，[t3,t4]=

若[t1,t2] ∩[t3,t4]=?，則說明航班f和航班g之間至少滿足一個(gè)方向上的最小間隔要求，兩航班之間無沖突發(fā)生；若[t1,t2] ∩[t3,t4]=[ts,tx]，則說明航班f和航班g在區(qū)間[ts,tx]上水平和垂直最小間隔要求均不滿足，兩航空器之間存在沖突，需要管制員干預(yù)，且當(dāng)[ts,tx] 區(qū)間長(zhǎng)度越大時(shí)，需要管制員付出的精力就越多，所產(chǎn)生的工作負(fù)荷就越大。

1.2 進(jìn)場(chǎng)-進(jìn)場(chǎng)沖突分析

對(duì)于兩架離場(chǎng)航班而言，由于本文以單跑道為研究對(duì)象，故不特別考慮離場(chǎng)航班間的交叉航線潛在沖突問題，僅在模型的間隔約束部分考慮使用同一離場(chǎng)航線的時(shí)間間隔。

2 問題描述與建模

2.1 問題描述

為減少進(jìn)離場(chǎng)排序中由潛在沖突引起的管制員工作負(fù)荷增加，提高排序結(jié)果的可執(zhí)行性，本文以單跑道運(yùn)行為背景，設(shè)航班集合為F=F1∩F2，其中，F(xiàn)1為進(jìn)場(chǎng)航班集合，F(xiàn)2為離場(chǎng)航班集合，引入Heidt[12]提出的時(shí)間索引模型，以步長(zhǎng)Δt將優(yōu)化時(shí)間區(qū)間TD=[tstart,tend] 離散化為時(shí)間點(diǎn)集TD={tstart,tstart+Δt,tstart+2Δt,…,tend} 。用區(qū)間表示航班i的最早和最晚著陸或起飛時(shí)間，通過兩者取交集的方式，可將航班i的有效著陸或起飛時(shí)間點(diǎn)表示為

最終可將航班i的起飛或著陸時(shí)間安排在相鄰有效時(shí)間點(diǎn)和之間的時(shí)隙上。

基于以上，本文致力于建立多目標(biāo)時(shí)間索引模型，為進(jìn)離場(chǎng)航班分配起飛和著陸時(shí)隙。

2.2 多目標(biāo)時(shí)間索引模型

2.2.1 優(yōu)化目標(biāo)

航班延誤時(shí)間和管制員工作負(fù)荷是影響終端區(qū)運(yùn)行效率和安全的重要影響因素。因此，以進(jìn)離場(chǎng)航班的總體延誤時(shí)間最小以及排序中潛在沖突引起的管制員工作負(fù)荷增加最小為優(yōu)化目標(biāo)，建立進(jìn)離場(chǎng)航班協(xié)同排序的多目標(biāo)時(shí)間索引模型，即

2.2.2 約束條件

(1)時(shí)隙約束

式中：ωi,m、ωj,m為0-1變量，當(dāng)航班i或航班j在時(shí)隙m上時(shí)等于1，否則為0。式(11)表示一個(gè)時(shí)隙最多只能安排一架進(jìn)離場(chǎng)航班；式(12)和式(13)表示一架進(jìn)離場(chǎng)航班只能分配給一個(gè)時(shí)隙。

(2)安全間隔約束

當(dāng)一架航班被分配在時(shí)隙m上時(shí)，為了保證最小安全間隔，則相鄰的另一架航班將被禁止安排在以下時(shí)隙上

由于不同運(yùn)行狀態(tài)的航班之間應(yīng)該滿足不同的最小安全間隔，因此本文設(shè)定最小安全間隔集合δ={δA,δD,δAD,δDA}，整合不同運(yùn)行狀態(tài)下相鄰兩架航班之間的安全間隔約束。其中，δA為兩架進(jìn)場(chǎng)航班的最小時(shí)間間隔；δD為兩架離場(chǎng)航班的最小時(shí)間間隔，對(duì)于使用同一離場(chǎng)航線的連續(xù)航班，則需要在原有的最小時(shí)間間隔上增加時(shí)間ΔtD以避免發(fā)生沖突；δAD為先進(jìn)場(chǎng)后離場(chǎng)航班的最小時(shí)間間隔；δDA為先離場(chǎng)后進(jìn)場(chǎng)航班的最小時(shí)間間隔。

(3)位置轉(zhuǎn)換約束

在基于先到先服務(wù)的航班序列基礎(chǔ)上，每架航班的移動(dòng)位置不能超過其最大偏移量，即

式中：Ni為先到先服務(wù)模式下航班i在隊(duì)列中的序號(hào)；為經(jīng)過優(yōu)化后航班i在隊(duì)列中的序號(hào)；M為最大位置偏移量。

3 求解算法

進(jìn)離場(chǎng)航班協(xié)同排序問題是典型的NP-hard問題[10]。確定航班最佳起飛著陸順序的計(jì)算量是一個(gè)階乘函數(shù)，具有高度復(fù)雜性，因此近年來的研究大多集中在開發(fā)啟發(fā)式求解算法上[13]。從以往的研究結(jié)論中可知，在航班排序調(diào)度等優(yōu)化模型的求解計(jì)算方面，相比于CPLEX等商業(yè)求解器，啟發(fā)式算法的運(yùn)算能力更強(qiáng)，對(duì)于同樣的優(yōu)化模型，啟發(fā)式算法可能在幾秒至幾十秒內(nèi)找到最優(yōu)解，而CPLEX等商業(yè)求解器則可能需要幾十分鐘甚至更長(zhǎng)，很難滿足空管系統(tǒng)內(nèi)實(shí)時(shí)排序的需求。為此，設(shè)計(jì)遺傳算法對(duì)模型進(jìn)行求解。

優(yōu)化模型涉及進(jìn)離場(chǎng)航班總延誤時(shí)間以及排序中潛在沖突引起的管制員工作負(fù)荷增加，為便于后續(xù)計(jì)算，利用加權(quán)求和的方法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題。

3.1 編碼方法

針對(duì)進(jìn)離場(chǎng)航班協(xié)同排序問題特點(diǎn)，采用序數(shù)編碼策略，生成可以直接表示進(jìn)離場(chǎng)航班順序的染色體序列，再通過結(jié)合位置轉(zhuǎn)換約束條件生成部分初始可行解。序數(shù)編碼方式不僅可以直觀表示航班集合，便于后續(xù)時(shí)隙分配和約束條件的驗(yàn)證，而且加快初始解生成速度提高計(jì)算效率。

3.2 適應(yīng)度函數(shù)

模型涉及的多目標(biāo)函數(shù)均為最小型函數(shù)，故將適應(yīng)度函數(shù)F定義為兩個(gè)帶有一定權(quán)重w1、w2的目標(biāo)函數(shù)Z1、Z2之和的倒數(shù)，即

針對(duì)給定的航班起降次序，首先按照順序依次為航班分配既能減少延誤時(shí)間又可以滿足最小安全時(shí)間間隔的時(shí)隙，確保所有進(jìn)離場(chǎng)航班既滿足時(shí)隙約束又滿足安全間隔約束；然后按照分配的時(shí)隙計(jì)算給定次序?qū)?yīng)的適應(yīng)度值。

3.3 遺傳操作

選擇操作利用代溝來控制每代中種群被替換的比例，再結(jié)合隨機(jī)遍歷抽樣方法獲得繼續(xù)進(jìn)行交叉、變異的種群。隨機(jī)遍歷抽樣方法在輪盤賭方法的基礎(chǔ)上得到進(jìn)一步優(yōu)化，它等間距的選擇不同適應(yīng)度的個(gè)體，使得每個(gè)個(gè)體被選中的機(jī)會(huì)“均等”，有利于保持種群的多樣性。

對(duì)選擇得到的種群采用部分匹配交叉的方法。隨機(jī)在父代染色體上選擇一個(gè)基因位作為交叉起點(diǎn)，并選擇自起點(diǎn)位向后的第5個(gè)基因位為交叉終點(diǎn)，將這兩點(diǎn)間的基因進(jìn)行交換，交換完成后進(jìn)行沖突檢測(cè)以確保子代染色體中沒有重復(fù)基因，部分匹配交叉流程如圖2所示。

圖2 部分匹配交叉示意圖Fig.2 Diagram of partially-matched crossover

變異操作則是隨機(jī)選取某一基因?yàn)樽儺悓?duì)象，交換該基因與下一位置基因的次序。

通過不斷的交叉、變異操作增加種群多樣性，使得種群能夠在搜索空間中被更廣泛的探索。最終以達(dá)到設(shè)置的最大迭代次數(shù)作為終止條件，求得使總延誤時(shí)間和管制員工作負(fù)荷加權(quán)之和最小的序列集合，再?gòu)募现羞x取與實(shí)際運(yùn)行情況下差異最小的序列作為最佳進(jìn)離場(chǎng)序列。

4 實(shí)例驗(yàn)證與結(jié)果分析

選取天津?yàn)I海國(guó)際機(jī)場(chǎng)2018年12月1日16跑道13:00-14:00 的數(shù)據(jù)作為實(shí)驗(yàn)樣本，如表1 所示，包括14 架進(jìn)場(chǎng)航班和14 架離場(chǎng)航班；機(jī)場(chǎng)航線沖突點(diǎn)和基礎(chǔ)數(shù)據(jù)如圖3所示，東側(cè)主要以進(jìn)場(chǎng)航班與離場(chǎng)航班沖突為主，西側(cè)主要以進(jìn)場(chǎng)航班與進(jìn)場(chǎng)航班沖突為主，對(duì)于兩架使用同一離場(chǎng)航線的航班，這里將兩者之間的最小安全間隔時(shí)間擴(kuò)展到5 min；航班的機(jī)型大多為中型機(jī)，僅包含少量重型機(jī)，無輕型機(jī)，因此本部分僅考慮重型機(jī)與中型機(jī)之間的最小間隔標(biāo)準(zhǔn)，將距離標(biāo)準(zhǔn)轉(zhuǎn)化為時(shí)間標(biāo)準(zhǔn)，結(jié)果如表2所示。

表1 進(jìn)離場(chǎng)航班樣本數(shù)據(jù)Table 1 Arrival and departure aircraft sample data

表2 航班最小時(shí)間間隔標(biāo)準(zhǔn)Table 2 Minimum time separation standard for aircraft (s)

除表1中可直接獲得的數(shù)據(jù)外，本文還需要計(jì)算得到進(jìn)離場(chǎng)航班的最早著陸、起飛時(shí)間，最晚著陸、起飛時(shí)間。結(jié)合進(jìn)離場(chǎng)航班的航線信息，各機(jī)型速度信息(表3)等，計(jì)算得到表4所示的結(jié)果。

表3 各機(jī)型速度參數(shù)設(shè)置Table 3 Speed parameter settings for each aircraft

表4 相關(guān)數(shù)據(jù)計(jì)算結(jié)果Table 4 Relevant data calculation results

基于以上數(shù)據(jù)，采用遺傳算法進(jìn)行求解，種群規(guī)模設(shè)置為20，交叉率0.9，變異率0.1，代溝0.9，最大迭代次數(shù)200，最大位置偏移量3，Δt=5 s，對(duì)上述28架進(jìn)離場(chǎng)航班進(jìn)行計(jì)算。在先到先服務(wù)策略和實(shí)際運(yùn)行情況下，計(jì)算結(jié)果如表5所示。

表5 先到先服務(wù)結(jié)果和實(shí)際運(yùn)行結(jié)果Table 5 First-come-first-served results and actual operation results (s)

通過設(shè)置不同數(shù)據(jù)組合尋找對(duì)優(yōu)化延誤時(shí)間和管制負(fù)荷均有利的權(quán)重組合，結(jié)果如表6所示。

表6 不同權(quán)重的計(jì)算結(jié)果Table 6 Calculation results of different weights

由表6可知，當(dāng)不斷提高目標(biāo)函數(shù)2的權(quán)重時(shí)，雖然航班延誤的優(yōu)化比例有所降低，但管制負(fù)荷優(yōu)化的比例卻快速提高。

為進(jìn)一步觀察兩目標(biāo)函數(shù)間的關(guān)系，繪制目標(biāo)函數(shù)解的Pareto 最優(yōu)前沿，如圖4 所示。從圖中可得，延誤時(shí)間最小化與管制員工作負(fù)荷最小化之間存在一定的矛盾關(guān)系，在優(yōu)化求解時(shí)無法找到兩者同時(shí)達(dá)到最優(yōu)的排序結(jié)果，為此需要通過設(shè)置權(quán)重來選擇符合期望的排序結(jié)果。

圖4 帕累托最優(yōu)前沿Fig.4 Pareto optimal front

在繁忙的終端區(qū)內(nèi)，對(duì)于降低航班延誤時(shí)間和減少管制員負(fù)荷兩者同樣重要，希望獲得既可以有效減少航班延誤時(shí)間，同時(shí)又可以減輕管制員工作負(fù)荷的排序結(jié)果。選擇0.2-0.8 的權(quán)重組合作為目標(biāo)函數(shù)的權(quán)重值，結(jié)果如表7所示。

5 結(jié)論

本文的主要結(jié)論如下：

(1)所建立的進(jìn)離場(chǎng)航班協(xié)同排序多目標(biāo)時(shí)間索引模型，為進(jìn)離場(chǎng)航班分配起飛和著陸時(shí)隙，將每架航班的起飛、著陸可執(zhí)行時(shí)間擴(kuò)展到一段時(shí)間內(nèi)，而非一個(gè)時(shí)間點(diǎn)上，在提高終端區(qū)運(yùn)行效率和安全的同時(shí)，可獲得魯棒性更高的航班序列。

(2)通過分析序列中航班的潛在沖突情況，利用潛在沖突時(shí)間長(zhǎng)度表征管制員工作負(fù)荷增加，在模型優(yōu)化求解后，由排序中潛在沖突引起的管制員負(fù)荷增加可得到有效減少。

(3)通過為目標(biāo)函數(shù)設(shè)置不同的權(quán)重組合，可得當(dāng)目標(biāo)函數(shù)2 的權(quán)重在0.7 以下時(shí)，管制員工作負(fù)荷的優(yōu)化率較低；當(dāng)權(quán)重大于等于0.8時(shí)，管制員工作負(fù)荷得到明顯減少，優(yōu)化程度大大提高。