突發(fā)事件下大規(guī)?？罩薪煌髁抗芾淼慕M合優(yōu)化模型

王莉莉，王航臣

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

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

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

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

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

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

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

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

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

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

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

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

1)航路和航線

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

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

2)機(jī)場(chǎng)節(jié)點(diǎn)和航路交叉點(diǎn)

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

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

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

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

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

3)高度層

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

4)空中與地面等待

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

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

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

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

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

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

1.2 ATFM中航路航線選擇的費(fèi)用問題

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

1.2.1 航路航線運(yùn)行費(fèi)用

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

(1)

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

(2)

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

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

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

(3)

(4)

1.2.2 突發(fā)事件費(fèi)用

1)危險(xiǎn)天氣

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

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

(5)

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

(6)

若以-lnRij作為中間機(jī)場(chǎng)節(jié)點(diǎn)(i-j)費(fèi)用的一部分，則可將天氣因素考慮到實(shí)際運(yùn)行中。

2)軍航活動(dòng)

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

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

情況1計(jì)劃最短航路航線時(shí)，必須飛越某節(jié)點(diǎn)。

情況2計(jì)劃最短航路航線時(shí)，不能飛越某節(jié)點(diǎn)。

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

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

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

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

2 短期流量管理模型

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

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

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

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

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

(7)

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

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

min:Zh(x)=CostH

(8)

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

(9)

2.2 約束條件

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

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

(10)

(11)

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

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

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

(12)

雖然表述改為扇區(qū)容量約束，但第1個(gè)目標(biāo)函數(shù)，即式(7)中需要使用各航路流量衡量費(fèi)用函數(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)對(duì)航空器到達(dá)扇區(qū)的時(shí)間做了約束。

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

(20)

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

(21)

3 求解算法設(shè)計(jì)

3.1 算法設(shè)計(jì)思路

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

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

3.2 軍航活動(dòng)下的最短路算法

對(duì)于情況3，是情況1和情況2的組合。

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

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

3.3 模型的求解算法

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

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

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

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

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

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

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

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

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

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

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

4 仿真算例

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

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

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

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

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

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

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

1)場(chǎng)景1的實(shí)現(xiàn)與驗(yàn)證

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

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

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

2)場(chǎng)景2的實(shí)現(xiàn)與驗(yàn)證

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

圖6 延誤分配Fig.6 Delay distributions

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

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

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

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

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

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

3)場(chǎng)景3的實(shí)現(xiàn)與驗(yàn)證

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

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

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

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

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

5 結(jié) 論

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

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

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

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

致 謝

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