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

楊新湦，齊　莉，翟文鵬

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

?

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

楊新湦，齊莉，翟文鵬

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

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

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

0引言

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

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

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

1模型算法

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

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

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

(1)

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

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

約束條件：

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

(2)

(3)

(4)

(5)

其中：

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

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

(6)

(7)

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

(8)

(9)

其中：

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

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

(10)

其中：

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

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

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

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

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

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

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

2算法仿真

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

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

圖2 機(jī)場進(jìn)離港架次散點(diǎn)圖圖3 機(jī)場起降架次概率分布圖

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

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

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

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

3結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

[5]張洪海,胡明華.CDM ADGDP 機(jī)場容量與時(shí)隙協(xié)同配置[J].系統(tǒng)工程理論與實(shí)踐,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é)報(bào),2011,32(4):863-870.

[9]徐肖豪,于躍,黃寶軍,等.基于 ISWO 的機(jī)場進(jìn)離場航班優(yōu)化排序研究[J].計(jì)算機(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 仿真模型在浦東國際機(jī)場飛行區(qū)中的運(yùn)用[C]//上海機(jī)場建設(shè)指揮部.上?？崭?第5輯).上海：上?？茖W(xué)技術(shù)出版社，2007:27-32.

中圖分類號(hào)：U8

文獻(xiàn)標(biāo)志碼：A

收稿日期：2015-06-06

作者簡介：楊新湦(1966-),男,天津人,教授,碩士,碩士生導(dǎo)師,主要研究方向?yàn)榭罩薪煌ü芾砗蜆屑~機(jī)場.

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

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

DOI:10.15926/j.cnki.issn1672-6871.2016.03.005