基于改進(jìn)Voronoi圖的終端扇區(qū)動態(tài)規(guī)劃研究

郭宇帥

（民航局空管局運(yùn)行管理中心，北京 100022）

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

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

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

1 基于權(quán)重的Voronoi 圖

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

1.1 Voronoi 圖構(gòu)成

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

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

圖1 Voronoi 圖結(jié)構(gòu)Fig.1 Structure of Voronoi diagram

1.2 關(guān)鍵點(diǎn)權(quán)重設(shè)置

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

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

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

式中：D 表示歐式距離；pj表示pk以外的關(guān)鍵點(diǎn)。

設(shè)每個關(guān)鍵點(diǎn)的復(fù)雜程度為qk，k=1，2，…，h，則關(guān)鍵點(diǎn)的權(quán)重Qk可表示為

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

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

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

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

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

式中

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

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

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

2.2 約束條件

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

1）幾何連通性約束

管制工作扇區(qū)應(yīng)為一個完整連續(xù)的單元主體，即不能出現(xiàn)中間為2 號扇區(qū)，左右兩側(cè)為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ū)域塊都應(yīng)被包含在劃設(shè)的扇區(qū)內(nèi)，即區(qū)域塊不能未被包含，即

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

3 改進(jìn)蟻群算法

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

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

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

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

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

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

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

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

當(dāng)每完成一次爬行，其信息素更新為

式中

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

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

式中0.3≤ρ≤0.6。

（5）當(dāng)所有航路點(diǎn)均被x 只螞蟻爬行完成，輸出本輪解。

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

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

4 算例分析

4.1 參數(shù)設(shè)置

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

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

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

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

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

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

表1 區(qū)域塊關(guān)鍵點(diǎn)復(fù)雜程度Tab.1 Complexity of area block key point

4.2 仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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