楊新湦，齊　莉，翟文鵬

(中國民航大學(xué) 空中交通管理研究基地，天津 300300)

?

航班時刻資源優(yōu)化配置與延誤水平評估

楊新湦，齊莉，翟文鵬

(中國民航大學(xué) 空中交通管理研究基地，天津 300300)

摘要：針對中國大型機場由于航班時刻資源受限造成的航班延誤問題，在評估機場容量的基礎(chǔ)上，建立了降低機場航班延誤水平的航班時刻分配模型。在滿足機場容量限制，考慮航班連續(xù)性和中轉(zhuǎn)旅客需求的約束下，應(yīng)用改進的吱呀輪優(yōu)化算法尋求航班調(diào)整總量最小的分配方案。以北京首都國際機場的航班時刻資源配置為例進行優(yōu)化，并應(yīng)用SIMMOD軟件對模型設(shè)計算法，驗證航班時刻優(yōu)化模型的有效性。優(yōu)化結(jié)果顯示：北京首都國際機場的進離港延誤水平都降低了26%以上，放行正常率提高了20%。

關(guān)鍵詞：航空運輸；航班時刻資源；SIMMOD仿真；時刻分配；機場容量

0引言

隨著中國民航運輸業(yè)的迅速發(fā)展，航班時刻資源的需求與供給矛盾日趨突出，航班正常率低。造成機場延誤的原因包括天氣、交通流量控制和機場設(shè)備保障等，但最根本的原因是有限的機場容量不能滿足旺盛的交通流量需求。中國大型機場的容量已達到飽和，部分機場安排的航班時刻量已超過機場容量負荷，一旦發(fā)生惡劣天氣或航路流量控制等情況，很容易造成機場航班的延誤[1]。

解決航班延誤的方法主要有：改善基礎(chǔ)設(shè)施以提高機場的運作效率；運用新技術(shù)和采用空中交通流量管理對機場和附近空域的交通流進行調(diào)整。文獻[2]根據(jù)航班時刻安排對跑道容量的影響，建立了多目標航班時刻優(yōu)化模型。文獻[3]通過協(xié)調(diào)航班延誤數(shù)量與延誤最長晚點時間，對降落航班排序。文獻[4]通過規(guī)定載貨航班在特定跑道起降，建立了平行跑道進離場排序模型，對進離港排序后有效減少了航班延誤。但上述模型并未考慮進離港航班之間的相互影響，而當(dāng)前中國機場采用進離港相互運作和協(xié)調(diào)的策略，因此，機場容量評估和航班時刻配置必須考慮進離港航班。文獻[5]考慮機場容量和航班連續(xù)性因素，基于進離港容量和機場容量，實現(xiàn)了容量與時隙協(xié)同優(yōu)化配置。

上述研究在解決航班延誤方面取得了一定成果，主要集中在進離港排序問題和提高跑道利用率等方面，但僅是在已有航班時刻的基礎(chǔ)上對同時刻的起降飛機進行排序。為了從根本上解決航班延誤問題，首先需要解決需求和容量之間的矛盾關(guān)系，對航班時刻進行合理編排。本文通過對航班時刻進行預(yù)先調(diào)配，減少航班延誤產(chǎn)生的誘因。大型機場在容量受限的情況下，通常會采用“削峰填谷”的策略削減機場的高峰航班量，可以大大減少航班延誤[6]，從而降低航空公司和旅客的損失[7]。本文提出的航班時刻優(yōu)化方案不僅涉及航班時刻資源的優(yōu)化，而且考慮進離港航班的相關(guān)性、連續(xù)航程的航班和中轉(zhuǎn)旅客的需求等。同時，本文應(yīng)用SIMMOD軟件進行模擬仿真，對航班進行進一步調(diào)整。

1模型算法

為了有效解決大型機場航班時刻資源需求旺盛與有限供給之間的矛盾，本文采用“削峰填谷”的策略，以評估出的機場容量為基準，對各個時段的航班架次進行調(diào)整。在滿足航班連續(xù)性和旅客中轉(zhuǎn)需求的基礎(chǔ)上，尋找最符合原始航班時刻表的調(diào)整方案，即航班的調(diào)整總量和最大調(diào)整量最小的多目標優(yōu)化方案。

1.1機場航班時刻優(yōu)化模型

以航班的調(diào)整總量最小和航班最大調(diào)整量最小建立下面的目標函數(shù)：

(1)

其中：S為航班的調(diào)整總量最小和航班最大調(diào)整量的加權(quán)函數(shù)值；λ為航班調(diào)整總量的加權(quán)因數(shù)，本文取λ=1。

例如，航班i在初始航班時刻表中的時刻為09:30，優(yōu)化后的航班時刻為09:45，則航班調(diào)整量ui為15 min；航班j在原始航班時刻表中的時刻為08:00，優(yōu)化后的時刻為08:30，則航班調(diào)整量為30 min；那么,航班調(diào)整總量為45 min，航班最大調(diào)整量δ為max(15,30)=30 min。航班時刻優(yōu)化模型旨在盡量滿足航空公司的航班申請需求，最小限度地調(diào)整原始航班時刻表，因此，目標函數(shù)為航班最大調(diào)整量δ最小，并且航班的調(diào)整總量ui最小。

約束條件：

(Ⅰ)滿足航班限制。每個航班必須分配且只分配一個時刻，調(diào)整的航班均得到一個新的進港和離港時間：

(2)

(3)

(4)

(5)

其中：

約束條件(2)和(3)保證了所有航班在新的航班時刻表中都分配到一個時刻，約束條件(4)和(5)為原始航班時刻和新的航班時刻與調(diào)整量之間的關(guān)系。

(Ⅱ)滿足機場容量限制。在每個時間窗內(nèi)進港航班總數(shù)和離港航班總數(shù)受到最大進港隊長和最大出港隊長的限制：

(6)

(7)

(Ⅲ)滿足航班連續(xù)性。具有連續(xù)性的航班必須滿足所需的最小中轉(zhuǎn)時間和最大中轉(zhuǎn)時間的限制：

(8)

(9)

其中：

同一架飛機在新的航班時刻表中將按照原定路線飛行，其中一個航班的時刻被調(diào)整，其他相關(guān)的航班都會受到影響，本文設(shè)定銜接航班必須滿足最小中轉(zhuǎn)時間和最大中轉(zhuǎn)時間的限制。

(Ⅳ)滿足旅客中轉(zhuǎn)需求。具有聯(lián)程的航班必須滿足旅客中轉(zhuǎn)所需的時間：

(10)

其中：

圖1　優(yōu)化算法流程圖

1.2改進的吱呀輪優(yōu)化算法

吱呀輪優(yōu)化算法(squeaky-wheel optimization,SWO)由構(gòu)造器、分析器和優(yōu)先級排序器三部分組成，具有較強的鄰域搜索能力，能夠提高算法的收斂速度[8]。本文在原始的SWO算法中加入了遺傳算法(genetic algorithm,GA)中的選擇和變異操作，用來加速收斂，并設(shè)計出新的算法。優(yōu)化算法流程如圖1所示。

(Ⅰ)從輸入的航班集合和時間集合中依次選取航班和時間窗加入已設(shè)計的方案中，初始解設(shè)定為原始航班時刻表。

(Ⅱ)利用分析器對所有時間窗內(nèi)已排序的航班進行分析，對不滿足約束條件的航班給出責(zé)罰值。

(Ⅲ)加入遺傳算法中的選擇和變異操作，加快收斂速度。根據(jù)某航班的適應(yīng)程度和選擇概率進行優(yōu)化。若航班適應(yīng)度值大于選擇概率則留在此位置，否則將從此位置離開。

(Ⅳ)對先前已排序的航班序列重新排序，采用冒泡排序算法，此步驟主要是控制航班最大調(diào)整量[9]。

2算法仿真

本文選取首都機場2014年8月20日的航班時刻表，共1 713個航班，其中進港811架，離港902架，通過飛機的機尾號信息得知948個航班涉及機型銜接問題。機場的最小中轉(zhuǎn)時間定為45 min，最大中轉(zhuǎn)時間定為相互銜接的兩個航班時刻的時間間隔。旅客銜接信息主要從航空公司獲得，旅客最小中轉(zhuǎn)時間τij=60 min。

機場容量評估是航班時刻編排的基本依據(jù)。本文統(tǒng)計了機場歷史的進離港航班數(shù)據(jù)，利用具有噪聲的基于密度的聚類算法(density-based spatial clustering of applications with noise，DBSCAN)完成進離港架次散點圖聚類分析，采用迭代核密度估計算法求取運行容量概率極大值[10]。圖2為機場進離港架次散點圖，機場實際運行中的最大容量為33架。圖3為機場起降架次概率分布圖，越靠近中心群，機場運行效率越高，最適宜的機場容量為26架。根據(jù)容量評估的結(jié)果，選取A=13，D=15。

圖2 機場進離港架次散點圖圖3 機場起降架次概率分布圖

根據(jù)本文的優(yōu)化模型，應(yīng)用改進的SWO算法求得：需調(diào)整230個航班，調(diào)整總量350架，30 min最大調(diào)整量為2架。SIMMOD仿真模型能夠?qū)ε艿馈⒒械?、停機位及終端區(qū)空域等進行仿真，從而預(yù)先得知航班時刻配置的優(yōu)劣，輸出延誤信息，得到可接受延誤水平下的機場容量評估。本文在真實模擬首都機場運行環(huán)境的基礎(chǔ)上，分別輸入優(yōu)化前后的航班時刻表，檢驗延誤水平[11]。表1為航班時刻優(yōu)化前后的延誤評估結(jié)果。由表1可見：延誤時間大大減少，航班放行率提高。東區(qū)進離港延誤均降低了40%以上，西區(qū)進離港延誤均降低了26%以上，進離港總延誤降低了26%以上，放行正常率提高了20%。

表1　航班時刻優(yōu)化前后的延誤評估結(jié)果

圖4和圖5分別為首都機場優(yōu)化前和優(yōu)化后的航班時刻分布情況，描述了首都機場某日6時至24時每15 min進離港航班架次總數(shù)的變化趨勢,直線表示一天中離港航班架次的變化趨勢，點線表示一天中進港航班架次的變化趨勢。圖4中,早上的離港高峰和晚上的進港高峰突出，航班過于集中；其他時刻的進離港航班均在15架次左右波動，波動幅度較大。經(jīng)過調(diào)整后的航班時刻表有效控制了各時段進離港航班架次，高峰時段的航班分布較為平均，如圖5所示。

圖4優(yōu)化前的航班時刻表 圖5優(yōu)化后的航班時刻表

3結(jié)束語

本文討論了航班時刻優(yōu)化配置的問題，同時考慮了機場進離港航班的相互關(guān)系、航班連續(xù)性和旅客中轉(zhuǎn)需求等約束條件，建立了最大限度符合原始航班時刻表的優(yōu)化模型。設(shè)計了優(yōu)化算法進行求解，合理安排航班時刻排序，并應(yīng)用SIMMOD仿真軟件對優(yōu)化前后的航班時刻表進行評估。使用優(yōu)化后的航班時刻表，延誤水平降低了26%以上，放行正常率提高了20%。本文的優(yōu)化模型可用于大型機場的航班時刻配置，可以提高航班正常率，能夠緩解繁忙機場的擁堵和延誤問題。

參考文獻：

[1]楊文東,黃鸝詩,劉萬明.首都機場航班延誤分布規(guī)律分析[J].交通運輸系統(tǒng)工程與信息,2013,13(2):199-204.

[2]彭瑛,胡明華,李印風(fēng).基于航班時刻優(yōu)化的跑道運行容量提升方法[J].系統(tǒng)工程理論實踐,2014,34(10):2695-2700.

[3]王世東,張越,張智海,等.繁忙機場航班降落排序的多目標優(yōu)化[J].交通運輸系統(tǒng)工程與信息,2012,12(4):135-142.

[4]王莉莉,顧秋麗.特殊情況下的進離場航班排序問題研究[J].交通運輸系統(tǒng)工程與信息,2014,14(2):102-107.

[5]張洪海,胡明華.CDM ADGDP 機場容量與時隙協(xié)同配置[J].系統(tǒng)工程理論與實踐,2010(10):1901-1908.

[6]PYRGIOTIS N,ODONI A.On the impact of scheduling limits:a case study at newark international airport[EB/OL].(2013-01-25)[2015-05-06].http://dx.doi.org/10.1287/trsc.

[7]VAZE V,BARNHART C.Modeling airline frequency competition for airport congestion mitigation[J].Transportation science,2012,46(4):512-535.

[8]經(jīng)飛,王釣,李軍,等.基于吱呀輪優(yōu)化的多衛(wèi)星數(shù)傳調(diào)度問題求解方法[J].宇航學(xué)報,2011,32(4):863-870.

[9]徐肖豪,于躍,黃寶軍,等.基于 ISWO 的機場進離場航班優(yōu)化排序研究[J].計算機仿真,2014,31(7):63-67.

[10]PARZEN E.On estimation of a probability density function and mode[J].Annals of mathematical statistics,1962,33(4):1065-1076.

[11]萬元,黃翔.SIMMOD 仿真模型在浦東國際機場飛行區(qū)中的運用[C]//上海機場建設(shè)指揮部.上海空港(第5輯).上海：上?？茖W(xué)技術(shù)出版社，2007:27-32.

中圖分類號：U8

文獻標志碼：A

收稿日期：2015-06-06

作者簡介：楊新湦(1966-),男,天津人,教授,碩士,碩士生導(dǎo)師,主要研究方向為空中交通管理和樞紐機場.

基金項目：國家自然科學(xué)基金項目(71571182);教育部人文社科青年基金項目(14YJC630185)

文章編號：1672-6871(2016)03-0019-05

DOI:10.15926/j.cnki.issn1672-6871.2016.03.005