基于交叉點復雜度的空域通行能力優(yōu)化方法

馬玲,劉韋廷，王航臣

(中國南方航空股份有限公司北京分公司，北京 102600)

隨著中國民航地快速發(fā)展，機場建設的規(guī)模逐漸增大，機場數量逐漸增多，這導致部分繁忙的終端更加擁擠，空域資源越加緊張。以華北地區(qū)為例，北京終端是中國最繁忙的終端之一，2019年大興機場啟用后，北京空域更加緊張。在早出港的繁忙時段，為了減少延誤，各航空公司時常預先調時、調減航班，這對于機場和航空公司的正常運行都是不利的。所以，對于空域通行能力的優(yōu)化問題，是亟待研究解決的。

中外對于通行能力的研究主要分為終端區(qū)、扇區(qū)、航路和空域。王超等[1]提出了管制員的認知力是航路和扇區(qū)通行能力的主要限制因素，通過分析管制員的認知能力，以改進的蟻群算法為基礎建立了通行能力計算方法。王莉莉等[2-3]通過圖論模型對空域進行建模，討論了危險天氣、軍方活動下通行能力的優(yōu)化問題。王航臣[4]以動態(tài)網絡流為基礎，辨析了容量和通行能力的區(qū)別，并設計了一種階段式分配流量的算法計算空域的通行能力。楊磊等[5]全面總結了空中交通流的概念、特點和建模方法。Wang等[6]為了適應日益增長的空域容量需求，以空域擁擠最小和空中交通復雜性最低為目標，提出了一種新的宏觀交通分配模型，以緩解擁堵并組織空中交通流結構。趙嶷飛等[7]針對空域資源緊張的問題，從水平和垂直兩個維度提出了一種終端區(qū)進場效率的評價方法，并以天津機場為例進行了驗證?？掠瓿降萚8]以空域的容流匹配為目標，建立了航班時刻優(yōu)化模型，優(yōu)化航班的滑行時間和飛行時間。Yin等[9]建立了一個多目標優(yōu)化模型，旨在最小化航班延誤和最大化機場通行能力，以最小間隔、時間窗口、跑道占用和航班周轉為約束建立模型，并通過一種高效的多目標進化算法，利用自適應可控時間編碼和目標引導個體選擇兩種機制，提高了計算性能。Idrissi等[10]通過優(yōu)化飛機在飛行區(qū)的優(yōu)化時間來解決機場通行能力低的問題，通過設計實時算法，在飛機離開停機位和接近滑行網絡沖突點之前，提前檢測并解決沖突。但是上述研究缺少交叉點的建模?？沼虻耐ㄐ心芰Σ粌H受限于管制員的負荷、扇區(qū)容量，也受限于交叉點的容量。交叉點的復雜度對于通行能力有較大的影響。關于交叉點對通行能力的影響分析研究較少。

管制員負荷測量困難?，F有對于管制員負荷的研究中，多借助專業(yè)設備測量獲取的腦電、皮膚電等參數來衡量，使用評價方法進行計算時難以準確量化。求解算法的時間復雜度高。已有研究對于空域的刻畫過于細致，而空中交通流的流動屬于宏觀的模型，這導致計算的時間復雜度高。通行能力的優(yōu)化對于計算的時效性要求高，過長的計算時間不能滿足實際運行的需求。為此，首先針對交叉點缺少建模的問題，分析了航路交叉點對于通行能力的影響，并將影響最大的交叉點流量和交叉數轉化為費用函數，給出了交叉點建模的具體方法；其次，針對管制員負荷測算較為困難的問題，根據空管運行的特點，改進了網絡流模型，將管制員的負荷轉化為扇區(qū)容量、航路容量；最后，針對空中交通流量管理(air traffic flow management,ATFM)問題求解算法時間復雜度高的特點，提出了建模方法，并分析了延誤傳播的特點，以期提升通行能力。

1 問題描述

1.1 空域的抽象方法

文獻[9-10]提出了使用圖論的方法抽象空域計算效果好，兼顧了理論分析和實際運行。因此采用圖論的方法對空域進行建模。

1.1.1 高度層的數學抽象

中國高度層的配置原則是東單西雙，但國內航班常用高度層主要集中在縮小垂直間隔(reduced vertical separation minimum,RVSM)空域的下層，如飛行高度層(flight level,FL)FL291～FL321，通過簡化，可以大幅降低網絡的規(guī)模，從而降低計算的復雜程度，簡化后的高度層如圖1所示。

s表示起始航路點；t表示終止航路點起始點和終止點之間的多個高度層可以抽象為圖中兩個節(jié)點之間的多條邊圖1 簡化后的高度層Fig.1 Simplified height layer

1.1.2 空域和交叉點的數學抽象

在空域的抽象方面，可以對點的集合進行簡化，在計算通行能力時，一些不涉及航路改變的強制報告點和導航臺點可以不進行抽象，只抽象對通行能力有影響的交叉點，這樣可以大幅減小計算時矩陣的規(guī)模，降低矩陣的稀疏性，從而降低由于稀疏矩陣帶來的時間復雜度。另外，以往文獻對于交叉點的刻畫也不夠細致，交叉點inters主要分為三交叉航路點(如交叉點OC)、四交叉航路點(如交叉點VAGBI)、五交叉航路點(如交叉點SQ)、六交叉航路點4種。需要考慮交叉數對通行能力的影響。

fi,1表示經過交叉點的第1股流量fi,2和fi,3分別表示第2股和第3股流量圖2 五交叉航路點的抽象圖Fig.2 Abstract illustration of five crossing waypoints

1.1.3 空域航班運行的數學抽象

在計算通行能力時考慮交叉點，原因在于：無論是在網絡流理論中，還是實際運行中，交叉點的通行能力都容易成為網絡通行能力的瓶頸。在實際運行中，由于交叉點處運行情況復雜，管制員需要花費更多的經歷調配沖突，在出現流量限制時，大多以重要交叉點中心進行限制。

空管發(fā)布的流量限制分為兩種：一是發(fā)布距離間隔，這是空管部門較為關注；二是發(fā)布時間間隔，這是航空公司運行控制部門較為關注的。以2021年9月15日北京區(qū)域發(fā)布的流控信息為例。距離流控：北京時12:20—15:00 經UGOTU 西安管制區(qū)不含以遠高低合算 60 km一架。時間間隔流控：北京時15:30—19:00 北京/首都、北京大興起飛經ESMEB、REVKU 珠海/金灣,深圳/寶安落地40分鐘2架,最小間隔10 min。這兩種流控方式都是以交叉點為核心進行流量控制的，所以空域的通行能力常常受制于交叉點。

(1)

(2)

式(2)中：T為空管的時刻間隔，取60 min；Interv，t為t時刻航班的時間間隔。如流控10 min一架，則Interv，t=10。

計算可得北京兩場在北京時15:30—19:00飛往珠海、深圳的航線容量為21架次。如果時段超容就需要調時、延誤甚至取消航班。

1.2 交叉點的費用函數

已有研究多在構建航路的費用函數[8-10]，但對于通行能力影響最大的因素是管制員的負荷(即空中交通流量)、交叉點的構型和扇區(qū)的容量。所以使用航路阻抗作為整個網絡配流的依據，不夠合理，以交叉點的結構作為費用來進行配流。

計算通行能力時需要考慮管制員的負荷，在運行中管制員負荷最直觀的表現是空中交通流量，因此在設計交叉點的費用時，需要考慮空中交通流量。鏈接交叉點邊的數量也對交叉點的復雜度有重要影響。綜上所述，交叉點費用函數表示為

(3)

在正常運行的情況下，航班按照領航計劃報申請的航路飛行，一般不會改航，只有在出現流量限制時，才可能出現航路航線的變更。即只有在流量控制或通行能力下降時節(jié)點的費用函數才有意義。這樣設置，可以在算法迭代時只更新流控影響航路的費用函數，從而可以大大減小運算規(guī)模，降低算法的復雜度。

2 通行能力優(yōu)化模型

2.1 目標函數的設置

關于通行能力的研究，目標函數一般設定為均衡各時段流量、最小化延誤(網絡費用)、最大化網絡的流量3種。由于通行能力這一概念形成的初衷在于減小延誤，科學指導航空公司調時、調減航班，所以通行能力的優(yōu)化模型類似于最小費用最大流模型，即在整個網絡交叉點復雜度最小的同時，網絡的流量可以達到最大。但兩者又有所不同，最小費用最大流問題中，使用的是邊的費用，且費用固定。而通行能力的計算中，使用的是點的費用，由于流量不同，所以交叉點的復雜度是不斷變化的。綜上所述，目標函數可以定義為

(4)

式(4)中：D為交叉點的復雜度。

2.2 約束條件

建立的通行能力優(yōu)化模型屬于最小費用最大流模型的改進模型，所以首先需要滿足最小費用最大流模型的約束。除此之外，還需要滿足針對通行能力的改進。

2.2.1 流量平衡條件

流量平衡條件屬于最小費用最大流模型中的約束，即流出量等于流入量，具體表示為對于非起飛機場和目的機場的任意兩個航路交叉點?i,j∈V，有

(5)

式(5)中：fij為由航路點i至航路點j的流量；fji為由航路點j至航路點i的流量；V為航路點的集合。

對于起飛機場s，有

(6)

式(6)中：fsj為由起飛機場s至航路點j的流量；fjs為由航路點j至起飛機場s的流量；v(f)為網絡中的可行流，由網絡流理論可知，可行流是一定存在的[9]。

對于目的機場p，有

(7)

式(7)中：fpj為由目的機場p至航路點j的流量；fjp為由航路點j至目的機場p的流量。

2.2.2 空域容量約束

空中交通網絡與地面網絡不同，地面網絡在建模時可以直接套用最小費用最大流中的容量約束，即邊的容量。但空中交通網絡由于航路航線是一種抽象的規(guī)劃，是為飛行員的飛行航跡提供引導的參考?？罩薪煌ǖ娜萘坎粌H受到航路容量的約束，更多的受制于管制員的負荷、扇區(qū)容量和交叉點的容量。由于在建模時，將管制員的負荷和交叉點的容量轉化為了費用函數，所以在模型的約束方面，只需要考慮扇區(qū)和航路的容量約束即可，可表示為

(8)

2.2.3 流控容量約束

民航運行時，簽派員會預先制作飛行計劃，飛機按照規(guī)定的航路飛行，一般不會改變航路。但在出現流控時，通過更改航路，可以達到優(yōu)化通行能力的目的。但在改航時，航路點i至航路點j的容量Cij不能大于流控給出的容量約束，即不能大于時刻約束下的航路容量和間隔約束下的航路容量，可表述為式(9)和式(10)。

(9)

(10)

2.2.4 整數和非負約束

分配的交通流量需要滿足整數和非負約束，即向空中交通網絡中分配的交通流量必須為整數，且不能出現負流量。以f表示交通流量，Z+表示正整數的集合，整數與非負約束可表示為

f∈Z+

(11)

3 求解算法設計

3.1 空中交通網絡延誤的反向傳播特性

在設計算法之前，需要了解在出現流量控制時，空中交通網絡延誤的傳播特性。在出現流量控制或禁航時，會導致部分航路通行能力下降甚至不可使用。這種下降會導致航路網絡結構上產生擁堵，從而導致通行能力的大幅下降。以中國民航局發(fā)布的航行資料匯編(aeronautical information publication,AIP)2017-Nr.13中航路圖部分(enroute chart,ERC)的ERC3蘭州情報區(qū)的部分航圖為例，如圖3所示。W66航路是常發(fā)生限制和禁航的航路，取由西向東運行的3條航路：NUKTI-W66-GOVSA-W66-JNQ-W66-GOBIN-W66-DKO、NUKTI-W66-GOVSA-W66-JNQ-B330-YBL-A596-DKO、NUKTI-V67(假設臨時航路開放)-CHW-V67-YBL-A596-DKO。這3條航路的范圍中，強制報告點NUKTI和GOBIN，VOR/DME合裝臺YBL和DKO都是交叉點。根據1.1節(jié)中的抽象方法，強制報告點ATBUG、GUVSA(僅從上述3條航路來看，下同)，VOR/DME合裝臺CHW可以在抽象為圖時忽略。

對圖3進行抽象前，先定義如下概念。

定義1容差是指某一頂點流入量與流出量的差值，差值為正時是正容差，差值為負時為負容差，即

(12)

定義2負容差網絡是指所有節(jié)點的最大流入量均大于最大流出量的網絡。

按照定義1中的空域抽象準則對圖3進行抽象，只取單一高度層進行說明，抽象后的網絡圖如圖4所示。邊旁邊的數字為航路的容量，單位架次，節(jié)點名稱旁的數字是容差。根據ICAO的規(guī)定，航空器至少間隔5 nm，NUKTI-GOBIN的距離為345 nm，計算可得其航路容量為69架次(不考慮扇區(qū)容量約束和管制員負荷約束，僅用作說明)，其他邊同理。顯然，所選部分的空域是一個負容差網絡。如果航路由東向西運行，就是一個正容差網絡。

YBL為雅布賴；DKO為磴口；其他字母為航路點的五字代碼圖4 抽象后的負容差網絡Fig.4 Negative tolerance network after abstraction

當GOBIN-DKO發(fā)布流量限制時，會導致該段容量減小，從而使GOBIN點的負容差進一步增大，導致網絡延誤的出現，進一步會影響NUKTI-GOBIN的容量，導致再往前流入NUKTI的流量也受到限制。

由此可知，流控可能導致網絡中出現甚至增大負容差，導致通行能力下降以及延誤，并且這種延誤不會向后傳播，而是向前傳播影響之前的交叉點。因此，空中交通網絡的延誤傳播具有反向傳播的特征，需要設計一種能夠考慮反向傳播的算法來優(yōu)化通行能力。

3.2 考慮延誤反向傳播的通行能力優(yōu)化算法

在正常運行的情況下，飛機的計劃航線是固定的，根據領航計劃報申請的航路執(zhí)行。在出現流量控制時，會出現延誤反向傳播現象，此時就需要根據流控信息的限制進行配流，適當改變飛機的計劃航路，從而達到優(yōu)化通行能力的目的。

步驟2計算網絡容差φ。根據流控信息更新航路容量Cij，根據更新后的容量向前計算網絡的容差φ。

步驟4配流。以小時作為時間窗，調用最短路算法向網絡配流fnum，num=num+1。

步驟5更新費用函數。根據網絡中的流量，更新費用函數。

步驟6容量檢驗。網絡中分配的流量需滿足模型中的容量約束[式(9)、式(10)]。如果fij≥Cij，則wi=+∞，剩余流量fij-Cij進入下一次迭代，轉步驟3。

4 算例分析

以華北區(qū)域空域為例。2019年大興機場投入使用后，為了優(yōu)化流量分布，空域結構進行了較大調整。但即使如此，在早出港時期，由于流量過大，為了避免延誤，首都、大興兩場也經常要求航空公司調時、調減航班，具體原理如圖5所示。航班由于某種原因造成容流不匹配導致延誤，此時航班的預計離場時間(scheduled time of departure,STD)要向后推遲，機場所有航班的撤輪擋時間(calculated off block time,COBT)也都需要向后推遲，如果能取消其中一班，其他航班COBT時間都能提前，從而保障STD正常。

圖5 航班調時、調減規(guī)則Fig.5 Flight time adjustment and reduction rules

這種調整雖然可以減少后續(xù)航班的延誤，但如果在出現流量控制時，通過合理的流量分配，減少航班的調時和調減，更有利于機場、航空公司和乘客。

4.1 算例空域特點分析

華北空域的主要管制交接點有APOGO、UGOTU、KAKAT、P240、ESMEB、ONAPI和ANRAT。但這些點涉及的方向不同，其中APOGO是B215航路西北方向的交接點，主要涉及銀川、蘭州、西寧、南線(阿克蘇、庫爾勒、喀什、烏魯木齊)的航班；UGOTU是B215、W43航路西南方向的交接點，主要涉及西安、成都、重慶、昆明、大理、貴陽等的航班；KAKAT是東北、北美方向的交接點，主要涉及長春、沈陽、哈爾濱、鞍山等地的航班。由于篇幅原因，其余節(jié)點方向不再贅述。綜上可知，流控限制是針對某一個方向的限制，很少有針對全方向的限制，所以在優(yōu)化通行能力時，應該分方向進行優(yōu)化。取北京大興國際機場幾個出港關鍵點一周的數據進行仿真，綜合后，每個節(jié)點通過量如圖6所示。

圖6 大興機場主要出港點平均航班量Fig.6 Average flight volume of major departure points at Daxing Airport

由圖6可知，可能產生擁擠的時段主要是北京時間06:00—12:00(后簡稱時段1)，北京時間13:00—19:00(后簡稱時段2)兩個時間段。主要對這兩個時間段進行仿真。

4.2 算例仿真

4.2.1 不同流控等級下延誤時間的優(yōu)化結果

西安管制區(qū)在出現軍事活動和惡劣天氣生成時常常發(fā)布流量控制限制UGOTU的流量，會影響北京首都機場/北京大興機場起飛經ESMEB的航班，從而產生延誤。ESMEB是北京飛往廣深的重要節(jié)點。以這一節(jié)點的流控為例。各種流控等級下的計算結果如圖7所示。其中，優(yōu)化前是指按照原航班時刻執(zhí)行，優(yōu)化后是指按照所提模型和算法計算，實施改航、調時、調減后的執(zhí)行情況。在計算平均延誤時，優(yōu)化前以機場的計劃航班數為除數，優(yōu)化后以經過調整后的航班數為除數。在優(yōu)化前后做對比時，由于需要衡量優(yōu)化后比起優(yōu)化前的效果，所以具體的計算方式為各時段(時段1、時段2)優(yōu)化后的總航班平均延誤時間的同比。

圖7 不同流控等級下的優(yōu)化效果Fig.7 Optimization effect under different flow control registrations

由圖7可知，模型和算法可以取得較好的優(yōu)化效果。京-廣深線這種流量較大的航線，在流控等級較小時，可以將延誤平均時間控制在10 min以內，達到消除延誤的效果(規(guī)定10 min以內不算延誤)，再出現較大的流控時，通過適當的改航，可以達到減小延誤時間的效果，經計算，優(yōu)化后比起優(yōu)化前平均延誤時間減小33.58%。

4.2.2 不同流控等級下受影響航班梳理的優(yōu)化結果

改航、調時、調減都屬于對航班的影響，但影響的效果存在差異。如通過改航避免延誤，對航班的影響最??；其次是調時，調時對航空公司正常運行與旅客出行有一定影響；影響最大的是調減，調減航班航空公司需要簽轉旅客，甚至給予旅客一定的賠償，對航空公司的收益和旅客的出行影響最大。通過上文的優(yōu)化，以時段1，限制為20 min/架為例，改航、調時的航班如表1所示。

表1 改航、調時、調減航班的計算結果(20 min/架)Table 1 Calculation results of flight changes,time adjustments,and flight reductions(20 min/aircraft)

其他計算方法類似，限于篇幅不再贅述。將所有計算結果匯總后，對航班的影響情況如表2所示。

表2 改航、調時、調減航班的計算結果Table 2 Calculation results of flight changes,time adjustments,and flight reductions

通過模型優(yōu)化，大多數航班通過改航來降低延誤，隨著延誤等級的加大，才會逐漸出現調時、調減的航班，這說明模型在出現流控時能夠有效地處理延誤。

4.2.3 算法復雜度對比

算法的測試環(huán)境為Intel i7-6700，計算軟件為Python3.7的Numpy和Networkx庫。在各種流量條件下的計算時間如表3所示。

表3 算法的計算時間Table 2 Algorithm calculation time

由此可見，在高流量等級下模型的運算時間也能夠滿足空管的實際運行。

5 結論

考慮空管實際運行的特點，構建了交叉點的費用函數，并以延誤最小作為優(yōu)化目標，通過流量平衡約束、空域容量約束、流控流量約束建立通行能力的優(yōu)化模型。并根據延誤傳播的特點建立了一種考慮延誤反向傳播的迭代求解算法。最后從不同的流控等級下的延誤時間、受影響航班數量和算法的復雜度3個方面運行進行了仿真。得出以下結論。

(1)所提模型和所提算法在流控較小時可以有效降低延誤。隨著流控的增大，所提模型和算法也能有效地處理改航、調時和調減的比例關系。

(2)所提算法的時間復雜度能夠很好地滿足流控出現時航班的調配。