基于ABOD算法的機(jī)場(chǎng)容量包絡(luò)曲線設(shè)計(jì)研究

沈笑云，陳泰安，吳世桂，張 潔

(1. 中國(guó)民航大學(xué)天津市智能信號(hào)與圖像處理重點(diǎn)實(shí)驗(yàn)室，天津 300300；2. 重慶機(jī)場(chǎng)集團(tuán)有限公司航務(wù)管理部，重慶 400000)

1 引言

機(jī)場(chǎng)容量作為航空交通系統(tǒng)容量的瓶頸，對(duì)航空交通系統(tǒng)的運(yùn)行效率有著重要影響[1]?？茖W(xué)準(zhǔn)確地評(píng)估機(jī)場(chǎng)容量對(duì)于應(yīng)對(duì)空中交通流量迅猛增長(zhǎng)、緩解機(jī)場(chǎng)擁堵和延誤具有重要作用。到目前為止，機(jī)場(chǎng)容量評(píng)估的主流方法有三種，分別是基于容量包絡(luò)曲線分析評(píng)估[2-4]，基于數(shù)學(xué)模型計(jì)算評(píng)估[5]，基于仿真軟件(Simmod， Arena)模擬評(píng)估[6]?；谌萘堪j(luò)曲線評(píng)估是通過(guò)分析機(jī)場(chǎng)航班歷史運(yùn)行數(shù)據(jù)，統(tǒng)計(jì)得到單位時(shí)間內(nèi)的進(jìn)離場(chǎng)架次，繪制容量包絡(luò)曲線分析機(jī)場(chǎng)容量。機(jī)場(chǎng)航班歷史運(yùn)行數(shù)據(jù)包含機(jī)場(chǎng)高峰繁忙時(shí)段的運(yùn)行數(shù)據(jù)信息，這些數(shù)據(jù)信息能夠反映機(jī)場(chǎng)處于或者超出容量水平值的狀態(tài)。機(jī)場(chǎng)容量包絡(luò)曲線反映了機(jī)場(chǎng)抵港容量和離港容量的內(nèi)在關(guān)系，以及不同抵離港比率下機(jī)場(chǎng)所能容納的單位時(shí)間內(nèi)航班架次的能力?；跀?shù)學(xué)模型評(píng)估是將航空器在機(jī)場(chǎng)的運(yùn)作過(guò)程用數(shù)學(xué)公式表示，通過(guò)模擬它們的運(yùn)作流程來(lái)確定容量?；诜抡孳浖M評(píng)估是用軟件詳細(xì)模擬飛行區(qū)運(yùn)行的各個(gè)方面，通過(guò)精確仿真機(jī)場(chǎng)、滑行道以及空域系統(tǒng)評(píng)估容量。在以上三種方法中，實(shí)施容量包絡(luò)曲線評(píng)估相對(duì)較易，因此，受到歐洲和美國(guó)一些主要機(jī)場(chǎng)的廣泛采用[7]?；谌萘堪j(luò)曲線評(píng)估的關(guān)鍵是通過(guò)一定的方法獲得準(zhǔn)確的包絡(luò)曲線，而劃設(shè)包絡(luò)曲線的關(guān)鍵是對(duì)離群值的處理，只有合理地剔除離群數(shù)據(jù)，才能依據(jù)留存的正常數(shù)據(jù)準(zhǔn)確地劃設(shè)容量包絡(luò)曲線。

目前，容量包絡(luò)曲線的劃設(shè)方法有三種，分別是基于頻率閾值劃設(shè)[2]、分位數(shù)回歸[3]，以及將問(wèn)題轉(zhuǎn)化成機(jī)會(huì)約束規(guī)劃問(wèn)題，再用場(chǎng)景法求解[4]。這三種方法均存在以下不足：①容量包絡(luò)曲線的形狀取決于預(yù)設(shè)參數(shù)，不同的預(yù)設(shè)參數(shù)會(huì)出現(xiàn)不同的結(jié)果，而能夠真實(shí)反映機(jī)場(chǎng)運(yùn)行容量的包絡(luò)曲線對(duì)應(yīng)的參數(shù)如何設(shè)置，至今還沒(méi)有準(zhǔn)確的結(jié)論。②以不同的樣本數(shù)據(jù)數(shù)量做分析，預(yù)設(shè)參數(shù)也不同，樣本數(shù)據(jù)數(shù)量與參數(shù)的對(duì)應(yīng)關(guān)系不明確。

針對(duì)以上劃設(shè)容量包絡(luò)曲線方法的不足，本文提出應(yīng)用ABOD算法[8]來(lái)劃設(shè)容量包絡(luò)曲線，通過(guò)計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)的ABOF值，并返回根據(jù)ABOF值排序的數(shù)據(jù)點(diǎn)列表，依據(jù)ABOF值的波動(dòng)情況確定離群值的范圍，插值后經(jīng)凸包算法勾劃容量包絡(luò)曲線輪廓。應(yīng)用ABOD算法劃設(shè)容量包絡(luò)曲線無(wú)需考慮樣本基數(shù)與預(yù)設(shè)參數(shù)的對(duì)應(yīng)關(guān)系，有效降低了樣本數(shù)據(jù)數(shù)量的差異對(duì)輸出結(jié)果的影響，且無(wú)需設(shè)置參數(shù)避免了因參數(shù)設(shè)置過(guò)與不及而導(dǎo)致容量包絡(luò)曲線失真的問(wèn)題。該方法得到的容量包絡(luò)曲線更穩(wěn)定，能夠更加真實(shí)地反映機(jī)場(chǎng)容納單位時(shí)間內(nèi)航班架次的能力，對(duì)于空管人員規(guī)劃進(jìn)離場(chǎng)航班、優(yōu)化機(jī)場(chǎng)容量具有重要意義。

2 基于ABOD算法劃設(shè)容量包絡(luò)曲線

異常值也稱(chēng)離群值，是指與正常數(shù)據(jù)不一致、具有一定偏差的數(shù)據(jù)實(shí)例。本文基于歷史航班運(yùn)行數(shù)據(jù)統(tǒng)計(jì)得到單位時(shí)間進(jìn)離場(chǎng)架次數(shù)據(jù)中的異常數(shù)據(jù)是指數(shù)據(jù)采集或記錄過(guò)程產(chǎn)生錯(cuò)誤的、或者某時(shí)段內(nèi)超出機(jī)場(chǎng)容納航班能力的偏離正常運(yùn)行航班數(shù)據(jù)的離群值。ABOD算法是數(shù)據(jù)挖掘領(lǐng)域中的一種異常檢測(cè)算法，大多數(shù)異常檢測(cè)模型要求用戶指定對(duì)輸出結(jié)果有著重要影響的參數(shù)，在實(shí)際應(yīng)用中，這種要求總是一個(gè)弊端。而基于ABOD算法檢測(cè)進(jìn)離場(chǎng)架次異常數(shù)據(jù)、劃設(shè)容量包絡(luò)曲線無(wú)需設(shè)置參數(shù)，不存在難以確定合適參數(shù)的問(wèn)題[9]。

2.1 ABOD算法

ABOD算法通過(guò)比較不同位置數(shù)據(jù)點(diǎn)與其它任意兩點(diǎn)連線所構(gòu)成夾角大小的差異程度，以?shī)A角的方差大小作為判斷該數(shù)據(jù)點(diǎn)是否離群的依據(jù)。由于離群值與其它任意兩點(diǎn)連線的夾角大小差異小，故其方差較??；而聚集區(qū)域內(nèi)的點(diǎn)與其它任意兩點(diǎn)連線的夾角大小差異大，故其夾角方差相對(duì)較大。夾角的方差大小程度用基于角度的離群系數(shù)(ABOF)表示，公式化表述如下。

(1)

通過(guò)式(1)的計(jì)算可對(duì)每個(gè)數(shù)據(jù)點(diǎn)賦予表征該點(diǎn)離群程度的ABOF值，ABOF值越小，表明該點(diǎn)為離群值的可能性越大。為直觀描述該算法，用示意數(shù)據(jù)說(shuō)明如下，根據(jù)式(1)對(duì)圖1中每個(gè)示意數(shù)據(jù)點(diǎn)計(jì)算ABOF值，并對(duì)計(jì)算結(jié)果從小到大編號(hào)，如圖1所示。

圖1 計(jì)算示意數(shù)據(jù)點(diǎn)的ABOF值

圖1中的每個(gè)數(shù)據(jù)點(diǎn)旁邊的數(shù)字表示該點(diǎn)的編號(hào)，中間矩形框內(nèi)標(biāo)明了每個(gè)編號(hào)的ABOF值，其中，[1：1.80e-09]表明編號(hào)為1的數(shù)據(jù)點(diǎn)的ABOF值為1.80×10-9。從圖1可以看出，數(shù)據(jù)點(diǎn)離聚集區(qū)域越遠(yuǎn)，ABOF值越??；離聚集區(qū)域中心越近， ABOF值越大。而且，編號(hào)為1的數(shù)據(jù)點(diǎn)的ABOF值遠(yuǎn)小于其它數(shù)據(jù)點(diǎn)的ABOF值(與編號(hào)為2的數(shù)據(jù)點(diǎn)的ABOF值相差105倍)。因此，可對(duì)ABOF值明顯低于其它ABOF值的數(shù)據(jù)點(diǎn)作為離群值予以剔除。

2.2 離群值范圍設(shè)定

實(shí)際上，并非所有給定的數(shù)據(jù)集中離群數(shù)據(jù)的ABOF值與聚集區(qū)域內(nèi)正常數(shù)據(jù)的ABOF值差異都如此明顯。例如，基于航班歷史運(yùn)行數(shù)據(jù)統(tǒng)計(jì)得到的單位時(shí)間進(jìn)離場(chǎng)架次數(shù)據(jù)集中，ABOF值由小到大是逐步過(guò)渡的，僅根據(jù)ABOF數(shù)值的大小，較難確定離群數(shù)據(jù)的ABOF值。但是，當(dāng)對(duì)所有的ABOF值從小到大排序后，ABOF值在由小到大的遞增過(guò)程中，會(huì)經(jīng)歷離群數(shù)據(jù)到離群數(shù)據(jù)，離群數(shù)據(jù)到正常數(shù)據(jù)，正常數(shù)據(jù)到正常數(shù)據(jù)三個(gè)階段的過(guò)渡，每個(gè)過(guò)渡階段的ABOF值的變化波動(dòng)均不一致，如圖2所示。

圖2 ABOF值的變動(dòng)情況

圖2的漸變色條標(biāo)明了由離群值向正常值的過(guò)渡，也表示ABOF值由小到大的遞增過(guò)程。從圖2可以看出，由離群數(shù)據(jù)向離群數(shù)據(jù)過(guò)渡及由離群數(shù)據(jù)向正常數(shù)據(jù)過(guò)渡，這兩種情況ABOF值波動(dòng)較大，因?yàn)殡x群點(diǎn)在遠(yuǎn)離聚集區(qū)域的位置隨意分布，量化數(shù)據(jù)點(diǎn)離群程度的ABOF值彼此差異較大。而由正常點(diǎn)向正常點(diǎn)過(guò)渡， ABOF值的波動(dòng)較小，因?yàn)檎｜c(diǎn)都位于聚集區(qū)域內(nèi)，彼此較為集中，量化離群程度的ABOF值彼此接近，ABOF值波動(dòng)不明顯。根據(jù)這個(gè)規(guī)律，可用ABOF值后者與前者的比值作為ABOF值波動(dòng)的度量，可對(duì)ABOF值前后波動(dòng)變化較大的數(shù)據(jù)點(diǎn)作為離群數(shù)據(jù)予以剔除。

2.3 凸包算法勾劃容量包絡(luò)曲線輪廓

基于以上分析，經(jīng)ABOD算法剔除離群數(shù)據(jù)后，根據(jù)容量包絡(luò)曲線的輪廓特征，本文設(shè)計(jì)凸包算法(Graham掃描法)勾劃容量包絡(luò)曲線輪廓。求解凸包的算法常用的有Graham掃描法，由于已有較多文獻(xiàn)對(duì)Graham掃描法展開(kāi)論述，故本文不做過(guò)多介紹。容量包絡(luò)曲線反映了不同抵離港比率下機(jī)場(chǎng)所能容納單位時(shí)間內(nèi)航班架次的能力。一般認(rèn)為，在首部和尾部部分的容量包絡(luò)曲線平行于坐標(biāo)軸，而直接應(yīng)用凸包算法勾劃得到的容量曲線與實(shí)際有偏差。根據(jù)機(jī)場(chǎng)容量包絡(luò)曲線的特征，本文在應(yīng)用凸包算法之前，先對(duì)數(shù)據(jù)點(diǎn)進(jìn)行插值。首先，根據(jù)留存的正常數(shù)據(jù)，找出縱坐標(biāo)最大的數(shù)據(jù)點(diǎn)和橫坐標(biāo)最大的數(shù)據(jù)點(diǎn)，記最大的縱坐標(biāo)和最大的橫坐標(biāo)分別為ymax和xmax，然后插值(0，ymax)、(xmax，0)和(0，0)三個(gè)點(diǎn)，在插入這三個(gè)點(diǎn)后應(yīng)用凸包算法可最終完成容量包絡(luò)曲線的繪制，如圖3所示。

圖3 插值前后的凸包形狀

圖3用示意數(shù)據(jù)說(shuō)明了插值前后應(yīng)用凸包算法劃設(shè)容量包絡(luò)曲線的不同，圖3(a)為插值前的凸包，不符合機(jī)場(chǎng)容量曲線形狀，而圖3(b)為插值后的凸包，符合機(jī)場(chǎng)容量曲線形狀特征。

3 仿真研究

為驗(yàn)證本文提出方法的有效性，以重慶江北國(guó)際機(jī)場(chǎng)為例，根據(jù)歷史航班運(yùn)行時(shí)刻數(shù)據(jù)，統(tǒng)計(jì)得到六月份小時(shí)進(jìn)離港架次樣本數(shù)據(jù)，共720條，如表1所示。

表1 六月份小時(shí)進(jìn)離港架次數(shù)據(jù)

表1記錄了6月1號(hào)至6月30號(hào)每個(gè)小時(shí)段的抵港離港架次，以每小時(shí)段的抵港離港架次作為一個(gè)數(shù)據(jù)點(diǎn)(例如(24，5)、(22，1)…(28，18))，共720個(gè)數(shù)據(jù)點(diǎn)。根據(jù)式(1)，計(jì)算ABOF值需要兩點(diǎn)之間的距離作為分母，而重復(fù)數(shù)據(jù)點(diǎn)之間的距離為0，故先將720條數(shù)據(jù)中重復(fù)的數(shù)據(jù)剔除，剔除后僅留399個(gè)數(shù)據(jù)點(diǎn)。對(duì)399個(gè)數(shù)據(jù)點(diǎn)計(jì)算對(duì)應(yīng)的ABOF值，計(jì)算結(jié)果如表2所示。

表2 數(shù)據(jù)點(diǎn)對(duì)應(yīng)ABOF值的計(jì)算

圖4 ABOF值波動(dòng)梯形圖

圖4記錄了398個(gè)ABOF比值，從圖4可以看出，梯形圖的前面小部分波動(dòng)較大，后面大部分波動(dòng)較小。根據(jù)2.2節(jié)的分析，基本可以判定前面小部分ABOF比值波動(dòng)較大的數(shù)據(jù)點(diǎn)為離群值。剔除離群值后，對(duì)剩下的樣本數(shù)據(jù)應(yīng)用凸包算法繪制包絡(luò)曲線，如圖5所示。

圖5 繪制六月份數(shù)據(jù)的容量包絡(luò)曲線

圖5中實(shí)心點(diǎn)為離群點(diǎn)，旁邊的數(shù)字為對(duì)應(yīng)的ABOF值(4.93E-06表示數(shù)值4.93×10-6)，其大小反映了離群程度的大小。由于基于ABOD的異常檢測(cè)算法可將內(nèi)外部的離群值都檢測(cè)，但是僅需要剔除外部的離群值，故圖5僅標(biāo)識(shí)了檢測(cè)出的外部的離群值。

同理，本文對(duì)重慶江北國(guó)際機(jī)場(chǎng)7月1日至12月31日六個(gè)月份記錄的歷史航班運(yùn)行時(shí)刻信息進(jìn)行分析，統(tǒng)計(jì)得到6個(gè)月份的小時(shí)抵港離港架次，以一個(gè)月的數(shù)據(jù)量為一組，分別基于ABOD算法繪制容量包絡(luò)曲線，如圖6所示。

圖6 繪制7-12月份數(shù)據(jù)的容量包絡(luò)曲線

從圖6可以看出，由不同月份繪制得到的容量包絡(luò)曲線并不一致，因?yàn)槊總€(gè)月份的小時(shí)抵港離港架次樣本數(shù)據(jù)不一致，剔除的離群值也不一致，如表3所示。

表3 不同月份的數(shù)據(jù)總量及剔除離群值的數(shù)量

表3標(biāo)明了每個(gè)月份的數(shù)據(jù)總量及剔除離群值的數(shù)量，數(shù)據(jù)總量記錄了剔除小時(shí)抵離港架次都為0的數(shù)據(jù)點(diǎn)后的數(shù)值。雖然不同月份的樣本數(shù)據(jù)及剔除的數(shù)據(jù)都不一致，導(dǎo)致所得到的容量包絡(luò)曲線也不一致，但對(duì)于一個(gè)機(jī)場(chǎng)而言，容量曲線反映了機(jī)場(chǎng)容納航班架次的能力，一般是相對(duì)固定的。所以，由不同數(shù)據(jù)分析得到的不同容量包絡(luò)曲線的差異程度，可作為容量包絡(luò)曲線劃設(shè)方法優(yōu)劣的比較依據(jù)。如果容量包絡(luò)曲線差異程度小，則表征容量包絡(luò)曲線劃設(shè)方法相對(duì)穩(wěn)定可靠，魯棒性高，由此得到的容量包絡(luò)曲線能夠更加真實(shí)的反映機(jī)場(chǎng)容納航班架次的能力。

4 與基于頻率閾值劃設(shè)容量包絡(luò)曲線對(duì)比分析

基于以上分析，為比較不同劃設(shè)方法所得容量包絡(luò)曲線的差異程度，將基于ABOD算法劃設(shè)得到的不同月份的容量包絡(luò)曲線繪制如下，如圖7所示。

圖7 基于ABOD算法繪制不同月份的容量包絡(luò)曲線

圖7所展示的六條不同線形的容量包絡(luò)曲線代表由不同月份分析得到的?？梢钥闯?，容量包絡(luò)曲線首部和尾部差異較大，這是因?yàn)橐砸粋€(gè)月的數(shù)據(jù)量為單位做分析，數(shù)據(jù)量較少導(dǎo)致出現(xiàn)在首部和尾部的數(shù)據(jù)點(diǎn)有一定程度的差異。

基于頻率閾值劃設(shè)容量包絡(luò)曲線是根據(jù)出現(xiàn)頻率一致的數(shù)據(jù)點(diǎn)繪制凸?fàn)畹倪B續(xù)的容量曲線。Gilbo出于魯棒性考慮，取頻率閾值為3的包絡(luò)線作為機(jī)場(chǎng)容量曲線[2]，但是，頻率閾值為3的包絡(luò)線對(duì)應(yīng)的樣本數(shù)據(jù)數(shù)量是多少，并未給出明確的結(jié)論。趙征通過(guò)分析一年的小時(shí)進(jìn)離場(chǎng)架次數(shù)據(jù)，得出頻率閾值為3的容量曲線比較適合兩個(gè)自然月的樣本數(shù)據(jù)，共1464個(gè)樣本基數(shù)[11]。綜合兩者的研究結(jié)論，本文基于重慶江北國(guó)際機(jī)場(chǎng)7月至12月六個(gè)月份的小時(shí)進(jìn)離港架次數(shù)據(jù)，以每個(gè)月為單位取頻率閾值為2的容量包絡(luò)曲線繪制如下，如圖8所示。

圖8 基于頻率閾值繪制不同月份的容量包絡(luò)曲線

圖8所展示的六條不同線形的容量包絡(luò)曲線代表由不同月份分析得到的。從圖8可以看出，7-11月份的容量曲線較為集中，而12月份的容量曲線偏離較大，故將12月份的頻率閾值為2的容量包絡(luò)曲線單獨(dú)繪制如下，如圖9所示。

圖9 繪制12月份數(shù)據(jù)的散點(diǎn)密度圖

圖9是用色彩的深淺來(lái)表示數(shù)據(jù)點(diǎn)不同出現(xiàn)頻率的散點(diǎn)密度圖。由于以一個(gè)月的數(shù)據(jù)量為單位分析，外層低頻率數(shù)據(jù)點(diǎn)出現(xiàn)的頻率較為隨機(jī)，偶然性比較大，導(dǎo)致基于頻率閾值劃設(shè)容量包絡(luò)曲線差異較大，故以十二月份的樣本數(shù)據(jù)取頻率閾值為2的容量包絡(luò)曲線與其它月份的容量包絡(luò)曲線差異較大。直觀比較圖7和圖8可知，與基于頻率閾值劃設(shè)容量曲線相比，基于ABOD算法劃設(shè)的六條容量包絡(luò)曲線更接近，表明該容量包絡(luò)曲線劃設(shè)方法相對(duì)穩(wěn)定可靠，魯棒性高，所得容量曲線能夠更加真實(shí)的反映機(jī)場(chǎng)抵離港容量的內(nèi)在關(guān)系。

5 結(jié)論

機(jī)場(chǎng)容量評(píng)估方法中，基于容量包絡(luò)曲線評(píng)估由于實(shí)施相對(duì)較易，故受到了廣泛采用。該方法的關(guān)鍵是準(zhǔn)確地劃設(shè)代表機(jī)場(chǎng)容納航班架次能力的容量包絡(luò)曲線。目前，幾種劃設(shè)方法均存在樣本基數(shù)與參數(shù)設(shè)置不明確、容量包絡(luò)曲線形狀受預(yù)設(shè)參數(shù)影響較大的問(wèn)題。本文提出基于ABOD算法的容量包絡(luò)曲線劃設(shè)方法，該方法劃設(shè)容量包絡(luò)曲線無(wú)需設(shè)置參數(shù)，能夠有效降低樣本數(shù)據(jù)的差異對(duì)容量包絡(luò)曲線的影響，魯棒性更好。與基于頻率閾值劃設(shè)容量包絡(luò)曲線對(duì)比分析，發(fā)現(xiàn)通過(guò)該方法得到的容量包絡(luò)曲線能夠更加真實(shí)的反映機(jī)場(chǎng)實(shí)際運(yùn)行容量，這對(duì)進(jìn)一步評(píng)估、優(yōu)化機(jī)場(chǎng)容量具有重要意義。