王興隆，石宗北，紀君柔

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

1 引言

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

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

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

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

2 問題描述

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

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

3 模型建立

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

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

3.1.1 航班延誤等級劃分

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

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

表1 航班延誤等級評價指標

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

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

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

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

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

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

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

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

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

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

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

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

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

4)假設(shè)各機場進離場分離。

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

表2 變量定義

決策變量定義如下：

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

1)延誤總成本最小

(1)

2)延誤總時間最小

(2)

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

minf=minf1minf2

(3)

3.3 約束條件

1)離場容量約束

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

Pmt≤Dm(t)

(4)

2) 尾流間隔約束

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

(5)

3)公共離場點約束

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

(6)

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

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

ηmax≤5

(7)

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

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

(8)

6) 航班運行特性約束

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

(9)

7)離場時隙約束

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

(10)

4 算法實現(xiàn)

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

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

4.1.1 速度與位置更新

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

多目標粒子群優(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)個體先存儲進外部集內(nèi)；

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

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

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

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

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

4.2 模型求解

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

圖1 基于多目標粒子群的模型求解流程圖

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

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

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

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

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

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

5 實例驗證

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

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

5.1 參數(shù)選取

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

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

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

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

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

表4 單位時間延誤成本

表5 航空器起飛尾流間隔標準規(guī)定

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

5.2 仿真結(jié)果分析

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

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

圖4 一組Pareto解計劃與實際對比圖

表7 不同機場延誤成本與延誤時間

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

表8 不同目標對比

6 結(jié)論

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