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

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

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

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

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

1 問題描述及模型假設

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

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

在建立相關模型之前，為了使得問題更嚴謹求解更方便進行如下假設說明。

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

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

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

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

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

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

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

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

2.1 決策變量

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

(1)

(2)

(3)

2.2 約束條件

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

(4)

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

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

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

|t-tf|≤tmax，t∈T

(5)

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

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

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

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

(6)

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

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

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

(7)

(8)

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

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

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

(9)

(10)

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

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

2.3 目標函數(shù)

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

(11)

3 求解算法及實例驗證

3.1 模型求解算法

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

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

3.2 算例分析

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

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

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

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

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

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

圖2 航班時刻偏移量分布

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

圖3 時刻偏移量直方圖

3.2.2 基于AirTop的模型仿真驗證分析

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

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

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

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

仿真結果數(shù)據(jù)有力驗證了所建立的航班時刻優(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%左右。由上述指標變化可知，航班運行效率得到了極大的改善，尤其是延誤水平顯著降低。因此，本文中所建立的模型是有效的。

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

4 結論

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

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

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

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