基于時空特征的終端區(qū)多機(jī)場航班時刻優(yōu)化

王興隆，石宗北，紀(jì)君柔

(中國民航大學(xué)空中交通管理學(xué)院，天津 300300)

1 引言

隨著我國民航業(yè)的不斷發(fā)展，在航班運(yùn)輸量不斷提高的同時，航班運(yùn)行正常性的保障壓力也隨之增大[1]，對延誤架次的控制成為了保障安全運(yùn)行前提下的重要挑戰(zhàn)。因此，為航班分配準(zhǔn)確的離場時刻對減輕延誤有著重大的意義。

目前，航班的離場過程受管制員控制，先到先服務(wù)(First Come First Served， FCFS)的理念已逐漸無法滿足日益增長的航班量和復(fù)雜的終端區(qū)運(yùn)行環(huán)境，在增加管制員的負(fù)擔(dān)的同時也增加了航班延誤成本及延誤時間。有序高效的對離場航班時刻排序成為研究熱點(diǎn)，國內(nèi)外相關(guān)學(xué)者從不同的角度對離場航班時刻優(yōu)化開展了大量研究。

離場航班時刻排序問題的研究主要集中于：動態(tài)調(diào)度、多跑道/多機(jī)場協(xié)同等方面[2]。Bolender[3]等在2000年對離場問題進(jìn)行了基礎(chǔ)性的研究；GUPTA[4]基于混合整數(shù)規(guī)劃的離場排序策略。隨著研究的深入，研究重心逐漸從單機(jī)場離場時刻優(yōu)化逐漸轉(zhuǎn)向了多機(jī)場協(xié)同離場放行。協(xié)同離場放行就是多個機(jī)場協(xié)同運(yùn)行，統(tǒng)籌規(guī)劃放行時刻，合理分配離場點(diǎn)和航線資源，使得運(yùn)行效率達(dá)到最大。Atking等[5]采用遺傳算法對離場航班協(xié)同放行時刻模型進(jìn)行求解。Capozzi等[6]提出空域資源和離場航路動態(tài)分配的方法，優(yōu)化了多機(jī)場協(xié)同離場放行問題。Chevalley等[7]將管制員管理的離場間隔工具與現(xiàn)有的戰(zhàn)術(shù)離場調(diào)度工具相結(jié)合，優(yōu)化多機(jī)場終端區(qū)航班協(xié)同離場問題。國內(nèi)，呂雙回[8]建立了終端區(qū)多機(jī)場航班協(xié)同放行模型，并采用啟發(fā)式隱枚舉算法求解。仇兆巨[9]基于管制運(yùn)行特點(diǎn)建立了多機(jī)場協(xié)同離場放行策略模型，并采用禁忌搜索算法求解。程傲[10]基于多機(jī)場協(xié)同放行和機(jī)場協(xié)同決策理念提出了珠三角多機(jī)場協(xié)同放行機(jī)制，并對多機(jī)場協(xié)同放行系統(tǒng)進(jìn)行了初步設(shè)計。通過對已有文獻(xiàn)梳理發(fā)現(xiàn)：多數(shù)研究未對終端區(qū)時空特征進(jìn)行考慮，即1)將每個機(jī)場視作同等地位的對象進(jìn)行建模。2)未考慮不同類型離場航班延誤特征不同對終端區(qū)造成影響的差異性。

本文在已有的研究基礎(chǔ)上，兼顧機(jī)場優(yōu)先級與航班延誤等級，以終端區(qū)內(nèi)的各機(jī)場群為對象建立總延誤成本最小、總延誤時間最少的多目標(biāo)優(yōu)化模型。并對京津大終端區(qū)兩地三場進(jìn)行了仿真驗(yàn)證。結(jié)果表明：本文所提方法可有效對多機(jī)場終端區(qū)離場時刻進(jìn)行分配，在降低航班延誤總時間及延誤成本的同時兼顧二者之間的平衡。與先到先服務(wù)策略相比，協(xié)同排序策略有著較好的優(yōu)化效果，對輔助管制員決策，提高機(jī)場及各航空公司效益，保障航班正常性等方面均有一定意義。

2 問題描述

多機(jī)場終端區(qū)是一個終端區(qū)內(nèi)具有兩個或者兩個以上機(jī)場構(gòu)成的機(jī)場群，機(jī)場間運(yùn)行相互制約，相互影響，空中交通流量密集，管制運(yùn)行復(fù)雜。在終端區(qū)內(nèi)飛行的航班分為進(jìn)場，離場以及穿越。終端區(qū)內(nèi)的航班的進(jìn)場、離場與穿越都需要管制員的協(xié)調(diào)與排序，避免飛行沖突，安全著陸或起飛，而多機(jī)場終端區(qū)空域資源有限，多個機(jī)場進(jìn)離場資源共享，因此多機(jī)場終端區(qū)的運(yùn)行約束更加復(fù)雜。機(jī)場統(tǒng)一離場放行的工作原理實(shí)際上是一個多元受限的排隊問題，航班離場時刻分配受多種因素影響。

在多機(jī)場的離場過程中存在各機(jī)場間共用離場定位點(diǎn)，航線匯聚點(diǎn)等空域資源的情況。同時，在協(xié)同放行過程中單位時間內(nèi)希望盡可能多的航班完成離場過程。因此終端區(qū)多機(jī)場協(xié)同放行問題兼具空間與時間特征。本文對終端區(qū)內(nèi)不同機(jī)場所處的空間位置、功能定位、運(yùn)行流量等進(jìn)行考慮以滿足離場放行過程中的空間特性；對不同類型航班延誤時間對終端區(qū)造成的影響進(jìn)行劃分以更好刻畫協(xié)同放行離場過程中的時間特征。

3 模型建立

設(shè)終端區(qū)內(nèi)所有機(jī)場m的集合為M，機(jī)場m在研究時段內(nèi)的離場航班集合為Fm。在充分考慮時空特性的基礎(chǔ)上提出航班延誤等級以及機(jī)場優(yōu)先度的概念，以延誤成本最小和延誤總時間最少進(jìn)行多目標(biāo)建模。

3.1 終端區(qū)時空特性描述

3.1.1 航班延誤等級劃分

航班類型的差異會對機(jī)場、公司等造成不同程度的影響，顧紹康[11]根據(jù)時間和空間兩個角度的評估指標(biāo)建立了航班延誤程度實(shí)時評估指標(biāo)體系。但僅考慮數(shù)值屬性指標(biāo)評估延誤等級，無法直觀有效的判斷航班延誤程度。

本文同時考慮數(shù)值屬性指標(biāo)和類別屬性指標(biāo)，對延誤航班進(jìn)行聚類分析，將延誤等級的劃分過程轉(zhuǎn)化為聚類過程。選取航班的延誤時間、飛行時間、延誤人數(shù)、航程等四個數(shù)值屬性以及航空器類型、是否經(jīng)停兩個類別屬性進(jìn)行聚類分析。研究中選取的屬性指標(biāo)值如表1所示。

表1 航班延誤等級評價指標(biāo)

在聚類得出結(jié)果的基礎(chǔ)上，采用粗糙集理論確定延誤航班等級劃分規(guī)則。

航班延誤等級規(guī)則生成步驟如下：

1)航班延誤屬性數(shù)值進(jìn)行離散化處理。

2)利用Johnson算法進(jìn)行屬性約簡，將多余的屬性值刪除。

3)獲取等價類和上下近似集。

4)生成航班延誤等級的劃分規(guī)則。

3.1.2 機(jī)場優(yōu)先度劃分

終端區(qū)內(nèi)的不同機(jī)場由于飛行航線，航班流量以及機(jī)場職能偏向等原因?qū)е虏煌瑱C(jī)場相同機(jī)型的航班延誤成本是不同的，因此在建立多機(jī)場協(xié)同放行機(jī)制時要進(jìn)一步考慮機(jī)場優(yōu)先度，本文根據(jù)所研究的多機(jī)場終端區(qū)內(nèi)各個機(jī)場的運(yùn)行情況分析，設(shè)定了相應(yīng)的優(yōu)先級因子。在本文中，機(jī)場優(yōu)先度由專家綜合航線數(shù)目、進(jìn)駐航司數(shù)量、航班量、功能定位等因素給出。

3.2 協(xié)同離場放行模型

為簡化模型復(fù)雜度，在本文中，對終端區(qū)離場過程做出如下假設(shè)：

1)多機(jī)場離場航班信息已知。

2)終端區(qū)內(nèi)各機(jī)場離場容量已知，離場定位點(diǎn)容量已知。

3)航班不得早于航班時刻表的時間起飛。

4)假設(shè)各機(jī)場進(jìn)離場分離。

建立模型所需參數(shù)及其定義如表2所示。

表2 變量定義

決策變量定義如下：

在此基礎(chǔ)上給出本文構(gòu)建模型的目標(biāo)函數(shù)。

1)延誤總成本最小

(1)

2)延誤總時間最小

(2)

3)多目標(biāo)優(yōu)化函數(shù)

minf=minf1minf2

(3)

3.3 約束條件

1)離場容量約束

終端區(qū)內(nèi)各機(jī)場應(yīng)在單位時間內(nèi)的離場航班數(shù)量滿足各機(jī)場的容量限制。即集合M內(nèi)的機(jī)場m在t時段的離場流量不大于該機(jī)場的離場容量，由式(4)表示

Pmt≤Dm(t)

(4)

2) 尾流間隔約束

不同類型的飛機(jī)在離場后會產(chǎn)生尾流，當(dāng)前機(jī)與后機(jī)之間起飛不滿足尾流間隔時會對后機(jī)運(yùn)行產(chǎn)生較大的安全影響。因此從相同機(jī)場起飛的相繼航班要滿足不同機(jī)型的尾流間隔值，尾流間隔約束由式(5)示

(5)

3)公共離場點(diǎn)約束

終端區(qū)內(nèi)不同機(jī)場放行的航班在經(jīng)過公用的同一離場點(diǎn)的航班流量不大于該離場點(diǎn)的離場容量，該約束由式(6)表示

(6)

4) 最大位置調(diào)整約束

在排序過程中，為了保持管制員工作負(fù)荷與減少延誤成本之間的平衡，本文設(shè)定航空器被優(yōu)化后在隊列中的位置與先到先服務(wù)隊列中的位置的差異不得大于5，在對航班次序盡量少的調(diào)換基礎(chǔ)上實(shí)現(xiàn)延誤最小化，可由式(7)表示

ηmax≤5

(7)

5) 機(jī)場優(yōu)先度因子約束

對終端區(qū)內(nèi)各機(jī)場優(yōu)先度進(jìn)行分配，各機(jī)場優(yōu)先度之和為1。由式(8)表示

(8)

6) 航班運(yùn)行特性約束

為使本文模型更貼近實(shí)際情況及運(yùn)行的公平性，規(guī)定離場航班在調(diào)整起飛次序之后不得早于航班計劃中的離港時間。由式(9)表示

(9)

7)離場時隙約束

每個起飛航班只有一個起飛時隙，如式(10)示

(10)

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

4.1 多目標(biāo)線性遞減粒子群算法(LD-MOPSO)

多目標(biāo)問題往往不能確定最優(yōu)值，一般得到的解對于其中一個目標(biāo)是最優(yōu)解而對于其它目標(biāo)則不是。多目標(biāo)粒子群算法(multi-objectiveparticleswarmoptimization，MOPSO)是粒子群算法解決多目標(biāo)問題的一種算法[12-13]。本文提出一種慣性權(quán)重線性遞減的粒子群算法(LD-PSO)對所建模型進(jìn)行求解，平衡了全局和局部搜索能力，更好的提高了算法尋優(yōu)性能。

4.1.1 速度與位置更新

慣性權(quán)重ω對粒子的速度變化進(jìn)行控制，慣性權(quán)重ω越大，粒子的速度越大，全局搜索能力越強(qiáng)，慣性權(quán)重ω越小，粒子的速度也越來越小，局部搜索能力越強(qiáng)。慣性權(quán)重ω為設(shè)為定值時，不能動態(tài)的平衡全局和局部搜索能力，對于有多個局部極值點(diǎn)的函數(shù)，容易陷入到局部極值，增大結(jié)果誤差。

多目標(biāo)粒子群優(yōu)化的速度與位置更新方法如式(11)和式(12)所示，線性權(quán)值遞減公式如式(13)示

vi，j(k+1)=ωvi，j(k)+c1r1(pbesti，j(k)-xi，j(k))

+c2r2(gbesti，j(k)-xi，j(k))

(11)

xi，j(k+1)=xi，j+vi，j(k+1)

(12)

(13)

i=1，2，…，N，j=1，2，…，n

4.1.2 外部集更新策略

外部集更新步驟如下：

Step1：算法開始時，將非支配集中的較優(yōu)個體先存儲進(jìn)外部集內(nèi)；

Step2：當(dāng)外部集里有粒子時，任意選取非支配解的某一個個體，假設(shè)為i，利用支配關(guān)系，依次判斷外部集中所有個體與該個體i，若結(jié)果是i被支配，則將i從外部集中刪除；若i不被任一個體支配或者i支配外部集中某一個或多個個體，則將i存入外部集，且將被支配的所有個體從外部集中刪除；

Step3：循環(huán)，直至算法完畢。

4.1.3 個體極值與全局極值選取

1)將當(dāng)前粒子位置(即新解)與當(dāng)前pbest進(jìn)行比較，如果新的解支配了當(dāng)前pbest，則新解作為新的pbest；如果新解和當(dāng)前pbest彼此不被對方支配，則從二者隨機(jī)選擇一個作為新的pbest。

2)從外部集的非支配解中隨機(jī)選擇一個解作為粒子的全局極值。

4.2 模型求解

對所提模型的多目標(biāo)求解算法流程如下，算法示意圖如圖1所示。

圖1 基于多目標(biāo)粒子群的模型求解流程圖

Step1：讀取終端區(qū)內(nèi)各個機(jī)場航班信息、機(jī)場容量信息、確定所選時段內(nèi)終端區(qū)離場定位點(diǎn)容量以及不同機(jī)型航班在終端區(qū)內(nèi)標(biāo)準(zhǔn)飛行時間，根據(jù)各個機(jī)場所選時段的航班流量確定機(jī)場優(yōu)先級因子，所選時段多機(jī)場終端區(qū)內(nèi)所有離場航班為粒子群P。

Step2：根據(jù)離場航班計劃時刻表結(jié)合尾流間隔利用先到先服務(wù)策略確定離場航班的初始起飛順序、起飛時間和過點(diǎn)時間。以航班初始起飛順序作為粒子。

Step3：初始化粒子群P，粒子位置x和粒子速度v；計算每個延誤程度評價指標(biāo)，由制航班延誤等級劃分，確定航班延誤等級損失系數(shù)g，計算每個粒子適應(yīng)度值。

Step4：按照Pareto支配關(guān)系要求，將非支配集中較優(yōu)個體存儲進(jìn)外部集中，從非支配集中選取群體極值gbest；

Step5：更新粒子的速度和位置，計算所有粒子新的適應(yīng)度值。更新外部集，更新個體極值pbest和群體極值gbest；

Step6：達(dá)到迭代次數(shù)停止，否則返回Step4。

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

隨著大興機(jī)場的投入運(yùn)營，京津地區(qū)兩地三場的終端區(qū)運(yùn)營模式逐漸成為具有代表性的多終端區(qū)空域系統(tǒng)。本節(jié)將新開航的大興機(jī)場納入研究范圍，以天津、北京兩地三場的大終端區(qū)運(yùn)行情況為背景進(jìn)行仿真驗(yàn)證。大興機(jī)場開航后的終端區(qū)空域結(jié)構(gòu)如圖2所示。

圖2 京津地區(qū)終端區(qū)空域結(jié)構(gòu)示意圖

5.1 參數(shù)選取

選取某大型樞紐機(jī)場一月份的4557條延誤航班數(shù)據(jù)作為樣本進(jìn)行航班延誤等級劃分，經(jīng)過k-prototype聚類及粗糙集劃分后得出的延誤等級如表3所示。

表3 航班延誤等級劃分規(guī)則表

京津終端區(qū)共包含北京首都機(jī)場、北京大興機(jī)場、天津?yàn)I海機(jī)場等兩地三場，其中北京大興國際機(jī)場運(yùn)營航司15家，航線量144條；天津?yàn)I海國際機(jī)場至今，運(yùn)營航司47家，航線量達(dá)205條。本文結(jié)合實(shí)際情況及專家評分設(shè)定優(yōu)先因子，首都機(jī)場為0.5，天津機(jī)場為0.2，大興機(jī)場為0.3。

以大興開航后繁忙時刻京津終端區(qū)8：00至8：30內(nèi)首都機(jī)場，大興機(jī)場和天津?yàn)I海機(jī)場的100架次離場航班為例，在考慮時空特征的前提下，從航班延誤時間、航班延誤成本兩方面統(tǒng)籌安排多機(jī)場航班協(xié)同放行時刻。

假設(shè)天津機(jī)場最大容量為12架次/15分鐘，北京機(jī)場最大容量為20架次/15分鐘，大興機(jī)場最大容量為30架次/15分鐘，各個離場點(diǎn)最大可用容量為5架次/10分鐘。結(jié)合本文實(shí)際問題，設(shè)置種群大小為300，最大粒子迭代次數(shù)為300代c1=0.5，c2=0.7。假設(shè)同延誤等級的航班單位時間延誤成本如表4所示，不同機(jī)型起飛尾流間隔標(biāo)準(zhǔn)規(guī)定如表5所示，大興機(jī)場開航后，大興機(jī)場及其它兩機(jī)場計劃航班時刻表如表6所示。

表4 單位時間延誤成本

表5 航空器起飛尾流間隔標(biāo)準(zhǔn)規(guī)定

表6 8∶00-8∶30計劃航班時刻表

5.2 仿真結(jié)果分析

當(dāng)算法最后到達(dá)所設(shè)置的停止代數(shù)時，Pareto最優(yōu)前沿圖如圖3所示，選取一組延誤成本與延誤時間相對平衡的Pareto解，圖4為一組Pareto解計劃與實(shí)際對比圖。

圖3 Pareto最優(yōu)前沿圖

圖4 一組Pareto解計劃與實(shí)際對比圖

表7 不同機(jī)場延誤成本與延誤時間

表7為基于一組Pareto解得到的不同機(jī)場延誤成本與延誤時間。表8為不同角度下延誤時間與延誤成本對比。由表9可得航班總延誤成本為72200元，航班總延誤時間為3982分鐘。由表8可得，Pareto一組得到的延誤成本較基于延誤成本角度增加0.32%，較基于延誤時間角度降低了1.23%，得到的延誤時間較基于延誤成本角度降低了2.3%，較基于延誤時間角度增加了4.1%。上述結(jié)果表明，多目標(biāo)優(yōu)化結(jié)果更好的平衡了總延誤成本與總延誤時間，從而避免單一優(yōu)化一個目標(biāo)函數(shù)而犧牲另一個目標(biāo)函數(shù)，更加的符合實(shí)際放行運(yùn)行情況，驗(yàn)證了模型的有效性。同時，相比于先到先服務(wù)策略，本文所提方法在延誤成本和延誤時間方面分別減少了22.3%和17.5%，證明了本文所提方法的有效性。

表8 不同目標(biāo)對比

6 結(jié)論

本文主要對基于時空特性的多機(jī)場終端區(qū)基于機(jī)場優(yōu)先級的協(xié)同放行問題進(jìn)行了研究，考慮延誤分級以及機(jī)場優(yōu)先度，建立了以航班總延誤成本和總延誤時間最小化的多目標(biāo)函數(shù)，構(gòu)造考慮延誤分級下基于機(jī)場優(yōu)先級的多機(jī)場協(xié)同放行模型，并采用多目標(biāo)線性遞減粒子算法對模型進(jìn)行求解，然后通過京津終端區(qū)新增大興機(jī)場的情況下的算例進(jìn)行仿真分析，最后分別求得基于最小延誤時間，基于最小延誤成本以及同時考慮延誤時間和延誤成本的多機(jī)場協(xié)同放行策略，通過分析對比，驗(yàn)證了模型的有效性，從而為多機(jī)場終端區(qū)構(gòu)建統(tǒng)一協(xié)同放行機(jī)制提供了理論方法和科學(xué)依據(jù)。