突發事件下大規模空中交通流量管理的組合優化模型

王莉莉，王航臣

中國民航大學 天津市空管運行規劃與安全技術重點實驗室,天津 300300

民航局空管局近些年對“通行能力”的研究十分關注，其核心問題是可用高度層如何分配，從而達到滿足交通需求、最優配置空域資源的目的。通行能力的研究體現了空域管理者對空域中運行交通流的優化調配，是空中交通流順暢運行的重要保障。目前容量評估的理論已趨于成熟[1]，但通行能力常常達不到評估出的容量。究其原因，一方面中國空域遼闊，各地天氣情況復雜多變，特點不同；另一方面，中國的兩大空域用戶——軍航和民航在對于空域時空資源利用方面，需求存在重疊。因此有必要研究空域在危險天氣與軍航活動下的通行能力，從而使得軍民航能夠高效、公平地得以利用空域資源，達到提升空域運行效率的目的。

在空中交通流調度與通行能力的研究中，很多學者從網絡流優化的角度進行建模。1992年，Helme[2]首次在空中交通流量管理(Air Traffic Flow Management,ATFM)中引入了航路容量限制約束。在時間-空間網絡上使用多品種流理論(Multicommodity Flow,MCF)與最小費用流理論來解決航班的空中與地面等待問題，雖然模型簡單且是連續的，但求解較為困難。2000年，Bertsimas和Patterson[3]針對文獻[2]中計算時間復雜度過高的問題從另一個角度——使用動態網絡流理論，構建了一個動態天氣條件下延誤成本最小的數學模型，并使用拉格朗日松弛與拉格朗日生成算法，將MCF問題中的難約束吸收到目標函數中，從而使模型易于求解。程朋等[4]通過動態網絡流理論描述空中航路航線網絡，并通過華北管制區的實際數據進行驗證，該文獻將機場以及與雙向航路相連的管制移交點建模為一對源點和匯點，將航路段之間的中間節點視為沒有流量需求和輸出的導航臺節點。而在實際運行中，中間節點中包括機場節點，這些節點常常有飛機起飛與降落，需要進一步的對這些節點進行刻畫。2009年，趙嶷飛[5]以《圖論》中的網絡優化方法抽象了空中交通網絡，建立了短期ATFM的動態網絡流模型，首次提出了流量控制事件的概念。Odoni等[6-7]結合整數規劃的方法，以扇區容量、機場節點容量和扇區連接度等因素為約束，并以歐洲空域作為算例進行仿真。2014年，Nosedal等[8]針對ATFM計算規模大、計算耗時長所造成的諸如危險天氣等突發事件對航班計劃影響大的缺陷，提出了一種高效率的算法，通過調整局部的航班計劃從而減少空域的延誤與擁擠，提升運算效率。2016年，Kicinger等[9]將危險天氣視為一種隨機因素，探討了固定機場容量在不同天氣輸入下的通行能力。在MCF模型的求解方面，寇瑋華等[10-11]做了一系列工作，通過構建復合參數和復合指標，分別討論了容量有差異與容量無差異下的求解方法，但設計的求解算法都是針對單目標的。

綜上，已有的文獻主要存在以下不足：① 將航路航線網絡抽象為圖后，對中間節點的刻畫存在不足。一方面，如果中間節點是機場則有流量進入和流出，不能單純的將中間節點都抽象為沒有流量進出的導航臺點；另一方面，通行能力受限于空中交通態勢，所以中間節點不能僅包括導航臺點，也需要考慮航路交叉點(如某些強制報告點)。② 只考慮了單一突發事件下的流量調配，且不能很好地反映空域航路網路的擁擠程度隨時間和流量變化的特點。③ 空中交通網絡與《運籌學》中高度抽象的網絡及其他運輸方式的網絡存在明顯差別，主要體現在4個方面：一是模型復雜，由于空中交通流調度是在不同高度層進行的，空中交通網絡是個多層次的網絡；二是缺乏成熟理論的支撐且航路網出現擁擠時產生的費用(即飛行成本)考慮的因素與其他交通網絡不同[12]，為貼近民航運輸的情況，在構建優化模型時需要用到網絡流理論、動態規劃理論等；三是數據量大，許多繁忙空域日流量過千，如中國的航路樞紐——周口(ZHO)日均流量在1 200架次以上；④ 計算復雜度高，許多空中交通網絡的建模是非線性的[12]，求解算法很難找到多項式時間的解，如何在可接受的時間求得符合要求的解，也是空中交通網絡流優化的難點之一。

針對前面提到的4點不足，做出了以下改進。

1)針對第①點，將存在交叉的航路點都考慮進中間節點中，并將中間節點分成有流量進出的節點(機場節點)和無流量需求的節點，對有流量進出且具有中間節點性質的點進行拆分處理：分為3個子節點，分別是作為源發出流量的節點，作為匯接收流量的節點，以及轉運流量的中間節點。并分別對源節點和匯節點進行建模，刻畫了兩種節點空域出現擁擠時的空中等待與地面等待。

2)針對第②點，建立了多目標規劃模型，將航空危險天氣和軍航活動都考慮入模型中。

3)針對第③點，使用MCF對空中交通網絡進行建模，將多高度層抽象為兩節點間的多條邊，通過費用函數動態反映航路相對擁擠程度，并通過設計近似算法降低算法求解的時間復雜度，從而滿足流量調配的時間約束。

1 突發事件下交通流量管理的問題描述

1.1 空域的數學描述

由于中國空域現行的高度層配備原則是“東單西雙”，所以可以將中國的空域網路抽象為連通有向圖G=(V,E,S，Costij)[13]，其中：V為機場、導航臺點和航路交叉點的集合;E為航路和航線的集合;S為扇區集合，飛機經過的扇區Sf∈S；Costij為兩點間的費用。

但空域網絡與網絡流理論中高度抽象的網絡不同，有許多自己的特點，如擁擠程度隨流量變化，中間的機場節點有流量進出，存在高度層變化，空中與地面等待需要在網絡中進行刻畫等。

1)航路和航線

每一段航路和航線都可以用有向弧表示，如圖1表示節點i,j之間的雙向航路。由于擁擠程度(隨流量變化情況)和可靠程度(隨危險天氣變化情況)不同，各航路的費用會存在差別，所以這是一個費用有差異的問題。

圖1 航路和航線的抽象描述Fig.1 Abstract description of air route and air way

2)機場節點和航路交叉點

文獻[4]將航空網絡中節點分為源節點、匯節點和中間節點。在實際的管制運行中，中間節點中的機場節點有流量發出和進入的情況普遍存在，這類情況用簡單的源、匯和中間節點概括會使得模型不滿足實際運行的要求，同時也會違背流量守恒約束，因此有必要對中間節點進行劃分。本文劃分為有流量需求的中間節點Ea∈E和無流量需求的轉運節點Enav∈E。這種劃分能夠去除文獻[4]中假設2，即“正常情況下飛行流量從源點傳送到匯點的過程中總流量值沒有損耗”。

除此之外，航路的容量受限于航路交叉匯聚情況和空中交通態勢，所以建模時中間節點的選取的節點不再僅是文獻[4]中的導航臺點，還包括航路交叉點(如某些具有交叉和匯聚的強制報告點)。

機場節點是有流量進出的中間節點，但很多機場節點又具有中間節點的性質，不能簡單地使用拓撲結構進行抽象。故可根據以上特點，將機場節點分為3個子節點，分別是作為源發出流量的節點，作為匯接收流量的節點，以及中間節點轉運流量。原理如圖2所示，將有流量進出的機場節點A拆成了源節點A1、中間節點A2和匯節點A3。

圖2 有流量需求節點的處理Fig.2 Processing of traffic demand nodes

無流量需求的中間節點滿足流量守恒約束，不需要做特殊處理。對于多起訖點與拆分后造成的多起訖點可以使用《運籌學》中的經典方法，添加虛擬節點轉化為單起訖點問題。

3)高度層

文獻[5]將同一航路上m個不同高度層的航路抽象成網絡圖中m條邊，原理如圖3所示。本文使用同樣的方法構建航路航線網絡的高度層。

4)空中與地面等待

在空域發生嚴重擁堵時，飛機抵達機場，而機場容量不足，將會出現飛機在空中的盤旋等待。通過推遲飛機起飛時間，將成本較高、風險較大的空中等待(Air Holding,AH)轉變為地面等待(Ground Holding,GH)，是短期ATFM中常用的策略[14]。無論是空中還是地面等待，都會發生在機場節點，故可將源節點與匯節點做進一步的細化。原理如圖4所示，由于2)中已將網絡中所有節點拆分成源節點、匯節點和中間點，所以可以分別對其進行建模。源節點只存在離場交通流，若不存在延誤，可以直接由節點i至節點j；若存在擁擠，需要進行地面等待，則從i至GH，再進入節點j。同理，對于匯節點，若可以直接降落，則從節點i到節點j，若需要空中等待，則從節點i至節點AH，再至節點j。

圖3 不同高度層航路的簡化表示Fig.3 Representation of routes at different height levels

圖4 機場模型Fig.4 Airport model

5)機型差異問題

跑道上前后機型組合的不同會對跑道的容量和安全間隔產生影響，本文將機型劃分為大型機(H)、中型機(M)和小型機(S)來計算機型成本，3種 機型對機場節點的影響差別較大，有必要針對以前的研究中將空中交通流視為一種流的假設做出改進，使用MCF分別描述3種機型。

由于儀表間隔的限制，任一時間各機場節點能降落和起飛的飛機數量都是有限制的，機型的分布對這些機場節點的通行能力有較大的影響，為了描述這一問題，建模時應考慮機型分布的影響。機型分布建模中，由于到達某機場的飛機機型是隨機分布的，可采用離散概率分布建模。用大型機、中型機和小型機占所有航班計劃的百分比，表示該機型到達的概率，設空中交通流中大型機、中型機和小型機所占百分比分別為p1、p2和p3，且p1+p2+p3=1。

1.2 ATFM中航路航線選擇的費用問題

經典運籌學方法在研究流量分配時，將交通網絡理想化，即假設網絡上不存在阻塞現象，每條邊的費用固定，這種假定適用于小流量下的交通網絡，但對于大流量且存在阻塞現象的交通網絡，計算的結果不符合一線運行。在實際的管制運行中，?i,j∈V,航路航線的費用Costij隨著流量的增加遞增，管制員分配流量時也會在“多條航路和航線”之間權衡選擇。影響管制員路徑選擇的因素主要有航路航線的運行費用(衡量各時段流量變化帶來的影響)、空中與地面等待的成本、危險天氣帶來的影響和軍航活動。

1.2.1 航路航線運行費用

由于國內外文獻缺少對航空網絡“擁擠程度”的定義，所以引入“相對擁擠”這一概念來平衡和分配空中交通流量，即在向最小費用的通路分配流量后，其路徑費用會由于新增流量而不再是最小的，下一次迭代要重新衡量“相對擁擠”的程度。文獻[15]首次針對航路和航線的費用函數進行建模，本文使用相同的費用函數來表示航路航線網絡“相對擁擠”的程度變化情況：

(1)

除了航路航線的費用，由1.1節中所述，航路航線網絡中的機場節點還存在AH節點與GH節點，對于兩種等待也應賦予費用函數。在空域出現擁擠時，通過比較從源節點到匯節點的總費用與地面等待、空中等待的費用，從而決定是否采用地面等待策略。AH每單位時間的成本遠比GH的高，假設每架航空器的延誤應該是“平等的”。因此，可在目標函數引入成本系數ε，使之變為一個略微超線性函數。引入成本系數將有利于航班延誤分配的適度性與公平性，從而不會出現延誤分配嚴重不均的情況。空中等待亦然，引入空中等待的成本系數ε2，并令其大于地面等待系數ε1，從而實現AH每單位時間的成本遠比GH的高的約定。引入兩個參數的原因是使目標函數進行近似變換，整體考慮空中等待與地面等待，從而克服Lulli和Odoni(2007年)提到的流量管理模型“公平性不足”的問題[6]。

(2)

式中：TDf=AHf+GHf為航班f的總延誤。

如果目標函數僅表示為最小化AH與GH之和，則與已有文獻分開考慮并計算AH與GH沒有區別。經過式(2)的變換，目標函數考慮到了總延誤TD。使用總延誤作為目標函數不僅具有能夠有效區別空中等待與地面等待費用的優點，還能夠克服引言中提到的大多數模型將空中延誤費用和地面延誤費用分開計算的缺陷，這樣設置目標函數求得的結果是從系統的角度進行考慮的，充分地考慮了兩者之間的相互影響。

綜上，等待費用由兩部分組成，第1部分考慮航班的總延誤，第2部分則是起飛前采用地面等待所節省的費用。故針對每個時刻t，設af為航班f的計劃到達時間，df為航班f的計劃離場時間，定義下述費用系數：

(3)

(4)

1.2.2 突發事件費用

1)危險天氣

1.2.1節中的費用函數沒有考慮天氣因素帶來的可靠性變化。天氣是對民航運輸影響最大的因素之一，表現在終端區航空器進離場受到延誤和航班取消等、空域扇區內航空器為避開危險天氣改航，從而導致航路通行能力降低。為了給空中交通網絡流提供最可靠的路徑，需要考慮航路和機場節點兩個方面的重要度。

衡量路徑可靠性主要有兩種準則：鏈條準則和串聯準則[18]。兩種準則表現在航路網絡中有不同的意義：在鏈條準則下，如果航路都經過某一機場節點，并且它的可靠度在航路集合的所有節點中是最低的，則這些航路具有同樣的可靠度，故以鏈條準則表示航路可靠度難以區分各航路的差別；而在串聯準則下，考慮到連接航路的各機場節點對航路可靠性都有影響，則能以可靠度串聯的乘積形式表現出各航路的區別。為了描述航空危險天氣的隨機性，航路的可靠度可定義為

(5)

式中：RPa為整條航路a的可靠度；Rij為航路(i-j)∈Pa的可靠度，Pa表示由源節點到匯節點的一條由航路組成的通路。為了便于求解，可將式(5)兩邊取以e為底的對數，得

(6)

若以-lnRij作為中間機場節點(i-j)費用的一部分，則可將天氣因素考慮到實際運行中。

2)軍航活動

隨著中國國防建設與民航事業的持續發展，軍民航防撞的任務日益艱巨，軍航活動對于民航飛行與空管保障會帶來一系列影響，如部分航路航線的關閉、民用機場短時禁航、改變民用飛機計劃航路和航線等。軍航活動與危險天氣帶來的影響不同，危險天氣會造成通行能力的下降問題，但軍航活動會造成一切飛行活動的避讓，一旦發生，將會出現部分節點和航路航線不可使用的問題。所以在建模過程中，軍航活動不體現在費用函數上，而是體現在最短路徑的選擇上。

在對各航路進行配流時，需要先迭代計算最小費用，搜索最短路，所以軍航活動帶來的影響具體可以表征為

情況1計劃最短航路航線時，必須飛越某節點。

情況2計劃最短航路航線時，不能飛越某節點。

情況3計劃最短航路航線時，必須經過某節點但不能經過某節點。

情況4計劃最短航路航線時，經過某節點就不能經過另一節點。

情況5計劃最短航路航線時，經過某節點就必須經過另一節點。

綜上所述，在搜索最小費用的航路分配流量時，需要充分考慮這些因素，從而得到軍航活動下民航飛機的調度方案。

2 短期流量管理模型

短期流量管理模型中的變量如表1所示。

表1 模型中所用變量Table 1 Parameters in model

2.1 目標函數

短期流量管理的目標通常是使空中等待與地面等待的損失成本總和最小，但由于實際管制運行中出于安全和成本考慮，只將地面等待作為目標函數。但由1.2節的分析，航路的費用、空中等待與地面等待的費用和危險天氣帶來的費用都需要考慮，有多于一個要追求最優的目標。

第1個優化目標是使航路網絡總費用最小，可表述為各航路費用之和最小，則優化目標可表示為

(7)

式中：為了區分飛行任務的重要程度，引入一個非0的權重系數λm，大型機活動的重要系數大于1，中型機和小型機的重要系數小于1。

第2個優化目標是使空中等待與地面等待的成本最小。目標函數可寫為

min:Zh(x)=CostH

(8)

第3個目標是使危險天氣對航路航線網絡的影響最小，即飛行計劃與調度飛機時路線的可靠性最好，可表示為

(9)

2.2 約束條件

1)機場的進離場容量約束

不同的跑道使用策略下機場容量不同，機場的進離場約束可表示為

(10)

(11)

式(10)表示時刻t起飛的航空器架次小于機場的離場容量，式(11)表示時刻t起飛的航空器架次小于機場的進場容量。跑道容量的確定方法在很多文獻里已有詳細的介紹，如文獻[19]，在此不再贅述。

2)扇區容量約束

文獻[4]的容量約束是航路容量約束，但空中交通與地面交通不同，空中交通航路/航線的容量是以扇區為單元表述，故可將容量約束表述為扇區容量約束：

(12)

雖然表述改為扇區容量約束，但第1個目標函數，即式(7)中需要使用各航路流量衡量費用函數的變化。可表示為

(13)

3)航班的連續性約束

(14)

(15)

(16)

4)扇區的連續性約束

(17)

(18)

(19)

式(17)～式(19)表明扇區的連接性，式(17)約定一架航空器如果截至時刻t-lfj′j沒有抵達扇區j之前的某一扇區，那么截至時刻t，航空器也無法到達扇區j；式(18)和式(19)對航空器到達扇區的時間做了約束。

5)非負與整數約束

(20)

截至t時刻，空中交通流量是一個非負整數變量，即

(21)

3 求解算法設計

3.1 算法設計思路

在求解MCF這一問題上，經典算法主要有拉格朗日松弛法、列生成法和Dantzig-Wolfe分解等，其他常用的算法還有將MCF問題視為容量指派問題[20]。這些算法面臨的一個重要問題是算法求解的時間復雜度高，而短期ATFM的時間敏感度高，在大流量的調度問題上難以滿足短期ATFM的需要。前面提到的文獻不能滿足上文中提到的網絡費用隨時間和流量變化的特點，也不能準確描述軍航活動給網絡帶來的影響。

由于危險天氣具有隨機性，各地氣象臺能對危險天氣做出概率預測，故以其為輸入數據之一；航路費用隨流量的變化而改變，而流量又有明顯的時變性，故各時段的流量也是輸入數據之一；一切飛行活動都要避讓軍航活動，所以軍航活動會造成部分點和邊不可用，本文通過修改最短路算法來描述軍航活動帶來的影響。

3.2 軍航活動下的最短路算法

對于情況3，是情況1和情況2的組合。

對于情況4，主要包含3個過程：第1個過程是將G轉變為不包含經過某節點的新圖，搜索其最短路；第2個過程是將G轉變為不包含不能經過某節點的新圖，計算出必須經過某節點的最短路徑；第3過程是對兩個求解出的最短路取最小。

對于情況5，主要包含3個過程：第1個過程是將G轉變為不包含經過某節點的新圖，計算其最短路徑；第2個過程是對G計算出起點到經過某節點的最短路，計算出經過某節點到必須經過某節點的最短路徑和必須經過某節點到終點的最短路徑，再將3個最短路合并；第3個過程對比第1和第2過程，取其小。

3.3 模型的求解算法

步驟2更新費用。將分配得到的流量加載進航路網絡，根據流量分配結果更新式(1)的費用，根據氣象報文MATAR更新式(6)的費用，從而得到新的航路費用。

步驟3判斷是否有軍航活動。如有則進行步驟4，否則進行步驟5。

步驟4根據3.2節中情況，調用對應的改進Dijkstran，n=1,2,3,4,5，計算最短路。

步驟7列出目標列表。建表過程參見文獻[21]。

步驟8給定初始約束集。令x1=x。

步驟9計算權系數δp。

步驟10求解輔助問題，輔助問題的構造參見文獻[21]，可得輔助問題的最優解(xp,λp)。

若對所有目標均滿意，則輸出Z*=ZM。

若對所有目標都不滿意，或M=3時仍有一些目標不滿意，則無滿意解，停止迭代。

若M<3，對目標Z表示滿意，進行步驟12。

步驟12由管制單位根據天氣與空域擁擠程度，給出最大寬容量，作新的約束集合。

4 仿真算例

將西南空管局所管制的空域作為算例對模型與算法的可行性和求解效率進行分析。先以2016年11月28日的實際數據為例進行初步驗證。仿真選取該區域的6個機場節點，包括成都雙流機場(ZUUU)、重慶江北機場(ZUCK)、綿陽南郊機場(ZUMY)、昆明長水機場(ZPPP)和麗江三義機場(ZPLJ)和貴陽龍陽堡機場(ZUGY)。該空域除了機場，包含23個扇區，973條邊，88個節點(沒有交叉的不計入)，日均流量超過300架次的繁忙節點有10個，如圖5所示。這些節點對網絡的通行能力有較大影響，應重點分析。

圖5 流量超過300架次的節點Fig.5 Nodes with more than 300 flights

為了驗證不同情況下模型的運算效果，分別構建3種不同的場景進行仿真。

場景1西南地區空域不受天氣和軍航活動影響，正常運行，即所有路徑可靠度均為1，沒有節點禁航。

場景2由于航空危險天氣的出現，導致通行能力下降，將扇區的通行能力分為5檔，即20%、40%、60%、80%和100%，分別計算不同通行能力下模型對AH與GH的分配，氣象條件見參數設定段。

場景3由于軍航活動的出現，導致部分節點短時間禁航，分別選取大流量節點(日均300架次以上)和小流量節點(100架次以下)，在考慮天氣影響的情況下，分析不同流量級別節點禁航下對網絡通行能力的影響。時間采樣以min為單位。

模型參數具體設定為，在可接受離場延誤為 15 min、進場延誤為10 min時，設各個扇區的容量均為10架次，ZUUU和ZUCK高峰小時保障架次為40架，其他機場均為25架，流的品種數m=3。為了模擬氣象條件的動態變化，使用計算機生成隨時間變化的氣象信息，且其在同一時間窗內不發生變化，在實際的運行可根據該地區歷史天氣數據進行標定，設3種機型進近著陸所占的比例分別為40%、35%和25%。

1)場景1的實現與驗證

任何一個ATFM模型的重要原則都是保證延誤分配的公平性[7]，但過于保證公平性會導致系統運行效率的降低。本文提出的引入參數ε1和ε2從來整體考慮到總延誤TD，能有效克服這一矛盾。模型中使用的目標函數，其略微超線性的成本系數和對于總延誤的考慮，使得模型可以相對均勻地分配延誤，從而避免大量延誤“堆積”，由后續航班承擔的情況，從而保證了模型的公平性。

作為說明，圖6比較了延誤的分配。橫坐標表示受影響的航班編號，按延誤時間(縱軸)升序排列。實線表示本文設定的目標函數分配得到的延誤，虛線段表示GH與AH簡單線性求和作為目標函數時延誤的分配。可見，考慮總延誤時，受影響的31架航空器延誤可以更加均勻地進行分配。

在完成實際數據初步驗證后，通過改變輸入流量，驗證固定容量但不同的通行能力下的仿真。

2)場景2的實現與驗證

由表2可知，兩個機場每架飛機的平均延誤隨著通行能力的下降，逐漸升高。但由于模型中將空中等待的成本設置的比地面等待成本高很多，故在延誤分配中，地面等待分配的時間也高于空中等待。

圖6 延誤分配Fig.6 Delay distributions

表2 延誤分配結果Table 2 Results of delay assignment

如果按照傳統方法，簡單的將AH與GH線性求和作為目標函數，將延誤飛機的延誤時間按升序排列后，會出現類似圖7的結果，出現延誤的“堆積”，這一點流量越大越明顯。以大流量低通行能力進行分析，即512架次與1 024架次，通行能力20%為例，如圖7所示，如果以傳統的AH與GH簡單線性求和作為目標函數，后續的航班的等待時間較長，這將導致大量航班取消。以240 min為限，超過此時限航空公司需要向乘客支付延誤補償。可見，相比于以往很多文獻將AH與GH加權求和，所提目標函數能均勻地分配延誤，提升流量調配的公平性。

圖7 延誤超過240 min的飛機數量對比Fig.7 Numbers of aircraft delayed more than 240 min

在算法效率方面，通過CPLEX軟件求解模型，算法運行環境為1臺CPU為Intel Core i5-4590 3.30 GHz*2，4 GB內存的臺式計算機。在算例給出的空域結構下進行仿真，短期ATFM時間敏感度高，要求在短時間內得到可靠解。算例設置的總求解時間長度為120 min，流量管理階段的時間窗為0～120 min，通過求解的時間與迭代次數對本文提出的算法與經典算法進行比較，分別將其他幾種算法與逐步寬容算法相結合。

由于列生成算法和Dantzig-Wolfe分解算法通常針對的是單目標而且有特殊結構的優化問題，故僅在算法步驟5中使用這兩種算法求解第一個目標函數，且令λf=0，列生成算法以最短路算法為子問題。運算結果見表3。

表3 算法求解性能分析Table 3 Algorithm performance analysis

3)場景3的實現與驗證

由圖5可知，算例空域的關鍵節點有10個，這10個關鍵節點有不同的特點。主要分為以下2種情況。

1)大流量節點和小流量節點相鄰，MASRO和KHP就屬于這種情況，其中MASRO的日流量達到357架次，而KHP的日流量只有58架次。

2)大流量和大流量節點相鄰，如WFX和JTG，兩者日流量均在300架次以上。

前文提到的參數w表示飛機是否經過某一航路，也可以之判斷飛機是否改航。以MASRO、KHP、WFX和JTG為例，使用改航的飛機數來衡量這兩種情況對航空網絡運行造成的影響。如圖8所示，當大-大流量節點相鄰時，一旦節點禁航，改航的飛機數最多；大-小節點相鄰大節點禁航次之，小節點禁航改航的飛機最少。

圖8 不同關鍵節點造成的改航飛機數Fig.8 Number of aircraft rerouting caused by different key nodes

5 結 論

根據中國民航管制運行特點，對容量與通行能力的概念進行了界定，并使用MCF理論，建立了突發事件下空中交通流調度的動態網絡流模型，并針對多品種動態網絡流模型求解時間復雜度高的特點，改進了逐步寬容約束法，設計了一種階段式求解的逐步寬容算法。

在模型建立方面，通過引入0-1變量衡量航路網的連通程度與航空器的改航問題；考慮了大型機、中型機與小型機交通流的尾流差異，將飛機性能問題轉變為一個MCF問題，并對各品種流量引入權重系數，從而在優化中體現優先大型機活動、保障中型機正常運行的宗旨。在目標函數方面，針對危險天氣的隨機性、網絡擁擠程度隨流量和時間變化的特點、空中等待和地面等待建立了多目標規劃模型；在約束條件方面，考慮了機場容量、航路容量和時間上的連接性。

在模型求解方面，針對軍航活動的特點，改進了最短路算法，針對傳統算法求解MCF時間復雜度高的問題，改進了逐步寬容約束法，提出一種階段式求解的近似算法。

算例結果表明，所改進的模型與提出的算法能夠在危險天氣和軍航活動下，高效地求解多品種流下大規模空中交通流量分配問題，相比于傳統算法在大流量下更具效率優勢。優化的效率與結果更符合航路網絡的運行特點。

致 謝

感謝崔德光教授，作者從崔老師處獲益良多。