王莉莉，王航臣

中國民航大學(xué) 天津市空管運行規(guī)劃與安全技術(shù)重點實驗室,天津 300300

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

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

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

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

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

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

3)針對第③點，使用MCF對空中交通網(wǎng)絡(luò)進(jìn)行建模，將多高度層抽象為兩節(jié)點間的多條邊，通過費用函數(shù)動態(tài)反映航路相對擁擠程度，并通過設(shè)計近似算法降低算法求解的時間復(fù)雜度，從而滿足流量調(diào)配的時間約束。

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

1.1 空域的數(shù)學(xué)描述

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

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

1)航路和航線

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

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

2)機(jī)場節(jié)點和航路交叉點

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

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

機(jī)場節(jié)點是有流量進(jìn)出的中間節(jié)點，但很多機(jī)場節(jié)點又具有中間節(jié)點的性質(zhì)，不能簡單地使用拓?fù)浣Y(jié)構(gòu)進(jìn)行抽象。故可根據(jù)以上特點，將機(jī)場節(jié)點分為3個子節(jié)點，分別是作為源發(fā)出流量的節(jié)點，作為匯接收流量的節(jié)點，以及中間節(jié)點轉(zhuǎn)運流量。原理如圖2所示，將有流量進(jìn)出的機(jī)場節(jié)點A拆成了源節(jié)點A1、中間節(jié)點A2和匯節(jié)點A3。

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

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

3)高度層

文獻(xiàn)[5]將同一航路上m個不同高度層的航路抽象成網(wǎng)絡(luò)圖中m條邊，原理如圖3所示。本文使用同樣的方法構(gòu)建航路航線網(wǎng)絡(luò)的高度層。

4)空中與地面等待

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

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

圖4 機(jī)場模型Fig.4 Airport model

5)機(jī)型差異問題

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

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

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

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

1.2.1 航路航線運行費用

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

(1)

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

(2)

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

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

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

(3)

(4)

1.2.2 突發(fā)事件費用

1)危險天氣

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

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

(5)

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

(6)

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

2)軍航活動

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

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

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

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

情況3計劃最短航路航線時，必須經(jīng)過某節(jié)點但不能經(jīng)過某節(jié)點。

情況4計劃最短航路航線時，經(jīng)過某節(jié)點就不能經(jīng)過另一節(jié)點。

情況5計劃最短航路航線時，經(jīng)過某節(jié)點就必須經(jīng)過另一節(jié)點。

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

2 短期流量管理模型

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

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

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

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

第1個優(yōu)化目標(biāo)是使航路網(wǎng)絡(luò)總費用最小，可表述為各航路費用之和最小，則優(yōu)化目標(biāo)可表示為

(7)

式中：為了區(qū)分飛行任務(wù)的重要程度，引入一個非0的權(quán)重系數(shù)λm，大型機(jī)活動的重要系數(shù)大于1，中型機(jī)和小型機(jī)的重要系數(shù)小于1。

第2個優(yōu)化目標(biāo)是使空中等待與地面等待的成本最小。目標(biāo)函數(shù)可寫為

min:Zh(x)=CostH

(8)

第3個目標(biāo)是使危險天氣對航路航線網(wǎng)絡(luò)的影響最小，即飛行計劃與調(diào)度飛機(jī)時路線的可靠性最好，可表示為

(9)

2.2 約束條件

1)機(jī)場的進(jìn)離場容量約束

不同的跑道使用策略下機(jī)場容量不同，機(jī)場的進(jìn)離場約束可表示為

(10)

(11)

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

2)扇區(qū)容量約束

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

(12)

雖然表述改為扇區(qū)容量約束，但第1個目標(biāo)函數(shù)，即式(7)中需要使用各航路流量衡量費用函數(shù)的變化?？杀硎緸?/p>

(13)

3)航班的連續(xù)性約束

(14)

(15)

(16)

4)扇區(qū)的連續(xù)性約束

(17)

(18)

(19)

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

5)非負(fù)與整數(shù)約束

(20)

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

(21)

3 求解算法設(shè)計

3.1 算法設(shè)計思路

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

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

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

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

對于情況4，主要包含3個過程：第1個過程是將G轉(zhuǎn)變?yōu)椴话?jīng)過某節(jié)點的新圖，搜索其最短路；第2個過程是將G轉(zhuǎn)變?yōu)椴话荒芙?jīng)過某節(jié)點的新圖，計算出必須經(jīng)過某節(jié)點的最短路徑；第3過程是對兩個求解出的最短路取最小。

對于情況5，主要包含3個過程：第1個過程是將G轉(zhuǎn)變?yōu)椴话?jīng)過某節(jié)點的新圖，計算其最短路徑；第2個過程是對G計算出起點到經(jīng)過某節(jié)點的最短路，計算出經(jīng)過某節(jié)點到必須經(jīng)過某節(jié)點的最短路徑和必須經(jīng)過某節(jié)點到終點的最短路徑，再將3個最短路合并；第3個過程對比第1和第2過程，取其小。

3.3 模型的求解算法

步驟2更新費用。將分配得到的流量加載進(jìn)航路網(wǎng)絡(luò)，根據(jù)流量分配結(jié)果更新式(1)的費用，根據(jù)氣象報文MATAR更新式(6)的費用，從而得到新的航路費用。

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

步驟4根據(jù)3.2節(jié)中情況，調(diào)用對應(yīng)的改進(jìn)Dijkstran，n=1,2,3,4,5，計算最短路。

步驟7列出目標(biāo)列表。建表過程參見文獻(xiàn)[21]。

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

步驟9計算權(quán)系數(shù)δp。

步驟10求解輔助問題，輔助問題的構(gòu)造參見文獻(xiàn)[21]，可得輔助問題的最優(yōu)解(xp,λp)。

若對所有目標(biāo)均滿意，則輸出Z*=ZM。

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

若M<3，對目標(biāo)Z表示滿意，進(jìn)行步驟12。

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

4 仿真算例

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

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

為了驗證不同情況下模型的運算效果，分別構(gòu)建3種不同的場景進(jìn)行仿真。

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

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

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

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

1)場景1的實現(xiàn)與驗證

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

作為說明，圖6比較了延誤的分配。橫坐標(biāo)表示受影響的航班編號，按延誤時間(縱軸)升序排列。實線表示本文設(shè)定的目標(biāo)函數(shù)分配得到的延誤，虛線段表示GH與AH簡單線性求和作為目標(biāo)函數(shù)時延誤的分配?？梢姡紤]總延誤時，受影響的31架航空器延誤可以更加均勻地進(jìn)行分配。

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

2)場景2的實現(xiàn)與驗證

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

圖6 延誤分配Fig.6 Delay distributions

表2 延誤分配結(jié)果Table 2 Results of delay assignment

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

圖7 延誤超過240 min的飛機(jī)數(shù)量對比Fig.7 Numbers of aircraft delayed more than 240 min

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

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

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

3)場景3的實現(xiàn)與驗證

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

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

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

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

圖8 不同關(guān)鍵節(jié)點造成的改航飛機(jī)數(shù)Fig.8 Number of aircraft rerouting caused by different key nodes

5 結(jié) 論

根據(jù)中國民航管制運行特點，對容量與通行能力的概念進(jìn)行了界定，并使用MCF理論，建立了突發(fā)事件下空中交通流調(diào)度的動態(tài)網(wǎng)絡(luò)流模型，并針對多品種動態(tài)網(wǎng)絡(luò)流模型求解時間復(fù)雜度高的特點，改進(jìn)了逐步寬容約束法，設(shè)計了一種階段式求解的逐步寬容算法。

在模型建立方面，通過引入0-1變量衡量航路網(wǎng)的連通程度與航空器的改航問題；考慮了大型機(jī)、中型機(jī)與小型機(jī)交通流的尾流差異，將飛機(jī)性能問題轉(zhuǎn)變?yōu)橐粋€MCF問題，并對各品種流量引入權(quán)重系數(shù)，從而在優(yōu)化中體現(xiàn)優(yōu)先大型機(jī)活動、保障中型機(jī)正常運行的宗旨。在目標(biāo)函數(shù)方面，針對危險天氣的隨機(jī)性、網(wǎng)絡(luò)擁擠程度隨流量和時間變化的特點、空中等待和地面等待建立了多目標(biāo)規(guī)劃模型；在約束條件方面，考慮了機(jī)場容量、航路容量和時間上的連接性。

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

算例結(jié)果表明，所改進(jìn)的模型與提出的算法能夠在危險天氣和軍航活動下，高效地求解多品種流下大規(guī)?？罩薪煌髁糠峙鋯栴}，相比于傳統(tǒng)算法在大流量下更具效率優(yōu)勢。優(yōu)化的效率與結(jié)果更符合航路網(wǎng)絡(luò)的運行特點。

致 謝

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