郭宇帥

（民航局空管局運行管理中心，北京 100022）

隨著國內(nèi)航班量的不斷增長，最初的終端區(qū)規(guī)劃已不能適應當前民航業(yè)發(fā)展需求?？沼蛞?guī)劃不合理會增大管制員在某個扇區(qū)內(nèi)的工作負荷，從而導致扇區(qū)間的管制復雜程度出現(xiàn)不均衡狀態(tài)，會進一步降低航班正常率，影響旅客的出行質量。

終端區(qū)空域規(guī)劃是空中交通管理的重要組成部分。國外對終端區(qū)空域規(guī)劃研究開展較早，Trandac 等[1]針對動態(tài)空域劃分問題，提出一種基于克尼丁算法增益概念的圖劃分啟發(fā)式方法，可在短時間內(nèi)為大規(guī)模實例尋找合理且良好的初始解，但并未從節(jié)點中確定扇區(qū)的確切邊界。Yousefi[2]將美國國家空域分解為3層，然后將空域劃分為航路交通管制中心（ARTCC，Air Route Traffic Control Center），并在每個ARTCC 中繼續(xù)進行分區(qū)，以構建最佳扇區(qū)邊界。Sabhnani 等[3]提出一種利用高度進行三維扇區(qū)劃分的方法，并提出一種符合交通流切割的方法。Gerdes 等[4]提出一種處理非凸空域邊界的劃分方法，并實現(xiàn)了動態(tài)扇區(qū)劃分。國內(nèi)對終端區(qū)空域規(guī)劃研究開展相對較晚。張慧[5]引入飛行航段理論，通過Voronoi 圖對空域進行有限元切割，并對上海終端區(qū)進行了優(yōu)化。賈鏵霏[6]提出一種基于均衡靜態(tài)復雜度的空域劃分方法，并基于西安05 號扇區(qū)進行驗算。寧亞美[7]將扇區(qū)劃分方法總結為Voronoi圖剖分方法和航段劃分方法，并利用太原終端區(qū)對兩種方法進行了算例驗證。高偉等[8]通過譜聚類對太原空域關鍵點進行聚類，并建立了扇區(qū)劃分模型，解決了管制扇區(qū)劃設時協(xié)調負荷過大的問題。

綜上，通過對國內(nèi)外研究發(fā)現(xiàn)，終端區(qū)扇區(qū)動態(tài)規(guī)劃存在未結合實際交通流進離場特性和剖分扇區(qū)未考慮航路點權重等問題。基于以上問題，本研究提出基于改進Voronoi 圖的終端扇區(qū)動態(tài)規(guī)劃研究方法，從結合實際交通流進離場特性與引入關鍵點權重方面入手，通過改進Voronoi 圖水平劃分，運用改進蟻群算法將終端區(qū)管制工作狀態(tài)按時間段分為3 種交通流情況，并對每種交通流情況建立模型，最終建立扇區(qū)動態(tài)規(guī)劃模型，使終端區(qū)扇區(qū)動態(tài)規(guī)劃更符合實際運行情況，可為提升管制工作效率提供借鑒。

1 基于權重的Voronoi 圖

根據(jù)文獻[6]不難發(fā)現(xiàn)，終端區(qū)空域規(guī)劃一般采用Voronoi 圖進行劃分，但Voronoi 圖的原理是將各節(jié)點視為具有相同權重的節(jié)點，即各航路點被視為同等重要，但這種規(guī)劃方式非常不符合實際情況。在空域規(guī)劃中，有的航路點聯(lián)接多條航路，其復雜程度必然高于聯(lián)接航路較少的航路點。因此，將航路點設置為不同權重符合空域規(guī)劃的實際情況，因此，本研究采用基于權重的Voronoi 圖對終端區(qū)進行空域規(guī)劃。

1.1 Voronoi 圖構成

根據(jù)文獻[4]，Voronoi 圖可將二維平面分割為若干個凸多邊形，其基本原理是畫出每相鄰兩個點的垂直平分線，由這些垂直平分線將二維平面分割成為不同的凸多邊形，二維平面上每個點都與其最近的關鍵點有關系。也就是說，該凸多邊形內(nèi)的點到該凸多邊形上關鍵點的歐式距離最近。

一般常用的Voronoi 圖構造方法為對偶生成法，其構造過程為：先找出不共線的相鄰3 點，形成三角剖分；然后基于歐氏距離，對每個三角形上的3 條邊作出其垂直平分線，這3 條垂直平分線便構成了正交中心，這些正交中心便是Voronoi 圖的邊界交點，分割的邊界則為這些垂直平分線，Voronoi 圖結構如圖1 所示。

圖1 Voronoi 圖結構Fig.1 Structure of Voronoi diagram

1.2 關鍵點權重設置

將終端管制區(qū)看作平面，終端區(qū)內(nèi)的航路點看作關鍵點，但每個航路點所聯(lián)接的航路數(shù)量是不相同的，所以每個航路點的重要程度也各不相同。因此，管制員在對航空器進行航空管制時，每個航路點的管制復雜程度也會不同。

故本研究引入權重概念，設平面內(nèi)關鍵點的集合d={p1，p2，…，ph}，其中pk（k = 1，2，…，h）為第k 個區(qū)域塊的關鍵點，pik為Voronoi 劃分區(qū)域第k 個區(qū)域塊內(nèi)的一點，根據(jù)Voronoi 圖的分割性質，可以得出該點距離關鍵點pk小于到其他關鍵點pj，即

D（pik，pk）≤D（pik，pj） j≠k j≠i j=1，2，…，Z

式中：D 表示歐式距離；pj表示pk以外的關鍵點。

設每個關鍵點的復雜程度為qk，k=1，2，…，h，則關鍵點的權重Qk可表示為

根據(jù)式（1）得到關鍵點的權重，則可將相鄰關鍵點的距離由歐氏距離改為權重距離，則權重距離可表示為

本研究將權重引入，將普通Voronoi 圖中的歐氏距離相等改為權重距離相等，設原始三角剖分的邊為e，運用權重距離得到兩相鄰關鍵點的垂直平分線e′，則該垂直平分線e′就是三角剖分的對偶邊，將所有的對偶邊依次相連，從而得到新的凸多邊形。

2 終端扇區(qū)動態(tài)規(guī)劃模型

2.1 目標函數(shù)

從幾何角度出發(fā)，終端區(qū)空域都可以視作不規(guī)則的多邊形，經(jīng)過引入權重的Voronoi 圖處理，可以得到m 個區(qū)域塊。假設規(guī)劃n 個扇區(qū)，那么便可轉化為數(shù)學問題，即如何將m 個區(qū)域塊合理地劃入n 個扇區(qū)集合中。在確定扇區(qū)個數(shù)后，從實際工作出發(fā)，為最大限度均衡各扇區(qū)的管制復雜程度，以各扇區(qū)間管制復雜程度的標準差，建立目標函數(shù)，標準差越小，則各扇區(qū)間復雜程度越均衡，即

式中

式中：Fj表示第j 個扇區(qū)的復雜程度表示n 個扇區(qū)的平均復雜程度；fi表示第j 個扇區(qū)內(nèi)第i 個區(qū)域塊的復雜程度。

在實際工作中，終端區(qū)的進場架次不可能總是與離場架次大致相同，其具體分成3 種情況：離場架次明顯多于進場架次（FD＞FA）、進離場架次數(shù)量基本一致（FA≈FD）、進場架次明顯多于離場架次（FA＞FD）。

為實現(xiàn)各扇區(qū)管制復雜程度相對均衡的目標，當FD＞FA時，應著重考慮離場航線的扇區(qū)劃分；當FD≈FA時，應平衡考慮進場、離場航線的扇區(qū)劃分；當FD＜FA時，應著重考慮進場航線的扇區(qū)劃分。

2.2 約束條件

在實際工作中，設定定量約束條件如下。

1）幾何連通性約束

管制工作扇區(qū)應為一個完整連續(xù)的單元主體，即不能出現(xiàn)中間為2 號扇區(qū)，左右兩側為1 號扇區(qū)的情況，即

式中：ξij為整數(shù)約束，即第j 個扇區(qū)是否包含第i 個區(qū)域塊，若包含則為1，若未被包含則為0；hi為第i 個區(qū)域塊所鄰接的區(qū)域塊集合。

2）幾何唯一性約束

每一區(qū)域塊只能被包含在唯一扇區(qū)內(nèi)，即該區(qū)域塊不能同時被包含于1 號與2 號扇區(qū)內(nèi)，即

3）幾何完整性約束

所有的區(qū)域塊都應被包含在劃設的扇區(qū)內(nèi)，即區(qū)域塊不能未被包含，即

除此之外，扇區(qū)規(guī)劃還應滿足航空器進入扇區(qū)不小于最低飛行時間和避免航空器多次轉換無線電頻率進入不同扇區(qū)，這些約束將作為手動修正的依據(jù)。

3 改進蟻群算法

根據(jù)文獻[9]，蟻群算法具有正反饋性、強魯棒性的優(yōu)點，但該算法收斂速度較慢，不易得出全局最優(yōu)解，為了解決上述缺點，設置動態(tài)信息揮發(fā)參數(shù)。

蟻群算法有以下參數(shù)：信息素參數(shù)α，信息素揮發(fā)參數(shù)ρ，信息素強度Q，啟發(fā)式函數(shù)參數(shù)β 等。

針對于本目標函數(shù)，面向扇區(qū)動態(tài)規(guī)劃的蟻群算法具體步驟如下。

（1）根據(jù)終端區(qū)實際管制工作特點，假設有x 只螞蟻，需要放在x 個離散點上，為實現(xiàn)基于進離港流量分布的終端扇區(qū)動態(tài)規(guī)劃，將分為以下3 種情況確定螞蟻爬行起點：①針對離場架次明顯多于進場架次的情況，螞蟻爬行起點應設置在離場關鍵點上；②針對進離場架次數(shù)量基本一致的情況，螞蟻爬行起點應均勻設置在進離場關鍵點上；③針對進場架次明顯多于離場架次的情況，螞蟻爬行起點應設置在進場關鍵點上。

（2）確定第i 個關鍵點和與之相鄰聯(lián)接的關鍵點Ei，生成鄰接矩陣，1 表示兩點相連，0 表示兩點不相連。

（3）根據(jù)兩點的連通情況得到蟻群禁忌表utab，將該表設為s。

（4）根據(jù)設定，蟻群只會選擇相連的點作為即將前往的下一點，則第x 只螞蟻選擇下一點的概率為

式中：Ax表示第x 只螞蟻選擇下一點的可行集合；τiu（t）表示在第t 次迭代中由點i 到點u 信息素的大?。沪蔵u（t）表示在第t 次迭代中由點i 到點u 螞蟻的啟發(fā)性因素；fu為該關鍵點所在區(qū)域塊的管制復雜程度。

當每完成一次爬行，其信息素更新為

式中

式中：M 表示當前完成的迭代次數(shù)；Tx表示第x 只螞蟻走的下一個關鍵點；E（i，u）為該螞蟻從點i 到點u所經(jīng)過的路線。

傳統(tǒng)蟻群算法中信息素揮發(fā)參數(shù)為固定數(shù)值，這易陷入局部最優(yōu)解，為加快尋找全局最優(yōu)解，故設置ρ值為自適應函數(shù)，即

式中0.3≤ρ≤0.6。

（5）當所有航路點均被x 只螞蟻爬行完成，輸出本輪解。

（6）如果經(jīng)過判斷未達到最初設置的迭代次數(shù)，則次數(shù)加1，轉回步驟（1）繼續(xù)輸出。

（7）根據(jù)不同時間段的動態(tài)進離場分布情況，得到扇區(qū)最優(yōu)動態(tài)規(guī)劃方案。

4 算例分析

4.1 參數(shù)設置

基于2020年8月昆明終端區(qū)管制數(shù)據(jù)，所有數(shù)據(jù)均來自管制自動化系統(tǒng)雷達數(shù)據(jù)。將終端區(qū)內(nèi)航路點看作劃分扇區(qū)的關鍵點，將各點的經(jīng)緯度轉為二維直角坐標系下的點，且坐標系內(nèi)的原點（0，0）為跑道基準點。

基于昆明終端區(qū)歷史航班架次統(tǒng)計數(shù)據(jù)，昆明終端區(qū)2020年8月平均每小時的進離港架次分布，如圖2所示。

圖2 昆明機場平均小時進離港架次分布Fig.2 Distribution of average hourly arrivals and departures at Kunming airport

通過對圖2 分析可發(fā)現(xiàn)：2:00—5:00 時段中，進離場架次明顯偏少，故不予考慮；6:00—8:00 時段屬于離場架次明顯多于進場架次的時段；9:00—21:00 的時段中，進離場架次數(shù)量基本一致，因此將該時段看作進離場均衡的時段；在22:00—次日1:00 時段中進場架次明顯居多。

蟻群算法的參數(shù)設定為：信息素參數(shù)α=1，信息素初始揮發(fā)參數(shù)ρ=0.6，信息素強度Q=20，啟發(fā)式函數(shù)參數(shù)β=1，迭代次數(shù)為100 次，劃設扇區(qū)數(shù)量為5。

如果航路關鍵點所聯(lián)接的航路越多，則該點的管制復雜程度越高，故將各個關鍵點的管制復雜程度數(shù)值設置為其聯(lián)接的航路個數(shù)，如表1 所示。

表1 區(qū)域塊關鍵點復雜程度Tab.1 Complexity of area block key point

4.2 仿真結果

將昆明終端區(qū)的關鍵點坐標數(shù)據(jù)導入Matlab 中，通過基于權重的Voronoi 圖剖分，并把各關鍵點所劃分的區(qū)域塊用序號進行標記，該空域共有19 個關鍵點，故每個區(qū)域塊用序號1～19 表示。各區(qū)域塊的紅點表示關鍵點的所在位置，結果如圖3 所示。

圖3 昆明終端空域剖分結果Fig.3 Dissection result of Kunming terminal airspace

（1）在6:00—到8:00 時段內(nèi)，由于離場架次明顯居多，為了盡可能減少離場航路出現(xiàn)在同一個扇區(qū)內(nèi)，爬行起點選為離場航路關鍵點，該時段扇區(qū)規(guī)劃結果如表2 所示。經(jīng)計算，該時段最優(yōu)劃分結果的均衡程度為1.469 7。

表2 6:00—8:00 時段扇區(qū)劃分輸出結果Tab.2 Sector division output results at time 6:00-8:00

（2）在9:00—21:00 的時段內(nèi)，由于離場架次大致等于進場架次，爬行起點選為昆明終端區(qū)所有關鍵點，該時段扇區(qū)規(guī)劃結果如表3 所示。經(jīng)計算，該時段最優(yōu)劃分結果的均衡程度為0.748 3。

表3 9:00—21:00 時段扇區(qū)劃分輸出結果Tab.3 Sector division output results at time 9:00-21:00

（3）在22:00—次日1:00 時段內(nèi)，進場架次明顯居多，為盡可能減少進場航路出現(xiàn)在同一個扇區(qū)，爬行起點選為進場航路關鍵點，該時段扇區(qū)規(guī)劃結果如表4 所示。經(jīng)計算，該時段最優(yōu)劃分結果的均衡程度為1.326 6。

表4 22:00—次日1:00 時段扇區(qū)劃分輸出結果Tab.4 Sector division output results at time 22:00-next day 1:00

優(yōu)化前后各時段內(nèi)扇區(qū)動態(tài)規(guī)劃得出的復雜程度[9]對比如圖4 所示。

圖4 優(yōu)化前后復雜程度對比Fig.4 Comparison of complexity before and after optimization

從圖4 可看出：優(yōu)化前，1 扇復雜程度最低，4 扇復雜程度最高，分配極不平均；經(jīng)過扇區(qū)動態(tài)規(guī)劃后，5 個扇區(qū)的復雜均衡程度有了極大提高，驗證了模型的有效性。

5 結語

本研究提出一種基于改進Voronoi 圖的終端扇區(qū)動態(tài)規(guī)劃方法。首先，通過引入權重概念，用改進后的Voronoi 圖對終端區(qū)進行剖分，形成了初步的分割模塊；其次，根據(jù)終端區(qū)流量特點，考慮進離流量分布不均的時隙特點，從實際工作出發(fā)構建了扇區(qū)動態(tài)規(guī)劃模型；最后，基于改進的蟻群算法，根據(jù)進離場流量變化情況分別劃分扇區(qū)，通過不同的區(qū)域塊組合方式，達到動態(tài)規(guī)劃扇區(qū)的效果，同時基于昆明終端區(qū)數(shù)據(jù)，驗證了該動態(tài)規(guī)劃模型的可行性與有效性。