多機場時空資源公平分配協同進場調度策略*

王　湛　吳　藝　萬莉莉

(南京航空航天大學民航學院　南京　211100)

?

多機場時空資源公平分配協同進場調度策略*

王湛吳藝萬莉莉

(南京航空航天大學民航學院南京211100)

分析終端區內進場航班各延誤措施特性，以協同決策(collaborative decision making，CDM)理論為基礎制定相應的分配策略調度進場航班，在降低延誤時間的前提下重點提高機場之間時空資源使用公平性，兼顧管制員工作負荷.運用模糊自修正多目標粒子群算法(fuzzy self-correction multi-objectives particle swarm optimization，FS-MOPSO)進行仿真計算.計算結果顯示2機場的30架進場航班調度延誤時間較傳統先到先服務(FCFS)方案減少16.54%，2機場航班延誤差值從單一以延誤最優遺傳算法仿真結果的115 s降低至31 s，較大程度提高了各機場進場航班調度時空資源分配的公平性，并實現公共進場定位點航班均衡分布，提高多機場終端區資源利用有效性.

航空運輸；多機場航班調度；延誤分配；模糊自修正多目標群算法；時空資源使用公平性；協同決策

0　引　　言

多機場系統是指具有2個或2個以上的機場群，機場之間運行具有一定的相關性，具體表現為機場群終端區時空資源之間的耦合關聯[1].因此，合理調度多機場終端區航班，優化進離場航班運行是我國空中交通流量管理亟需解決的問題之一.

國內外對該問題的研究主要集中在調度方法的改善和排序模型的改進，調度方法上，主要有基于機場的先到先服務排序法(APFCFS)和基于定位點的先到先服務方法(MFFCFS)[2]，2種方法主要依據先到先服務原則，在一定程度上保證了航班調度的公平性，但是容易引起空間資源的浪費；在排序模型上，S?lveling等[3]提出將容量利用率加入到航班排序模型，對多機場運行的時空影響進行分析，有效地減少了終端區內擁堵情況，張洪海[4]對從容流平衡的角度出發，建立了多機場終端區協同容流調配模型，張妍等[5]分析了定位點和跑道雙重約束，建立了以延誤最優的為目標的優化模型，并利用Lingo進行求解，Cynthia等[6-7]利用先到先服務原則制定了均衡公平性和功效性的多機場終端區航班管理策略，馬園園等[8-9]引入多元受限時間窗理念，綜合考慮移交間隔、尾流間隔、多跑道運行間隔等約束限制建立多機場終端區進場航班協同排序模型.上述所建模型和調度方法在提高終端區運行效率上有所成就，但沒有綜合考慮機場、航空公司、管制單位三方利益優化航班調度，缺少對多機場系統中各機場對時空資源公平分配的研究.

針對上述分析，文中將主要對多機場系統進場航班調度過程中時空資源進行分析，通過各種進場航班延誤措施的合理分配來實現多機場區域時空資源優化調度，以延誤時間最小和各機場對時空資源的使用公平性為優化目標進行建模求解.模糊自修正多目標粒子群算法(FS-MOPSO)充分考慮了各粒子自身的性能，改善了傳統粒子群算法的過早收斂、局部最優的缺陷[10]，在多機場終端區多目標進場航班調度問題上具有可用性.

1　問題描述與建模

多機場區域不同機場的航班主要分享的時空資源集中在進場定位點處，在此類定位點處航班流量將受到尾隨間隔的控制，產生延誤并傳播至各機場；在高峰流量時期，為了保障樞紐機場的運行效率，常常會為樞紐機場航班優先分配空域資源，導致周邊機場航班產生過多延誤.因此，文中主要尋求多機場終端區各機場之間進場航班協同調度方法.具體描述為：終端區Nm個機場的n架航班等待進場，要求在確保安全的條件下，通過Nr個定位點降落到Nm個機場跑道上，為各跑道上的航班確定降落次序和時間，并通過延誤措施的分配均衡各機場之間時空資源的使用，降低總延誤同時兼顧管制員工作負荷.

1.1變量定義

決策變量定義

1.2目標函數

1) 延誤最小多機場終端區進場航班運行定位點和跑道是互相影響的排序口，航班在跑道上的降落次序為最終輸出隊列，因此目標函數將以航班目標到達跑道的時間與預計到達時間差值絕對值作為多機場進場航班延誤值進行優化.

(1)

2) 時空資源公平分配多機場終端區各機場之間航班運行相互影響，主要表現在：(1)共用進場定位點時對尾隨間隔的控制將引發各航班延誤并傳播到機場；(2)高峰流量期間，各航路交通流匯聚過程中，為了保障樞紐機場的運行效率，將對其航班優先分配空域資源，影響周邊機場航班進場，產生過多延誤；(3)相鄰機場之間飛行程序的相互影響，終端區內共用扇區、航路點因此本場飛行程序將受到鄰場飛行程序的限制.

基于上述分析，以整個航班調度過程中各機場航班平均延誤差值最小為優化目標.

(2)

3) 管制員工作負荷最小管制員工作負荷以終端區內航班調度過程中改變著陸次序航班架次衡量，因此降低終端區內管制員工作負荷實質上是最小化改變次序的航班架次.每一次調度過程中航班調整總架次見圖1.

圖1　第x次優化改變位置航空器架次計算流程圖

需盡量減少航班調整架次，則目標函數如下.

(3)

式中：x為排序次數.

1.3約束條件

1) 時間窗約束保證航班f必須在指定的時間區間內飛過定位點AFr，或降落到跑道RWm.

2) 安全間隔約束主要包括航空器飛過定位點時需要滿足航空器之間尾隨間隔約束，降落在跑道上時需要滿足尾流間隔約束.

(6)

(7)

3) 最大可吸收延誤約束在多機場終端區航班運行過程中，航空器從任意定位點r到機場m的跑道需要滿足終端區內最大可吸收延誤約束.

(8)

4) 最大位置交換約束在排序過程中，航空器被調配后在隊列中的位置與先到先服務隊列中的位置的差異不得超過某一規定的值MPS,以保證管制員工作負荷.

(9)

5) 同股流不超越約束由于終端區內航空器飛行過程復雜，管制壓力大，一般規定在終端區內飛行的航空器在同航路飛行時不得超越.

i≠j,si=sj

(10)

6) 延誤措施選擇約束多機場終端區內存在多個公共航班進近點，航路航線交叉等復雜狀況，因此需要根據航班所處位置決定延誤措施的選擇.

Gm(f)=1

(11)

(12)

航班在相鄰定位點組成航段上不可執行盤旋等待.

(13)

航班在可執行盤旋等待的航段上，至多可以執行一次盤旋等待，且該航班的延誤值需不小于執行一次盤旋等待的延誤值.

(14)

航班在相鄰定位點組成的航段上可不執行延誤措施，或只能執行能執行調速、雷達引導，以及兩者混合方式的一種，航班延誤值需小于最大可吸收延誤值.

上述約束見圖2.

圖2　延誤措施選擇約束示意圖

對不同機場而言：A，B，C, D點為不同機場的公共進近定位點，飛往不同機場的航班沿航路AB，BC，BD飛行至C，D點后沿各自進場航線實施進近.根據約束條件5可知，航路AB段要求過點次序一致，BC和BD段不要求一致，但在該四個公共進場定位點需要滿足尾隨間隔約束條件.

對其中某一機場分析，如機場1，共存在兩條進場航路s11和s12：s11={A,B,C,E,RWm1}，即航路s11包含參考點A,B,C,E；s12={A,B,D,E,RWm1}，即航路s12包含參考點A,B,D,E，根據約束條件5可知，飛往機場1的航班在CE和DE航段不要求過點次序一致，E點之后需要滿足尾流間隔約束，并不許超越.

粘液腺囊腫需要與血管瘤、早期粘液表面樣癌和粘液腺癌相區別。血管瘤是一種閉合性腔隙，受到壓力時血液進入血管，體積可縮小，色澤變淺，觸診無波動感，刺穿內容物為血性。早期粘液表面樣癌和粘液腺癌多發生在腭、頰粘膜以及上唇等部位，通常基底與周圍組織粘連，較硬，存在實質性腫塊。粘液腺囊腫具有以下幾點特征：

根據上述分析，圖2可執行盤旋等措施的航段為：BC,BD,CE,CF,DE,DF.其余航段只能執行調速、雷達引導，以及兩者混合方式的一種.

2　調度方法和算法設計

2.1基于延誤分配的進場航班協同調度方法

第一步根據上述優化模型和約束條件計算航班排序結果，并分析各機場累計航班延誤值和該機場每架航班平均延誤值.

第二步依據各延誤方式的特征和每架航班的延誤值進行延誤方式分配.

5) 否則，Gm(f)=1.

第三步根據上述延誤方式的分配結果對航班預計著落時間重新調整，并根據飛行過渡時間生成公共進場定位點可用時間窗，模型進行新一輪排序.

第四步，對上述排序結果進行目標驗證，若達到優化目標，則結束，否則轉第一步.

2.2模糊自修正多目標粒子群算法運算步驟

模糊自修正多目標粒子群算法(FS-MOPSO)通過引入模糊推理機制，建立各粒子適應度值隸屬度函數.每次尋優，計算各粒子的適應度隸屬度值來確定各粒子下次尋優時對應的慣性權重值，使得每次尋優過程中粒子可以依據各目標函數和約束條件來完善粒子本身性能，提高全局搜索的能力來避免陷入局部最優.由于多維變量的約束難以滿足，算法引入自調整罰系數加快算法的收斂性.算法的具體運算步驟如下.

1) 初始化粒子群P針對多機場終端區進場航班排序問題的特點，以APFCFS確定的航班初始位置作為粒子群P中每個粒子的目標向量.

2) 確定模糊隸屬度函數多機場終端區進場航班協同排序優化模型以延誤值最小、各機場之間時空資源使用公平性以及管制負荷為目標，屬于有僅有上限的多目標期望，隸屬度函數采用降半形，并使用降半Γ分布，建立的隸屬度函數為

(15)

式中：gmin為粒子在滿足約束條件下的歷史最小值；g為粒子當前值，u∈(0,1]

3) 修正慣性權重該算法各粒子的慣性權重采用不斷更新的形式，主要基于模糊自修正策略利用上述隸屬度函數值修正慣性權重.慣性權重的大小決定了粒子的搜索性能，權重值大則相應的搜索性能較優，權重值小則反之.為了保證粒子的搜索性能，權重值應屬于[0.4 0.9]，因此采用以下方式對上述隸屬度函數值進行修正：

(1) 如果uxi∈[0.4,0.9]，則慣性權重值為

(16)

(2) 否則，慣性權重值保持不變，即

(17)

4) 引入自調整罰系數引入罰函數處理文中部分約束難以完全滿足的問題，提高算法的收斂速度和精度.在求解多機場進場航班調度問題時，采用的罰系數調整策略為

(19)

式中：η為約束因子，保證罰系數不小于0；ei(x)

為粒子i在第x次尋優時候與約束條件的最大值和最小值的偏差.

3　仿真計算

對上海虹橋機場和浦東機場的機場航班調度進行仿真模擬，選取的數據來自于文獻[8]共30架航空器.進場航空器最小尾流間隔和尾隨間隔依據ICAO規定的標準.SASAN和AND是ZSSS和ZSPD的共用進場定位點.設MPS=4，采用Matlab2009編程構建，Cell工具將模型程序分步.模型最大位置交換數MPS=3，最大慣性權重wmax為0.9，最小慣性權重wmin為0.4，學習因子c1、c2為2，最大迭代次數xmax為100.仿真得到最優調度方案，并與APFCFS和延誤最優調度方案對比分析，結果見表1，其中用陰影部分標出的航班數據為ZSPD機場的進場航班，非陰影部分數據為ZSSS機場進場航班.

表1　仿真結果比較

由表1可知，在降低延誤水平方面：基于延誤方式分配的多機場進場航班調度策略可以降低總延誤時間，相對于APFCFS排序結果而言，總延誤時間降低了16.54%.圖3為累積延誤曲線圖，反映出該調度方法延誤增加相對緩慢，并且隨著航班數量的增加，該方法將更加有效地提高多機場終端區航班進場效率；在多機場終端區時空資源使用公平性方面：基于延誤方式分配的多機場進場航班調度方法大大減少了兩機場之間航班延誤差值，從APACFS的180 s和遺傳算法優化結果的115 s降低至31 s.圖4為不同策略下多機場進場航班調度對比，由圖4可知，該策略下公共進場定位點SASAN和AND航班分布較均衡，而APFCFS和延誤最優調度策略下存在部分時段兩定位點特別是通過航班架次較多的SASAN點過分擁擠或者空缺的情況；在管制員工作負荷方面，在仿真過程中通過控制MPS值保證不會過多增加管制員工作負荷.

圖3　航班累計延誤值

圖4　不同策略下多機場進場航班調度對比

4　結 束 語

文中以協同決策(CDM)理念為基礎，根據各延誤方式的特點建立了基于延誤方式分配的多機場進場航班調度策略，重點分析終端區內各機場時空資源調度公平性建立了多目標優化模型，并利用模糊自修正多目標粒子群算法仿真.研究表明：策略能在保障管制安全的條件下，降低延誤時間，盡可能最小化各進場航班平均延誤差值，提高各機場進場航班調度時空資源分配的公平性，并實現公共進場定位點航班均衡分布，提高資源利用效率.之后將研究多機場終端區進離場結合調度提高終端區時空資源公平分配策略.

[1]COONS T. Temperature errors &altimeters or d-values: who cares[J]. Flying Safety, 2000,23(10):4-7.

[2]程傲.珠三角地區多機場放行時隙分配策略研究[D].南京:南京航空航天大學,2013.

[3]S?LVELING G, CLARKE G P. Scheduling of airport runway operations using stochastic branch and bound methods[J] Transportation Research Part C, 2014,45：119-137.

[4]張洪海.機場終端區協同流量管理關鍵技術研究[D].南京:南京航空航天大學,2009.

[5]張妍,胡明華,張穎.多機場終端區進場航班排序模型研究[J].航空計算技術,2013,43(3):20-25.

[6]BARNHART C, BERTSIMAS D. Equitable and efficient coordination in traffic flow management[J]. Transportation Science,2012,42(2):262-280.

[7]HANCERLIGULLARI G, RABADI G, ALSALEM A H, et al. Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem[J]. Journal of Air Transport Management,2013,32:39-48.

[8]馬園園，胡明華，張洪海，等.多機場終端區進場航班協同排序方法[J].航空學報,2014,35(10):1-12.

[9]胡明華，馬園園，田文，等.復雜終端區進場交通流優化排序方法研究[J].南京航空航天大學學報,2015,47(4):459-466.

[10]周任軍,李紹金,陳瑞先,等.采用模糊自修正粒子群算法的碳排放權交易冷熱電多目標調度[J].中國電機工程學報，2014,34(34):6121-6126.

Collaborative Arrival Aircrafts Scheduling Strategy Aimed at Common Resources Utilization Fairness in Metroplex Terminal Area

WANG ZhanWU YiWAN Lili

(DepartmentofCivilAviation,NanjingUniversityofAeronauticsandAstronautics,Nanjing211100,China)

The characteristics of every delay measure are analyzed to develop an allocation strategy to schedule arrival aircrafts collaboratively based on Collaborative Decision Making (CDM). On the premise of minimizing the total delay, this strategy focuses on enhancing the fairness of using the common airspace resources among different airports and reducing the ATC workload. FS-MOPSO (fuzzy self-correction multi-objectives particle swarm optimization) is used for the simulation. The simulation results indicate that the total delay time is reduced by 16.54% compared to the traditional strategy FCFS (First come first service); the difference between the average delay time of the two airports decreases from 115 s to 31 s compared to the results from genetic algorithm aiming at minimizing the delay time only, which shows that the strategy could reduce the difference between the average delay time of every airports as far as possible to enhance the fairness and to make the flights arrive at the common fix evenly and to improve the efficiency of the resource utilization.

air transportation; aircrafts scheduling in metroplex; delay allocation; FS-MOPSO; the fairness of common airspace resources utilization; CDM

2016-06-22

V355

10.3963/j.issn.2095-3844.2016.04.004

王湛(1982- )：女，博士后，講師，主要研究領域為空中交通流量管理、軟件性能保持

*江蘇省自然科學基金項目資助(Bk20130821)