江灝 劉繼新 董欣放

(1. 南京航空航天大學(xué) 民航學(xué)院, 南京 211106; 2. 國(guó)家空管飛行流量管理技術(shù)重點(diǎn)實(shí)驗(yàn)室, 南京 211106)

空中交通需求的持續(xù)增長(zhǎng)與可用空域和機(jī)場(chǎng)資源的長(zhǎng)期受限,給空中交通管理帶來(lái)了新的機(jī)遇與挑戰(zhàn)。 目前,民航部門投入了大量的人力與物力在繁忙機(jī)場(chǎng)新建跑道、更新管制運(yùn)行設(shè)備。但單純依靠該方法來(lái)提高機(jī)場(chǎng)和終端區(qū)運(yùn)行容量會(huì)受到多種因素(如時(shí)間、資金)的制約,已不能作為當(dāng)前提高交通流量的有效措施。 因此,如何有效地優(yōu)化和調(diào)度時(shí)空資源,最大化地發(fā)揮現(xiàn)有機(jī)場(chǎng)基礎(chǔ)設(shè)施的潛能,成為空中交通管理領(lǐng)域的研究熱點(diǎn),而在跑道系統(tǒng)中對(duì)航班進(jìn)行進(jìn)離場(chǎng)排序優(yōu)化是該領(lǐng)域的典型問(wèn)題。

離場(chǎng)航班排序和進(jìn)場(chǎng)航班排序在性質(zhì)上相似,其區(qū)別于進(jìn)場(chǎng)航班排序之處在于目標(biāo)函數(shù)、間隔要求及求解算法方面[1]。 在目標(biāo)函數(shù)方面,由于離場(chǎng)航班起飛前的整個(gè)離場(chǎng)運(yùn)行過(guò)程發(fā)生在機(jī)場(chǎng)范圍內(nèi),相較于進(jìn)場(chǎng)航班排序,需要更多考慮機(jī)場(chǎng)方的訴求。 在間隔要求方面,最為不同的是離場(chǎng)航班會(huì)受到航路放行間隔的約束,這使得對(duì)于進(jìn)場(chǎng)航班排序問(wèn)題很容易滿足的三角不等式(對(duì)于航班序列中的任意3 個(gè)航班l(xiāng)、m和k,以Slm、Smk和Slk分別代表航班對(duì)lm、mk和lk之間須滿足的間隔要求,則三角不等式可表示為Slm+Smk≥Slk),對(duì)離場(chǎng)航班排序問(wèn)題并不總是能夠成立。因?yàn)樵谶M(jìn)場(chǎng)著陸的航班對(duì)中,后機(jī)僅受到與其相鄰前機(jī)的尾流間隔、水平間隔和進(jìn)近-塔臺(tái)移交的協(xié)議間隔[2],而離場(chǎng)航班的航路放行間隔并不僅與其相鄰前機(jī)相關(guān),還須檢查所有先前離場(chǎng)的航班。 求解算法方面,動(dòng)態(tài)規(guī)劃算法能夠求解航班排序問(wèn)題必須滿足的先決條件是:航班對(duì)之間的間隔滿足三角不等式約束,且若離場(chǎng)排序問(wèn)題中航班之間的間隔不滿足三角不等式,問(wèn)題的復(fù)雜度會(huì)大幅增加[3-4]。 因此,被廣泛應(yīng)用于求解進(jìn)場(chǎng)航班排序問(wèn)題的動(dòng)態(tài)規(guī)劃算法,在用于求解離場(chǎng)航班排序問(wèn)題時(shí)必須假定離場(chǎng)航班對(duì)之間的間隔滿足三角不等式[5-8]。 Gupta[9]、Su[10]和Liu[11]等建立了離場(chǎng)航班排序問(wèn)題的混合整數(shù)線性規(guī)劃模型;分支定界法[12-13]、元啟發(fā)式算法[3-4]等也被用于解決離場(chǎng)航班排序問(wèn)題。

近年來(lái),航空運(yùn)輸業(yè)呈現(xiàn)多方協(xié)同決策的發(fā)展趨勢(shì),離場(chǎng)航班本身作為空管、航司和機(jī)場(chǎng)等多方單位基于各自利益的決策載體,各方秉持不同的訴求。 空管立足運(yùn)行安全和降低管制負(fù)荷,航司著眼運(yùn)行效率和公平性,機(jī)場(chǎng)注重容量提高和放行正常,離場(chǎng)排序的研究重點(diǎn)也由單目標(biāo)優(yōu)化逐步轉(zhuǎn)向多目標(biāo)優(yōu)化。 Montoya 等[8]、尹嘉男等[14]、Zhang 和Hu[15]、Zhong 等[16]同時(shí)考慮多個(gè)目標(biāo),對(duì)離場(chǎng)航班排序問(wèn)題進(jìn)行多目標(biāo)優(yōu)化。 上述多目標(biāo)優(yōu)化相關(guān)研究豐富了離場(chǎng)航班排序問(wèn)題的內(nèi)涵,但仍存在2 方面問(wèn)題亟待解決:①如何充分考慮空管、航司和機(jī)場(chǎng)的訴求,在對(duì)離場(chǎng)航班排序時(shí)兼顧各方利益并滿足公平性的要求;②如何根據(jù)不同時(shí)段機(jī)場(chǎng)交通狀態(tài)的差別調(diào)整資源,選擇合理的優(yōu)化目標(biāo)與排序方案。

本文立足于民航運(yùn)輸業(yè)多方協(xié)同決策的發(fā)展趨勢(shì),以擁有單條起飛跑道的機(jī)場(chǎng)為對(duì)象,重點(diǎn)研究機(jī)場(chǎng)擁擠與非擁擠場(chǎng)景下離場(chǎng)航班動(dòng)態(tài)協(xié)同排序問(wèn)題。 研究工作著眼于離場(chǎng)航班排序的動(dòng)態(tài)性、協(xié)同性和定制化。 在滿足離場(chǎng)航班排序的動(dòng)態(tài)性方面,基于離場(chǎng)航班的計(jì)劃撤輪檔時(shí)間(scheduled off-block time, SOBT)和預(yù)計(jì)撤輪檔時(shí)間(estimated off-block time, EOBT)數(shù)據(jù),設(shè)計(jì)一種離場(chǎng)航班動(dòng)態(tài)排序方法;協(xié)同性是指在對(duì)離場(chǎng)航班排序時(shí),充分考慮空管、航司和機(jī)場(chǎng)的訴求;通過(guò)分析擁擠場(chǎng)景與非擁擠場(chǎng)景下各方訴求的差異,定制化地選擇目標(biāo)函數(shù)和約束,建立離場(chǎng)航班排序模型。

1 離場(chǎng)航班動(dòng)態(tài)排序方法

在離場(chǎng)航班的SOBT 前150 min,航空公司或航務(wù)代理單位會(huì)通過(guò)領(lǐng)航計(jì)劃報(bào)提交該航班的EOBT。 本文利用EOBT 數(shù)據(jù)自身具有的動(dòng)態(tài)特性,設(shè)計(jì)一種離場(chǎng)航班動(dòng)態(tài)排序方法,以滿足離場(chǎng)航班排序的動(dòng)態(tài)性要求。 參考滾動(dòng)時(shí)域控制[17](receding horizon control,RHC)中時(shí)間窗參數(shù)的設(shè)置,確定排序時(shí)段時(shí)長(zhǎng)為15 min。

圖1 為離場(chǎng)航班動(dòng)態(tài)排序方法流程,各步驟的詳細(xì)描述如下。

圖1 離場(chǎng)航班動(dòng)態(tài)排序方法流程Fig.1 Flowchart of departure flight dynamic sequencing method

步驟1 選定離場(chǎng)航班動(dòng)態(tài)排序的時(shí)間區(qū)間[Ts,Te],初始化SOBT 在[Ts,Te]之內(nèi)的原始航班列表L0(按照SOBT 從小到大排序),初始化離場(chǎng)航班排序時(shí)段索引i=1,初始化待排序航班列表L1為空。

步驟2 實(shí)時(shí)接收EOBT 數(shù)據(jù),將其所對(duì)應(yīng)的離場(chǎng)航班按照EOBT 由小到大的順序插入L1相應(yīng)位置。

步驟3 取L0中第1 個(gè)位置離場(chǎng)航班的SOBT 記為t0,取L1中第1 個(gè)位置離場(chǎng)航班的EOBT 記為t1,令t*= min{t0,t1}。若t*∈[Ts,Te], 則繼續(xù)步驟4,否則結(jié)束流程。

步驟4t*前150 min 開(kāi)始計(jì)時(shí),計(jì)時(shí)時(shí)長(zhǎng)15 min。 計(jì)時(shí)結(jié)束時(shí)初始化排序時(shí)段i待排序航班列表Li,將L1中EOBT 處于[t*,t*+15]的離場(chǎng)航班加入Li中,并將其從L0和L1中剔除。 觸發(fā)排序,輸出Li作為對(duì)當(dāng)前時(shí)段i離場(chǎng)航班排序的初始輸入信息。

步驟5 排序時(shí)段索引i加1,返回步驟3。

2 模型建立

在協(xié)同決策理念下對(duì)離場(chǎng)航班排序時(shí),希望同時(shí)考慮到空管、航司和機(jī)場(chǎng)的訴求,因此針對(duì)各方構(gòu)建了離場(chǎng)航班排序的多個(gè)優(yōu)化目標(biāo),并且為保證排序公平性,提出了航空公司延誤公平性評(píng)價(jià)指標(biāo)。 通過(guò)分析機(jī)場(chǎng)交通狀態(tài)擁擠與非擁擠場(chǎng)景下運(yùn)行特性和各方訴求的差異,確定2 種場(chǎng)景下不同的目標(biāo)函數(shù)和約束,提出一種基于交通狀態(tài)的離場(chǎng)航班協(xié)同排序模型,從而實(shí)現(xiàn)各方利益的協(xié)同和不同場(chǎng)景下的定制化排序。

本節(jié)闡述對(duì)第1 節(jié)離場(chǎng)航班動(dòng)態(tài)排序方法輸出的時(shí)段i待排序航班列表Li,進(jìn)行優(yōu)化排序的模型建立過(guò)程。

2.1 航空公司延誤公平性

在一組參與者之間分享有限資源或利益的系統(tǒng)背景下,公平得到了廣泛的研究[18]。 航班排序問(wèn)題中,參與者為各待排序航班,有限資源為跑道時(shí)隙資源。 航班次序約束位置交換[19]的應(yīng)用使得跑道系統(tǒng)在提升運(yùn)行效率的同時(shí),航班間的相對(duì)公平得到保障。 近年來(lái),針對(duì)航班排序問(wèn)題中航班延誤公平性的研究已取得了一定的成果[2,15,20]。

而對(duì)于單機(jī)場(chǎng)航班排序問(wèn)題而言,空管、航司和機(jī)場(chǎng)三方中的航司方也存在多個(gè)決策主體,即多個(gè)不同航司。 文獻(xiàn)[16]通過(guò)最小化各航班流方向航班平均延誤的差別,實(shí)現(xiàn)保證各航班流方向之間延誤公平性的目標(biāo),借鑒此思路,本文基于各航空公司航班平均延誤的差別建立航空公司延誤公平性評(píng)價(jià)指標(biāo)。

在計(jì)算離場(chǎng)航班延誤時(shí)將離場(chǎng)航班按照是否受到流控影響分為非受控離場(chǎng)航班和受控離場(chǎng)航班。 為實(shí)現(xiàn)準(zhǔn)點(diǎn)保障的目標(biāo),在計(jì)算航班延誤時(shí)將航班提前起飛也當(dāng)作延誤處理。 因此在計(jì)算非受控離場(chǎng)航班延誤時(shí),其等于優(yōu)化起飛時(shí)間與計(jì)

而對(duì)于受控航班,全國(guó)流量管理系統(tǒng)會(huì)以航班計(jì)劃為基礎(chǔ),依據(jù)流量管理措施并按照相關(guān)規(guī)則發(fā)布其計(jì)算起飛時(shí)間(calculated take off time,CTOT)。 受控航班須在其CTOT 前后一定容差范圍內(nèi)起飛,CTOT 時(shí)隙容差分為一類容差和二類容差。 根據(jù)《中國(guó)民航空管流量管理運(yùn)行程序》,基于容量管理的流量管理措施為一類容差,容差范圍為( -5, +10) min;基于間隔管理的流量管理措施為二類容差,容差范圍為( -3, +3) min。為盡可能保障受控航班按照其CTOT 準(zhǔn)點(diǎn)起飛,在計(jì)算受控離場(chǎng)航班延誤時(shí),令其等于優(yōu)化起飛時(shí)間與CTOT 差值的絕對(duì)值。

各航司離場(chǎng)航班平均延誤的差別越小,航空公司間的延誤公平性越高。 因此,在計(jì)算航空公司延誤公平性評(píng)價(jià)指標(biāo)時(shí),對(duì)各航司離場(chǎng)航班平均延誤的差別進(jìn)行“取倒數(shù)”的處理,從而使各航司離場(chǎng)航班平均延誤的差別與航空公司間延誤公平性的內(nèi)涵表征保持一致性。 另外,由于各航司離場(chǎng)航班平均延誤的差別存在取值為零的可能,為保證分母的有效性和將航空公司延誤公平性評(píng)價(jià)指標(biāo)限定在(0,1]范圍之內(nèi),需以各航司離場(chǎng)航班平均延誤的差別取值加上常數(shù)1 作為分母。

基于以上分析,本文將航空公司延誤公平性評(píng)價(jià)指標(biāo)定義為

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

本文根據(jù)空管、航司和機(jī)場(chǎng)三方的訴求,建立了三方共同關(guān)注的2 個(gè)目標(biāo)函數(shù),并針對(duì)各方訴求分別設(shè)計(jì)了一個(gè)目標(biāo)函數(shù)。 其中,最小化離場(chǎng)航班總延誤和最大化航空公司延誤公平性2 個(gè)目標(biāo)函數(shù)同時(shí)涉及非受控航班和受控航班。 一般情況下,若某排序時(shí)段存在受控航班,該排序時(shí)段最后一個(gè)離場(chǎng)航班通常為受控航班,其起飛次序較計(jì)劃起飛次序也會(huì)相應(yīng)地存在較大偏差,并且其優(yōu)化空間有限,因此對(duì)于最小化離場(chǎng)航班次序調(diào)整和最大化跑道容量2 個(gè)目標(biāo),僅考慮非受控航班。 根據(jù)《民航航班正常統(tǒng)計(jì)辦法》中放行正常航班判定標(biāo)準(zhǔn),受控航班基本不會(huì)被判定為放行正常,故對(duì)于最大化機(jī)場(chǎng)放行正常率目標(biāo),亦不將受控航班納入統(tǒng)計(jì)。

1) 綜合指標(biāo):最小化離場(chǎng)航班總延誤

航班延誤時(shí)間是反映航班延誤程度的指標(biāo),航班延誤對(duì)空管社會(huì)形象、機(jī)場(chǎng)運(yùn)行效率和航空公司成本效益等均造成了嚴(yán)重影響。 某排序時(shí)段離場(chǎng)航班總延誤最小,即

2) 綜合指標(biāo):最小化離場(chǎng)航班次序調(diào)整

離場(chǎng)航班優(yōu)化起飛次序若與計(jì)劃起飛次序存在偏差,機(jī)組會(huì)和管制員進(jìn)行額外的通話,這將增加管制負(fù)荷;機(jī)場(chǎng)和航司會(huì)根據(jù)離場(chǎng)航班的離場(chǎng)順序安排航班保障的先后次序,為保證機(jī)場(chǎng)和航司對(duì)于離場(chǎng)航班保障服務(wù)的平穩(wěn)、有序和高效運(yùn)行,優(yōu)化起飛次序較計(jì)劃起飛次序的偏離程度應(yīng)

4) 航司:最大化航空公司延誤公平性

由2.1 節(jié)可知,航空公司延誤公平性評(píng)價(jià)指標(biāo)值的大小可直接反映航空公司間的公平性高低。某排序時(shí)段內(nèi)的航空公司延誤公平性最高,即

2.3 約束條件

離場(chǎng)航班受到的約束主要有管制間隔要求、時(shí)間窗約束和最大約束位置轉(zhuǎn)換(maximum position shift, MPS)約束。

2.3.1 管制間隔要求

空管的安全運(yùn)行目標(biāo)通過(guò)滿足管制間隔要求實(shí)現(xiàn)。 離場(chǎng)航班起飛受到的水平間隔約束有非雷達(dá)間隔的尾流間隔、跑道運(yùn)行間隔和放行間隔。

1) 非雷達(dá)間隔的尾流間隔

2.3.2 時(shí)間窗約束

由于非受控離場(chǎng)航班和受控離場(chǎng)航班時(shí)間窗上下界的確定方式存在差異,本文將時(shí)間窗約束分為非受控離場(chǎng)航班時(shí)間窗約束和受控離場(chǎng)航班時(shí)間窗約束。

1) 非受控離場(chǎng)航班時(shí)間窗約束

管制運(yùn)行過(guò)程中,管制員會(huì)根據(jù)不同類型離場(chǎng)航班的重要度,在離場(chǎng)排序時(shí)考慮其優(yōu)先級(jí)。在文獻(xiàn)[2,16]的基礎(chǔ)上,本文將非受控離場(chǎng)航班優(yōu)先級(jí)分為最高等級(jí)、次高等級(jí)和最低等級(jí)3 類,并建立具有各類優(yōu)先級(jí)的非受控離場(chǎng)航班和其可接受的最大延誤時(shí)間之間的關(guān)系。 最高等級(jí)的航班重要度最高,常為專機(jī)或需要立即起飛離場(chǎng)的航班;次高等級(jí)的航班常為國(guó)際航班和國(guó)內(nèi)重要航班;最低等級(jí)的航班為一般國(guó)內(nèi)普通航班。

因此,非受控離場(chǎng)航班優(yōu)化起飛時(shí)間應(yīng)當(dāng)不早于航司提交的該航班EOBT 與其滑行到達(dá)離場(chǎng)跑道的最短滑行時(shí)間之和,不晚于計(jì)劃起飛時(shí)間

2.3.3 MPS 約束

2.4 基于交通狀態(tài)的離場(chǎng)航班協(xié)同排序模型

根據(jù)待排序時(shí)段機(jī)場(chǎng)交通擁擠程度的不同,選擇相應(yīng)的目標(biāo)函數(shù)和約束對(duì)離場(chǎng)航班進(jìn)行優(yōu)化排序。 由于本文離場(chǎng)航班排序中的空中交通擁擠識(shí)別問(wèn)題發(fā)生于起飛前2 ～3 h,屬于短期實(shí)時(shí)交通管理問(wèn)題,根據(jù)文獻(xiàn)[21],宜采用基于短期數(shù)據(jù)的閾值判別方法。 基于閾值判別的擁擠識(shí)別方法,是將交通容量C(即MAP 值)作為閾值,再將交通需求與該閾值進(jìn)行比較,如果需求大于容量,則判定交通狀態(tài)為擁擠,否則判定交通狀態(tài)為非擁擠。

通過(guò)以上分析,建立基于交通狀態(tài)的離場(chǎng)航班協(xié)同排序模型如下:

3 算法設(shè)計(jì)

航班排序問(wèn)題屬于典型的NP-hard[22],而遺傳算法作為一種經(jīng)典的元啟發(fā)式算法,其并不需要事先描述問(wèn)題的全部特點(diǎn)及確定算法應(yīng)采取的措施,特別適合處理此類問(wèn)題。 因此,采用NSGA-Ⅱ[23]求解2.4 節(jié)建立的非線性多目標(biāo)優(yōu)化模型。

3.1 算法流程

對(duì)第1 節(jié)離場(chǎng)航班動(dòng)態(tài)排序方法輸出的時(shí)段i待排序航班列表Li進(jìn)行排序計(jì)算的算法流程如圖2 所示。

圖2 算法流程Fig.2 Flowchart of algorithm

步驟2 根據(jù)2.4 節(jié)的判別方法判定當(dāng)前排序時(shí)段的交通狀態(tài),確定當(dāng)前排序時(shí)段對(duì)離場(chǎng)航班排序的目標(biāo)函數(shù);根據(jù)式(16)和式(17)確定所有離場(chǎng)航班的起飛時(shí)間窗,以起飛時(shí)間窗作為決策變量的上下界,隨機(jī)生成初始種群。

步驟3 解碼,得到各航班的離場(chǎng)時(shí)間和離場(chǎng)次序。

步驟4 約束符合性檢驗(yàn)。 根據(jù)式(13) ～式(15)判斷種群各個(gè)體初始離場(chǎng)時(shí)間是否滿足間隔要求(若當(dāng)前排序時(shí)段的交通狀態(tài)為非擁擠,還須根據(jù)式(18)判斷初始離場(chǎng)次序是否滿足MPS 約束),若滿足,根據(jù)步驟2 確定的目標(biāo)函數(shù)計(jì)算個(gè)體的各個(gè)目標(biāo)函數(shù)值;若不滿足,設(shè)置個(gè)體的目標(biāo)函數(shù)值為(M,M,0),其中M為一任意大的正數(shù)。

步驟5 執(zhí)行快速非支配排序并計(jì)算擁擠距離,基于此進(jìn)行各種遺傳算子操作,得到子代種群;父/子代種群合并,執(zhí)行快速非支配排序,將處于臨界層之前的個(gè)體直接保留到下一代,對(duì)處于臨界層的個(gè)體根據(jù)擁擠距離從大到小的順序選擇若干個(gè)個(gè)體保留到下一代,直至新一代種群的個(gè)體數(shù)目等于父代種群的個(gè)體數(shù)目。

步驟6 若達(dá)到最大進(jìn)化代數(shù),則當(dāng)前時(shí)段算法運(yùn)行結(jié)束,輸出算法運(yùn)行結(jié)果:當(dāng)前種群的Pareto 最優(yōu)解中各航班的離場(chǎng)時(shí)間和離場(chǎng)次序;若否,進(jìn)化代數(shù)加1,轉(zhuǎn)至步驟3。

3.2 算法實(shí)現(xiàn)

1) 非受控航班時(shí)間窗約束與MPS 約束處理

考慮到機(jī)場(chǎng)和航司雙方的訴求,將機(jī)場(chǎng)基地航空公司的非受控離場(chǎng)航班優(yōu)先級(jí)設(shè)置為次高等級(jí)。

2.3.2 節(jié)中確定非受控離場(chǎng)航班時(shí)間窗約束時(shí),將離場(chǎng)航班優(yōu)先級(jí)與可接受的最大延誤時(shí)間聯(lián)系起來(lái)。 根據(jù)文獻(xiàn)[14,16],將最低等級(jí)離場(chǎng)航班可接受的最大延誤時(shí)間設(shè)定為40 min;將次高等級(jí)離場(chǎng)航班可接受的最大延誤時(shí)間設(shè)定為最低等級(jí)的一半,即20 min;由于優(yōu)先級(jí)為最高等級(jí)的離場(chǎng)航班重要度很高,參照同樣具有高重要度的受控航班,將其可接受的最大延誤時(shí)間設(shè)定為受控航班一類容差的上界10 min;因此,非受控離場(chǎng)航班可接受的最大延誤時(shí)間集合。

2.3.3 節(jié)中確定非受控離場(chǎng)航班MPS 約束時(shí),建立了離場(chǎng)航班優(yōu)先級(jí)與最大位置偏移量之間的聯(lián)系。 設(shè)置非受控航班最大位置偏移量集合為ε={1,2,3}。

2) 編碼與解碼

在進(jìn)行模型求解時(shí)將以時(shí)分形式表示的時(shí)間均轉(zhuǎn)換成用秒表示,即將ahbmin 轉(zhuǎn)換成s 的轉(zhuǎn)換公式為:a×3 600 +b×60。 根據(jù)2.3.2 節(jié)確定的離場(chǎng)航班時(shí)間窗,采用整數(shù)編碼的方式對(duì)離場(chǎng)航班的優(yōu)化起飛時(shí)間進(jìn)行編碼。

3) 遺傳算子

算法中存在2 個(gè)階段的選擇:①采用二元錦標(biāo)賽選擇;②采用基于非支配分層及擁擠距離度量的選擇方法,詳見(jiàn)文獻(xiàn)[23]。 交叉算子為模擬二進(jìn)制交叉;變異算子為多項(xiàng)式變異。 由于采用整數(shù)編碼,在使用多項(xiàng)式變異時(shí)先按實(shí)數(shù)值進(jìn)行突變,再四舍五入進(jìn)行取整。

3.3 算法性能評(píng)價(jià)指標(biāo)

從算法運(yùn)行過(guò)程中各代Pareto 最優(yōu)解的收斂性和多樣性2 個(gè)角度出發(fā),選取2 個(gè)多目標(biāo)優(yōu)化常用的算法性能指標(biāo)[24]評(píng)價(jià)多目標(biāo)離場(chǎng)排序優(yōu)化解集的優(yōu)劣。

1) 世代距離

世代距離(generational distance, GD)是用于評(píng)價(jià)多目標(biāo)算法收斂性的指標(biāo),其值越小說(shuō)明算法的收斂性越好。 GD 的計(jì)算式為

式中:w為算法計(jì)算得到的Pareto 前沿中解的個(gè)數(shù);p為目標(biāo)維數(shù);du為算法計(jì)算得到的Pareto 前沿中每個(gè)解距離真實(shí)Pareto 前沿的最近歐氏距離。

2) 反轉(zhuǎn)世代距離

反轉(zhuǎn)世代距離(inverted generational distance,IGD)值不僅能反映多目標(biāo)算法收斂性,還能反映解的多樣性,其值越小則算法的性能越好。 IGD的計(jì)算式為

式中:q為真實(shí)Pareto 前沿中解的個(gè)數(shù);dr為真實(shí)Pareto 前沿中每個(gè)解距離算法計(jì)算得到的Pareto前沿的最近歐氏距離。

4 實(shí)例驗(yàn)證

4.1 實(shí)驗(yàn)設(shè)計(jì)

以南京祿口國(guó)際機(jī)場(chǎng)隔離平行運(yùn)行模式下的離場(chǎng)運(yùn)行為例,對(duì)離場(chǎng)航班進(jìn)行動(dòng)態(tài)協(xié)同排序。機(jī)場(chǎng)的基地航空公司有5 家,分別為:東方航空、深圳航空、吉祥航空、首都航空和郵政航空。 機(jī)場(chǎng)的離場(chǎng)點(diǎn)共4 個(gè),分別為:OF、HFE、TESIG 和ESBAG。 研究時(shí)段內(nèi)離場(chǎng)航班機(jī)型共2 種,分別為重型機(jī)和中型機(jī),無(wú)A380-800 型機(jī)和輕型機(jī)。

3.3 節(jié)GD 和IGD 的計(jì)算需要以真實(shí)Pareto前沿作為參考,而對(duì)于實(shí)際問(wèn)題,很難獲得真實(shí)Pareto 前沿。 通過(guò)進(jìn)行多次獨(dú)立實(shí)驗(yàn),將各次獨(dú)立實(shí)驗(yàn)獲得的Pareto 解集合并為一個(gè)集合,在此集合中尋找非支配解,近似替代真實(shí)Pareto 前沿。進(jìn)行獨(dú)立實(shí)驗(yàn)的次數(shù)為50 次,獨(dú)立實(shí)驗(yàn)時(shí)設(shè)置算法的種群規(guī)模為200,最大進(jìn)化代數(shù)為300。

4.2 結(jié)果分析

將基于先到先服務(wù)(FCFS)策略的排序方法(以下簡(jiǎn)稱先到先服務(wù)方法)與本文所提的基于交通狀態(tài)的離場(chǎng)航班動(dòng)態(tài)協(xié)同排序方法(以下簡(jiǎn)稱動(dòng)態(tài)協(xié)同方法)進(jìn)行對(duì)比,以評(píng)估本文方法的優(yōu)化效果。 選擇某典型日7:00—11:00(區(qū)間1)和14:00—18:00(區(qū)間2)2 個(gè)時(shí)間區(qū)間,共對(duì)162 架次(區(qū)間1(2):83(79)架次)離場(chǎng)航班進(jìn)行排序。

在區(qū)間1(區(qū)間2)內(nèi),動(dòng)態(tài)協(xié)同方法共包括12 個(gè)(12 個(gè))排序時(shí)段:擁擠時(shí)段3 個(gè)(2 個(gè)),非擁擠時(shí)段9 個(gè)(10 個(gè))。 仿真結(jié)果表明,擁擠場(chǎng)景和非擁擠場(chǎng)景下各時(shí)段算法運(yùn)行時(shí)間均小于5 s,且隨著遺傳算法進(jìn)化代數(shù)的增加,2 種場(chǎng)景下種群中的個(gè)體均朝著最優(yōu)化方向進(jìn)化,故其能快速獲得最優(yōu)解。 較先到先服務(wù)方法,對(duì)區(qū)間1(區(qū)間2)而言:擁擠場(chǎng)景下,各排序時(shí)段平均增加4 種(4 種)排序方案,離場(chǎng)航班總延誤平均減少73%(71%);非擁擠場(chǎng)景下,各排序時(shí)段平均增加6 種(7 種)排序方案,離場(chǎng)航班總延誤平均減少51%(53%),離場(chǎng)航班總次序調(diào)整平均減少4 次(5 次),航空公司公平性平均提高3 倍(3 倍)。

以下在擁擠場(chǎng)景和非擁擠場(chǎng)景下各選擇1 個(gè)時(shí)段,對(duì)使用先到先服務(wù)方法和基于交通狀態(tài)的離場(chǎng)航班協(xié)同排序模型(以下簡(jiǎn)稱優(yōu)化模型)的排序結(jié)果作詳細(xì)的對(duì)比討論。

1) 擁擠場(chǎng)景

圖3 為區(qū)間1 第4 個(gè)排序時(shí)段(11 架次離場(chǎng)航班)的離場(chǎng)航班總延誤時(shí)間、起飛時(shí)間間隔和機(jī)場(chǎng)放行正常率在種群進(jìn)化完成時(shí)所得的26 個(gè)Pareto 最優(yōu)解。

圖3 Pareto 最優(yōu)解(時(shí)段1-4)Fig.3 Pareto optimal solution (time interval 1-4)

圖4 為區(qū)間1 第4 個(gè)排序時(shí)段在不同進(jìn)化代數(shù)對(duì)應(yīng)的Pareto 最優(yōu)解集的GD 和IGD 數(shù)值變化趨勢(shì)。 可以看出,隨著種群的不斷進(jìn)化,GD 和IGD 數(shù)值變化趨勢(shì)一致,均朝著優(yōu)化的方向變化,100 代后GD 和IGD 數(shù)值趨于穩(wěn)定。

圖4 種群進(jìn)化過(guò)程中GD 和IGD 值變化趨勢(shì)(時(shí)段1-4)Fig.4 Trend of GD and IGD value in process of population evolution (time interval 1-4)

擁擠場(chǎng)景下的第3 個(gè)目標(biāo)函數(shù)為最大化機(jī)場(chǎng)放行正常率,該目標(biāo)取值為離散值,可能取值的數(shù)目等于當(dāng)前時(shí)段待排序離場(chǎng)航班中的非受控航班數(shù)加1。 為便于三目標(biāo)Pareto 最優(yōu)解的直觀展示和對(duì)比分析,對(duì)擁擠場(chǎng)景下求得的Pareto 最優(yōu)解按照機(jī)場(chǎng)放行正常率取值的不同,繪制各正常率取值下的其他2 個(gè)目標(biāo)函數(shù)取值情況圖,并將基于先到先服務(wù)方法結(jié)果的目標(biāo)函數(shù)表現(xiàn)一并展示,如圖5 所示。

由圖5 所示,基于先到先服務(wù)方法的結(jié)果不被基于優(yōu)化模型的Pareto 最優(yōu)解所支配,同時(shí)也不支配基于優(yōu)化模型的Pareto 最優(yōu)解。 其在起飛時(shí)間間隔與機(jī)場(chǎng)放行正常率上的表現(xiàn)較好;但其在離場(chǎng)航班總延誤時(shí)間上的表現(xiàn)極差:基于優(yōu)化模型的Pareto 最優(yōu)解中最大離場(chǎng)航班總延誤時(shí)間2 222 s,基于先到先服務(wù)方法的離場(chǎng)航班總延誤時(shí)間為8 760 s,約為2 222 s 的4 倍。 因此,基于先到先服務(wù)方法的結(jié)果因過(guò)多的延誤難以被接受。

圖5 Pareto 最優(yōu)解與先到先服務(wù)方法結(jié)果(時(shí)段1-4)Fig.5 Pareto optimal and FCFS solution (time interval 1-4)

圖6 為區(qū)間1 第4 個(gè)排序時(shí)段基于優(yōu)化模型的結(jié)果與基于先到先服務(wù)方法的結(jié)果中非受控航班起飛次序情況。 此時(shí)段中的2 個(gè)受控航班DKH1697 和CRK221 的CTOT 均較晚,且基于優(yōu)化模型的結(jié)果和基于先到先服務(wù)方法的結(jié)果中這2 個(gè)航班均按照CTOT 準(zhǔn)點(diǎn)保障,二者的起飛次序位于此時(shí)段的最后2 個(gè)次序(10 和11)。 由圖6可見(jiàn),基于優(yōu)化模型的結(jié)果提供了4 種離場(chǎng)排序方案,此4 種排序方案與基于先到先服務(wù)方法的起飛次序中,CES2893、CES2739 和CSN3578的起飛次序均為7、8 和9。 因此,基于優(yōu)化模型結(jié)果的起飛次序與基于先到先服務(wù)方法的起飛次序不同之處主要在于前6 個(gè)航班:CES2945、HDA863、CES579、CSZ9571、CES2795 和CBJ5279,其中HDA863 和CBJ5279 的次序差異較大,即優(yōu)化模型較先到先服務(wù)方法的優(yōu)化主要體現(xiàn)在對(duì)此6 個(gè)航班起飛次序的優(yōu)化。

空中交通管理人員可根據(jù)Pareto 最優(yōu)解的性能特點(diǎn),在離場(chǎng)航班總延誤、跑道容量和機(jī)場(chǎng)放行正常率之間進(jìn)行綜合權(quán)衡。 例如,對(duì)區(qū)間1 第4個(gè)排序時(shí)段,希望所選的排序策略航班總延誤時(shí)間在1 800 s 以下,起飛時(shí)間間隔在1 200 s 以下,機(jī)場(chǎng)放行正常率在0.8 以上,則從26 個(gè)Pareto 最優(yōu)解中篩選出5 個(gè)解,如圖7 所示。 此5 個(gè)解在各個(gè)目標(biāo)上的差異很小,離場(chǎng)航班總延誤最大差異為56 s,起飛時(shí)間間隔最大差異為23 s,機(jī)場(chǎng)放行正常率最大差異為0.11;此5 個(gè)解對(duì)應(yīng)2 種離場(chǎng)排序方案,分別為圖6 中的優(yōu)化模型結(jié)果1 和優(yōu)化模型結(jié)果3,注意到此2 種排序方案離場(chǎng)航班次序差異很小,僅為CES2945 與CBJ5279 的次序互換。 經(jīng)過(guò)篩選,Pareto 最優(yōu)解數(shù)目減少至個(gè)位數(shù),排序方案減少一半,更有利于管制運(yùn)行中的選擇。

圖6 不同策略下離場(chǎng)航班起飛次序(時(shí)段1-4)Fig.6 Sequences of departure flights using different strategies (time interval 1-4)

圖7 篩選后的Pareto 最優(yōu)解(時(shí)段1-4)Fig.7 Selected Pareto optimal solution (time interval 1-4)

2) 非擁擠場(chǎng)景

圖8 為區(qū)間2 第2 個(gè)排序時(shí)段(8 架次離場(chǎng)航班)的離場(chǎng)航班總延誤時(shí)間、離場(chǎng)航班總次序調(diào)整和航空公司延誤公平性在種群進(jìn)化完成時(shí)所得的95 個(gè)Pareto 最優(yōu)解。

圖8 Pareto 最優(yōu)解(時(shí)段2-2)Fig.8 Pareto optimal solution (time interval 1-4)

圖9 為區(qū)間2 第2 個(gè)排序時(shí)段在不同進(jìn)化代數(shù)對(duì)應(yīng)的Pareto 最優(yōu)解集的GD 和IGD 數(shù)值變化趨勢(shì)。 可以看出,隨著種群的不斷進(jìn)化,GD 和IGD 數(shù)值變化趨勢(shì)一致,均朝著優(yōu)化的方向變化,50 代后GD 和IGD 數(shù)值趨于穩(wěn)定。

圖9 種群進(jìn)化過(guò)程中GD 和IGD 值變化趨勢(shì)(時(shí)段2-2)Fig.9 Trend of GD and IGD value in process of population evolution (time interval 2-2)

與擁擠場(chǎng)景下機(jī)場(chǎng)放行正常率取值為離散值相同,非擁擠場(chǎng)景下的第2 個(gè)目標(biāo)函數(shù)離場(chǎng)航班總次序調(diào)整同樣為離散取值。 因此,在非擁擠場(chǎng)景下,仿照擁擠場(chǎng)景對(duì)于基于優(yōu)化模型的Pareto最優(yōu)解和基于先到先服務(wù)方法結(jié)果的三目標(biāo)函數(shù)值展現(xiàn)方式,如圖10 所示。

由圖10 所示,基于先到先服務(wù)方法的結(jié)果被基于優(yōu)化模型的Pareto 最優(yōu)解所支配。 相對(duì)于基于優(yōu)化模型的Pareto 最優(yōu)解,基于先到先服務(wù)方法的結(jié)果雖在各個(gè)目標(biāo)上的表現(xiàn)均較差:基于優(yōu)化模型的Pareto 最優(yōu)解中最大的離場(chǎng)航班總次序調(diào)整最大為2,而基于先到先服務(wù)方法結(jié)果的離場(chǎng)航班總次序調(diào)整為9,為2 的4.5 倍;基于優(yōu)化模型的Pareto 最優(yōu)解的離場(chǎng)航班總延誤時(shí)間最大為3 309 s,而基于先到先服務(wù)方法結(jié)果的離場(chǎng)航班總延誤時(shí)間為6 900 s,為3 309 s 的2 倍多;較基于優(yōu)化模型的Pareto 最優(yōu)解中最小的航空公司延誤公平性0.004 5,基于先到先服務(wù)方法結(jié)果的航空公司公平性為0.001 2 s,約為0.004 5 s 的1/4。 因此,基于先到先服務(wù)方法的結(jié)果因過(guò)多的次序調(diào)整、過(guò)多的延誤和過(guò)低的公平性難以被接受。

圖10 Pareto 最優(yōu)解與先到先服務(wù)方法結(jié)果(時(shí)段2-2)Fig.10 Pareto optimal and FCFS solution (time interval 2-2)

基于優(yōu)化模型的Pareto 最優(yōu)解共提供了7 種離場(chǎng)排序方案,基于先到先到先服務(wù)方法結(jié)果中非受控航班起飛次序情況、此7 種排序方案中的非受控航班起飛次序及其出現(xiàn)的頻次如圖11所示。

圖11 不同策略下離場(chǎng)航班起飛次序頻數(shù)(時(shí)段2-2)Fig.11 Sequence frequency of departure flights using different strategies (time interval 2-2)

此時(shí)段中的受控航班CSZ9864 的CTOT 較晚,基于優(yōu)化模型的結(jié)果和基于先到先服務(wù)方法的結(jié)果中此航班均按照CTOT 準(zhǔn)點(diǎn)保障,其起飛次序位于此時(shí)段的最后次序(次序8)。 此時(shí)段中,HDA811 的計(jì)劃起飛時(shí)間最早,但其預(yù)計(jì)起飛時(shí)間最晚,由圖11 所示,基于優(yōu)化模型結(jié)果的HDA811起飛次序均滿足MPS 約束,但基于先到先服務(wù)方法結(jié)果與計(jì)劃起飛次序偏差過(guò)大。 CES5001、CES2747 和CSZ9846 的計(jì)劃起飛時(shí)間相同,因此對(duì)于此3 個(gè)航班,其計(jì)劃起飛次序相等,即3 個(gè)航班的起飛次序?yàn)?、3 和4 中的任一次序,均為按照計(jì)劃起飛次序起飛。 CES2835 的計(jì)劃起飛次序?yàn)?;同樣對(duì)于CES2889 和OTC7111 擁有相同的計(jì)劃起飛時(shí)間,二者的計(jì)劃起飛次序?yàn)? 和7。結(jié)合以上分析和圖11 的結(jié)果,基于優(yōu)化模型的結(jié)果各航班最大起飛次序調(diào)整量為1,基于先到先服務(wù)方法的結(jié)果各航班最大起飛次序調(diào)整量為6,優(yōu)化模型在控制離場(chǎng)航班起飛次序偏移方面的效果顯著。

空中交通管理人員可根據(jù)Pareto 最優(yōu)解的性能特點(diǎn),在離場(chǎng)航班總延誤時(shí)間、離場(chǎng)航班總次序調(diào)整和航空公司延誤公平性之間進(jìn)行綜合權(quán)衡。例如,對(duì)區(qū)間2 第2 個(gè)排序時(shí)段,希望所選的排序策略航班總延誤時(shí)間在2 000 s 以下,航空公司平均延誤時(shí)間偏差在120 s 以下(即航空公司延誤公平性在0.008 3 以上),則從95 個(gè)Pareto 最優(yōu)解中篩選出28 個(gè)解,如圖12 所示。 此28 個(gè)解對(duì)應(yīng)2 種離場(chǎng)排序方案,分別為2-3-4-5-7-6-1 和4-2-3-6-5-7-1,經(jīng)過(guò)篩選,排序方案減少至2 個(gè),更有利于管制運(yùn)行中的選擇。

圖12 篩選后的Pareto 最優(yōu)解(時(shí)段2-2)Fig.12 Selected Pareto optimal solution (time interval 2-2)

5 結(jié) 論

1) 利用離場(chǎng)航班EOBT 數(shù)據(jù)自身具有的動(dòng)態(tài)特性,結(jié)合離場(chǎng)航班SOBT 數(shù)據(jù),設(shè)計(jì)了一種離場(chǎng)航班動(dòng)態(tài)排序方法,將某一時(shí)間區(qū)間劃分為多個(gè)排序時(shí)段,縮小了問(wèn)題的求解規(guī)模,滿足了離場(chǎng)航班排序的動(dòng)態(tài)性要求。

2) 從保障航空公司間的延誤公平性考慮,對(duì)各航空公司離場(chǎng)航班平均延誤的差別進(jìn)行轉(zhuǎn)化,提出了航空公司延誤公平性評(píng)價(jià)指標(biāo),用于航空公司延誤公平性的定量計(jì)算。

3) 根據(jù)不同類型離場(chǎng)航班的重要度,在離場(chǎng)排序時(shí)考慮其優(yōu)先級(jí)。 將非受控離場(chǎng)航班優(yōu)先級(jí)分為3 類,建立具有各類優(yōu)先級(jí)的非受控離場(chǎng)航班和其可接受的最大延誤時(shí)間、MPS 約束中最大位置偏移量之間的關(guān)系;考慮機(jī)場(chǎng)和航空公司雙方的訴求,將機(jī)場(chǎng)基地航空公司的非受控離場(chǎng)航班優(yōu)先級(jí)設(shè)置為次高等級(jí)。

4) 針對(duì)機(jī)場(chǎng)交通擁擠和非擁擠場(chǎng)景,分析空管、航司和機(jī)場(chǎng)在2 種場(chǎng)景下的不同利益需求,確定相應(yīng)的目標(biāo)函數(shù)及約束,建立了基于交通狀態(tài)的離場(chǎng)航班協(xié)同排序模型,設(shè)計(jì)了相應(yīng)的求解算法,所提方法可為空中交通管理人員制定航班排序方案提供理論支撐。