面向?qū)嶋H運(yùn)行的戰(zhàn)略航班時(shí)刻優(yōu)化技術(shù)

柯雨辰， 胡明華， 楊 磊， 趙 征

(南京航空航天大學(xué)民航學(xué)院， 南京 211106)

航班時(shí)刻既是民航運(yùn)輸業(yè)重要的資源，也是航空運(yùn)輸企業(yè)的立足之本。同時(shí)，作為治理延誤和實(shí)施空中交通流量管理最重要的基礎(chǔ)數(shù)據(jù)，尋找一個(gè)合適的角度對其進(jìn)行優(yōu)化，可以在機(jī)場需求管理中起到事半功倍的效果。Zografos等[1]以最小化申請時(shí)刻和實(shí)際分配時(shí)刻之間的差異為目標(biāo)，提出了一種可以對整個(gè)航季優(yōu)化的航班時(shí)刻優(yōu)化模型；Jacquillat等[2]提出一種綜合方法，共同優(yōu)化機(jī)場在戰(zhàn)略層面的航班時(shí)刻表和戰(zhàn)術(shù)層面的機(jī)場容量利用率；Corolli等[3]考慮了航空公司運(yùn)營偏好以及機(jī)場網(wǎng)絡(luò)結(jié)構(gòu)，提出了一種兩階段的隨機(jī)規(guī)劃模型對時(shí)隙進(jìn)行分配；Pellegrini等[4]提出了一種模型，應(yīng)用國際航空運(yùn)輸協(xié)會(huì)現(xiàn)有的規(guī)則和做法，能同時(shí)在所有歐洲機(jī)場分配航班時(shí)刻；Zografos[5]等針對單機(jī)場開發(fā)并解決了一種同時(shí)考慮效率性和公平性的雙目標(biāo)時(shí)隙分配模型；王飛等[6]以航班正點(diǎn)率、旅客延誤時(shí)間、延誤成本、基尼系數(shù)等目標(biāo)的不同組合為優(yōu)化目標(biāo)建立航班時(shí)刻優(yōu)化模型；羅亮[7]建立了基于航路資源分配的航班時(shí)刻優(yōu)化模型；裴一麟[8]考慮航空公司收益，對航線網(wǎng)絡(luò)和航班時(shí)刻建立了雙層規(guī)劃模型；汪夢蝶等[9]提出可接受調(diào)整水平的概念，建立了基于功效性和可接受性的雙目標(biāo)航班時(shí)刻優(yōu)化模型；李昂等[10]以京津冀機(jī)場群為研究對象，構(gòu)建提升航班正點(diǎn)率的航班時(shí)刻優(yōu)化模型。

上述研究從航空公司偏好、效率性和公平性等具有現(xiàn)實(shí)意義的角度出發(fā)，在降低延誤、緩解機(jī)場擁堵方面取得了一定的成果，但沒有結(jié)合航班起降后的實(shí)際運(yùn)行情況進(jìn)行優(yōu)化。現(xiàn)將停機(jī)位、跑道及終端區(qū)的進(jìn)出走廊口作為一個(gè)系統(tǒng)來研究，將跑道和走廊口看作系統(tǒng)內(nèi)的受限單元，通過滑行時(shí)間和飛行時(shí)間對系統(tǒng)關(guān)鍵節(jié)點(diǎn)建立連接并根據(jù)資源能力限制進(jìn)行約束，從而減少飛機(jī)在跑道頭的排隊(duì)等待時(shí)間以及走廊口因?yàn)榱骺囟斐傻暮桨嘌诱`。

1 問題描述及模型假設(shè)

所要解決的問題可以簡述如下：首先，以停機(jī)位、跑道和終端區(qū)進(jìn)出走廊口構(gòu)成的系統(tǒng)為研究對象；其次，考慮航班在系統(tǒng)中的運(yùn)行流程，計(jì)算航班經(jīng)過跑道和走廊口的時(shí)間節(jié)點(diǎn)，如圖1所示；最后，根據(jù)受限單元的資源能力，即跑道運(yùn)行容量和走廊口通行能力對關(guān)鍵時(shí)間節(jié)點(diǎn)的航班量進(jìn)行限制，在滿足容流匹配的前提下通過小幅度的調(diào)整為每個(gè)航班分配一個(gè)最優(yōu)的起降時(shí)刻，從而提高機(jī)場運(yùn)行效率、降低延誤。

圖1 航班在所研究系統(tǒng)中運(yùn)行流程

在建立相關(guān)模型之前，為了使得問題更嚴(yán)謹(jǐn)求解更方便進(jìn)行如下假設(shè)說明。

假設(shè)1在實(shí)際應(yīng)用中航班時(shí)刻不是一個(gè)精確、具體的時(shí)間點(diǎn)，而是一段特定時(shí)隙。同一機(jī)場時(shí)隙長度相同，通常設(shè)定為5 min。一個(gè)時(shí)隙內(nèi)可以起降多個(gè)航班，即根據(jù)機(jī)場的服務(wù)能力設(shè)定時(shí)隙容量。

假設(shè)2根據(jù)《民航時(shí)刻管理辦法》總則第二條規(guī)定“航班時(shí)刻的時(shí)間基于擋輪擋時(shí)間和撤輪擋時(shí)間”，將某一航班分配到的航班時(shí)刻看作是該航班的輪擋時(shí)間，即機(jī)位時(shí)間。

假設(shè)3將優(yōu)化前航班時(shí)刻表中各公司分配的航班時(shí)刻視作航空公司所申請的即期望獲得的時(shí)刻，并認(rèn)為各公司所能接受的最大調(diào)整量相同。

假設(shè)4本文中考慮的實(shí)際運(yùn)行場景中，跑道運(yùn)行模式的設(shè)定是固定的。各個(gè)航班所分配到的起降跑道根據(jù)走廊口進(jìn)行匹配。

假設(shè)5由于戰(zhàn)略階段在換季航班時(shí)刻表中無法為每個(gè)航班分配具體的停機(jī)位，滑行時(shí)間的計(jì)算從該航班的歷史運(yùn)行數(shù)據(jù)中進(jìn)行挖掘。根據(jù)該航班的歷史停放機(jī)位和使用跑道信息，匹配相應(yīng)的滑行時(shí)間并進(jìn)行平均，取平均值代表該航班的滑行時(shí)間。

假設(shè)6航班在終端區(qū)內(nèi)的飛行時(shí)間，即航班在跑道和走廊口之間的飛行時(shí)間通過仿真軟件模擬運(yùn)行得到。為此選用浦東機(jī)場為研究對象，經(jīng)過仿真得到走廊口和跑道對應(yīng)的飛行時(shí)間如表1所示。

假設(shè)7聯(lián)程航班必須保證有充足的過站時(shí)間上下客和進(jìn)行地面保障服務(wù)，現(xiàn)忽略機(jī)型對模型和算法的影響，對于聯(lián)程航班設(shè)定統(tǒng)一的最小過站時(shí)間。

2 航班時(shí)刻優(yōu)化模型

2.1 決策變量

由于本文模型關(guān)注的是受限單元在各自對應(yīng)的時(shí)間節(jié)點(diǎn)下的容流匹配關(guān)系，為了便于約束條件使用數(shù)學(xué)表達(dá)式進(jìn)行說明，在此設(shè)立三組決策變量，分別與時(shí)間節(jié)點(diǎn)有關(guān)，即

(1)

(2)

(3)

2.2 約束條件

(1)每個(gè)航班只能分配到一個(gè)時(shí)間片，即

(4)

式(4)中；T為時(shí)間片集合，T={1,2，…，Tn}；t∈T；F為所有航班集合，f∈F。

式(4)表示每個(gè)航班在1 d內(nèi)有且只能分配到一個(gè)時(shí)刻，保證沒有航班被拒絕。

(2)每個(gè)航班必須滿足最大調(diào)整量約束，即

|t-tf|≤tmax，t∈T

(5)

式(5)中：tf為航班f原計(jì)劃申請的時(shí)間片，f∈F,tf∈T；tmax為航班的最大允許調(diào)整量。

式(5)表示每個(gè)航班在時(shí)刻分配過程中有一個(gè)最大允許調(diào)整量，是航空承運(yùn)人可以接受的一個(gè)時(shí)刻偏移范圍。

(3)過站航班要滿足最小過站時(shí)間約束，即

(fa,fd)∈P,k∈[tf,h)，t∈T

(6)

式(6)中：fa和fd表示航班為進(jìn)港航班和離港航班；P為過站航班對集合；tad為航班對最小過站時(shí)間；h為時(shí)刻集合中的最后一個(gè)時(shí)刻。

式(6)表示過站航班要滿足最小過站時(shí)長。

(4)跑道運(yùn)行容量限制，即

(7)

(8)

式中：R為機(jī)場跑道集合；Ra為機(jī)場內(nèi)用于進(jìn)場航班的跑道集合；Rd為機(jī)場內(nèi)用于離場航班的場跑道集合；Fr-a為使用進(jìn)場跑道r-a的航班集合，r-a∈Ra；Fr-d為使用離場跑道r-d的航班集合，r-d∈Rd；Cr-a為進(jìn)場跑道r-a的運(yùn)行容量限制；Cr-d為離場跑道r-d的運(yùn)行容量限制;lf為所有航班的滑行時(shí)間集合。

式(7)、式(8)表示分別對進(jìn)場跑道和離場跑道運(yùn)行容量進(jìn)行約束。《機(jī)場時(shí)刻容量評估技術(shù)規(guī)范》中規(guī)定容量評估時(shí)選用的單位為小時(shí)，為了防止出現(xiàn)一小時(shí)內(nèi)流量分布不均，在此設(shè)置容量限制的區(qū)間長度為15 min和60 min。

(5)走廊口通行能力限制，即

(9)

(10)

式中：U為機(jī)場終端區(qū)走廊口集合；Ua為到達(dá)走廊口集合；Ud為出發(fā)走廊口集合；Fu-a為使用到達(dá)走廊口u-a的航班集合，u-a∈Ua；Fu-d為使用出發(fā)走廊口u-d的航班集合，u-d∈Ud；Cu-a為出到達(dá)廊口u-a的通行能力；Cu-d為出發(fā)走廊口u-d的通行能力；lr*u為終端區(qū)飛行時(shí)間集合，r*u表示跑道r和走廊口u之間的飛行時(shí)間，r∈R，u∈U。

式(9)和式(10)根據(jù)走廊口通行能力分別對到達(dá)走廊口和出發(fā)走廊口進(jìn)行容量約束。由于管制單位為了對飛行流量進(jìn)行更加精細(xì)化的管理，對于走廊口通常會(huì)設(shè)置5 min區(qū)間的流量限制，因此設(shè)置走廊口容量限制的區(qū)間長度為5、15和60 min。

2.3 目標(biāo)函數(shù)

本文中研究的優(yōu)化技術(shù)是基于機(jī)場的角度，作為服務(wù)方的機(jī)場應(yīng)當(dāng)盡量滿足用戶即航班承運(yùn)人的需求。因此，在考慮航空公司偏好的前提下，調(diào)整過程中使得優(yōu)化后的航班時(shí)刻盡可能少的偏離航空公司請求的時(shí)刻。從效率性角度出發(fā)，同時(shí)由于多重約束下的調(diào)整難度，以最小化總的航班時(shí)刻偏移量為目標(biāo)函數(shù)，其表達(dá)式為

(11)

3 求解算法及實(shí)例驗(yàn)證

3.1 模型求解算法

為確保容量約束的平滑性和緊致性，設(shè)計(jì)了以5 min為步長的滑動(dòng)時(shí)間窗，以滿足連續(xù)小時(shí)和15 min約束。由于變量空間較大，針對問題規(guī)模的復(fù)雜性，設(shè)計(jì)了面向精確解的高效最優(yōu)化算法，采用MATLAB中的線性整數(shù)規(guī)劃工具箱intlinprog進(jìn)行編程求解。

Step2構(gòu)建系數(shù)矩陣。構(gòu)建目標(biāo)函數(shù)的系數(shù)矩陣，根據(jù)航班可接受的前后最大偏移量建立不等式約束條件和等式約束條件的系數(shù)矩陣，最后將系數(shù)矩陣和變量參數(shù)輸入工具箱進(jìn)行求解。

3.2 算例分析

本文中采用的數(shù)據(jù)來源于《2019冬春浦東機(jī)場班期時(shí)刻表》，以航班量最大的周三為例開展優(yōu)化。需要說明的是，在本文中跑道設(shè)定為北向運(yùn)行，即離場跑道為34L和35R，進(jìn)場跑道為34R和35L，每架航班所使用的跑道根據(jù)走廊口進(jìn)行匹配。統(tǒng)計(jì)表明，在班期計(jì)劃周三這一天，共有計(jì)劃起降航班1 529架次，其中離港航班764架次，進(jìn)港航班765架次。經(jīng)過仿真得到浦東機(jī)場走廊口和跑道對應(yīng)的飛行時(shí)間如表1所示。

航班信息以及優(yōu)化前后的部分航班時(shí)刻如表2所示。優(yōu)化前跑道和走廊口存在超過容量限制的情形，而優(yōu)化后所有跑道和走廊口均能滿足各種時(shí)間區(qū)間長度下的容量限制約束，從而達(dá)到容流匹配的效果。以流量較多的進(jìn)場跑道34R和離場走廊口PIKAS進(jìn)行說明：優(yōu)化前以15 min和60 min為區(qū)間劃分時(shí)間片，34R跑道分別有4個(gè)和3個(gè)時(shí)間片超出對應(yīng)區(qū)間容量限制；優(yōu)化前以5、15和60 min為區(qū)間劃分時(shí)間片，PIKAS分別有9、6、0個(gè)時(shí)間片超出對應(yīng)區(qū)間容量限制；優(yōu)化后，不論是跑道還是走廊口，各時(shí)間片均能滿足容量限制約束。下文對航班調(diào)整情況進(jìn)行具體分析，同時(shí)借助仿真軟件評估優(yōu)化后運(yùn)行效率是否得到改善，以驗(yàn)證模型的有效性。

表1 走廊口飛行時(shí)間統(tǒng)計(jì)

表2 優(yōu)化前后航班時(shí)刻表信息

3.2.1 航班時(shí)刻調(diào)整量分析

以5 min時(shí)間片為單位，將一天劃分為288個(gè)時(shí)間片，航班時(shí)隙最大允許偏移量為1 h，即可以前后移動(dòng)12個(gè)時(shí)間片。進(jìn)行全局優(yōu)化調(diào)整后，共調(diào)整航班295架次，其中進(jìn)港航班127架次，離港航班168架次。圖2是航班時(shí)刻偏移量的分布情況，橫坐標(biāo)是可能的航班偏移量，縱坐標(biāo)是該時(shí)刻偏移量大小對應(yīng)的航班調(diào)整數(shù)目。

圖2 航班時(shí)刻偏移量分布

由圖2可知，時(shí)刻調(diào)整范圍從-50 min跨越至45 min，最大時(shí)刻偏移量的絕對值為50 min，在各公司的最大調(diào)整接受范圍內(nèi)。其中多數(shù)航班的時(shí)刻偏移量集中在柱狀圖的中段位置，說明大部分航班的偏移量較小。進(jìn)一步作出偏移量絕對值的直方圖。如圖3所示，總體來說，約80%的航班僅需前后調(diào)整3個(gè)時(shí)間片(15 min)。眾所周知，時(shí)刻是一種資源且具有一定的價(jià)值，較小的調(diào)整幅度，不僅使得航空承運(yùn)人的偏好得到最大程度的滿足，同時(shí)保障了航班的時(shí)刻利益。

圖3 時(shí)刻偏移量直方圖

3.2.2 基于AirTop的模型仿真驗(yàn)證分析

對優(yōu)化前后的班期時(shí)刻表使用AirTop軟件進(jìn)行仿真驗(yàn)證，作出優(yōu)化前后的平均進(jìn)離場延誤與流量分布圖，如圖4所示。由圖4(a)可知，優(yōu)化前05：00—07：00的離場延誤較為嚴(yán)重，延誤伴隨著航班量的增加而增大，當(dāng)流量增大至趨于穩(wěn)定時(shí)延誤開始遞減，隨即在午時(shí)隨著流量輕微的增加又出現(xiàn)一個(gè)小高峰；進(jìn)場延誤較小且較為穩(wěn)定。由圖4(b)可知，優(yōu)化后各個(gè)小時(shí)的離場延誤變化趨勢和優(yōu)化前相似，但高峰值明顯降低，進(jìn)場延誤仍保持較小，不作討論。

圖4 優(yōu)化后平均進(jìn)離場延誤與流量分布

為了從數(shù)值上更清晰的對優(yōu)化前后的離場延誤變化進(jìn)行比較，將優(yōu)化前后的延誤分布至于同一坐標(biāo)系下，如圖5所示，一天的延誤水平有明顯改善，尤其是高峰延誤經(jīng)過優(yōu)化后大大降低。最后由表1中列出的優(yōu)化前后仿真運(yùn)行指標(biāo)數(shù)據(jù)對運(yùn)行效率進(jìn)行評估。

圖5 優(yōu)化前后離港延誤分布對比

仿真結(jié)果數(shù)據(jù)有力驗(yàn)證了所建立的航班時(shí)刻優(yōu)化模型的有效性。如表3所示，對比優(yōu)化前后，平均離場延誤從6.5 min降低至3.3 min，降低了49%左右；高峰離場延誤從33 min降低為10 min，降低了69%左右；平均滑行延誤從6 min降低為2 min，降低了2/3；平均放行正常率從72.38%增加至81.42%，增加了12%左右。由上述指標(biāo)變化可知，航班運(yùn)行效率得到了極大的改善，尤其是延誤水平顯著降低。因此，本文中所建立的模型是有效的。

表3 優(yōu)化前后運(yùn)行指標(biāo)數(shù)值

4 結(jié)論

以航班時(shí)刻為研究對象，從時(shí)間和空間兩個(gè)維度考慮了航班在所研究系統(tǒng)內(nèi)的實(shí)際運(yùn)行情況，建立了面向?qū)嶋H運(yùn)行的戰(zhàn)略航班時(shí)刻優(yōu)化模型。以浦東機(jī)場班期時(shí)刻表數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證，得到以下結(jié)論。

(1)通過對約20%的航班時(shí)刻進(jìn)行微調(diào)，優(yōu)化后的時(shí)刻表完全滿足了跑道和走廊口的容流匹配限制。

(2)配合AirTop軟件進(jìn)行仿真驗(yàn)證，證明該模型能夠有效降低航班延誤水平、提高放行正常率。

由于本文的優(yōu)化圍繞單機(jī)場展開，在未來研究中，可以將研究范圍擴(kuò)展至終端區(qū)多機(jī)場協(xié)調(diào)問題作進(jìn)一步探討。