基于譜聚類的扇區(qū)劃分*

高 偉，陳姝含，葉志堅(jiān)，呂振華

（中國(guó)民航大學(xué)空中交通管理學(xué)院，天津 300300）

0 引言

隨著航空運(yùn)輸業(yè)的不斷發(fā)展，空中交通量持續(xù)增加，有限的民航空域資源要承擔(dān)越來(lái)越多的飛行需求，飛行安全受到威脅的同時(shí)，管制員的工作量也不斷增大［1］。面對(duì)日益飽和的民用航空空域，如何更好地利用空域資源已成為國(guó)內(nèi)外許多學(xué)者和空中交通管制組織關(guān)注的焦點(diǎn)。終端區(qū)交通流密集、空域結(jié)構(gòu)復(fù)雜且存在較多的交叉飛行，因此，終端區(qū)的合理規(guī)劃對(duì)于提高機(jī)場(chǎng)運(yùn)行效率和空中交通的安全性，以及平衡管制員的工作負(fù)荷具有重要意義［2］。

目前國(guó)內(nèi)外許多學(xué)者對(duì)扇區(qū)的劃分和優(yōu)化展開(kāi)了深入的研究，可以對(duì)管制空域以二維、三維以及功能性的形式進(jìn)行劃分，在當(dāng)前階段，研究重點(diǎn)圍繞二維空域［1］。文獻(xiàn)［2］基于終端區(qū)內(nèi)交通流的特征提出了內(nèi)扇功能性的概念。文獻(xiàn)［3-4］在管制空域拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上研究了扇區(qū)優(yōu)化設(shè)計(jì)工作的理論基礎(chǔ)。文獻(xiàn)［5］利用空域的正六邊形分割法，將給定空域分割為六邊形空域單元，并將其作為輸入量輸入TAAM 仿真軟件來(lái)求取管制員工作負(fù)荷。文獻(xiàn)［6］以符合交通流特征為目標(biāo)，利用二進(jìn)制空間劃分法BSP（Binary Space Partition）方法對(duì)民航高空管制空域進(jìn)行劃分，并在模型中加入管制員可選參數(shù)，將交通流的方向、交通流的特征作為扇區(qū)劃分的主要考慮因素。文獻(xiàn)［7］基于空域的內(nèi)部結(jié)構(gòu)與運(yùn)行狀態(tài)，定義了空中交通復(fù)雜度并以此來(lái)衡量管制員的工作負(fù)荷。文獻(xiàn)［8］通過(guò)總結(jié)前人的經(jīng)驗(yàn)，對(duì)動(dòng)態(tài)扇區(qū)劃分作出了調(diào)查研究，并將一天24 h 分為4 個(gè)時(shí)間段，對(duì)時(shí)間點(diǎn)生成過(guò)渡圖來(lái)實(shí)現(xiàn)扇區(qū)的動(dòng)態(tài)劃分。

國(guó)內(nèi)外的研究大多基于管制員工作負(fù)荷和空域復(fù)雜度對(duì)管制扇區(qū)進(jìn)行劃設(shè)。在基于圖論的扇區(qū)劃設(shè)研究中，多數(shù)研究對(duì)關(guān)鍵的航路點(diǎn)進(jìn)行頂點(diǎn)融合后再設(shè)置保護(hù)區(qū)，導(dǎo)致空域結(jié)構(gòu)的過(guò)度簡(jiǎn)化，不僅無(wú)法反映空域真實(shí)結(jié)構(gòu)，還會(huì)產(chǎn)生自相矛盾的結(jié)果。并且以上研究多是以分割的多邊形空域單元為單位進(jìn)行研究，難以全面地反映空域?qū)嶋H情況，不符合實(shí)際需求?；诖耍疚谋Ａ敉暾目沼蚪Y(jié)構(gòu)，將空域結(jié)構(gòu)細(xì)化為航段，全面地反映空域的實(shí)際情況；提出了點(diǎn)的靠近程度并對(duì)航空器航跡進(jìn)行檢測(cè)，對(duì)空域中關(guān)鍵點(diǎn)間的關(guān)系進(jìn)行描述，并建立帶有權(quán)重的空域圖論模型，利用譜聚類算法對(duì)模型進(jìn)行解算；利用voronoi 圖生成扇區(qū)邊界并對(duì)其進(jìn)行幾何修正，最后結(jié)合了一個(gè)實(shí)例對(duì)提出的扇區(qū)劃分方法進(jìn)行了驗(yàn)證。

1 管制扇區(qū)劃設(shè)模型

扇區(qū)劃分的過(guò)程需要考慮諸多因素［9］，如：扇區(qū)對(duì)應(yīng)的空域結(jié)構(gòu)、扇區(qū)內(nèi)航空器狀態(tài)、空域需求以及管制員的工作需求等。中國(guó)民用航空局在《民用航空使用空域辦法》［10］中細(xì)述了扇區(qū)劃分原則。利用譜聚類構(gòu)圖的思想，建立管制扇區(qū)劃設(shè)模型，在進(jìn)行構(gòu)圖時(shí)考慮了扇區(qū)的連續(xù)性原則、扇區(qū)間協(xié)調(diào)移交的限制。

1.1 空域網(wǎng)絡(luò)結(jié)構(gòu)

空域扇區(qū)劃分的必要性主要是由影響交通安全的管制員工作負(fù)荷所決定的。Li［11］等人依據(jù)Eurocontrol 提出的影響管制員工作負(fù)荷的3 個(gè)因素，將管制員工作負(fù)荷量化為：

基于現(xiàn)實(shí)問(wèn)題而假設(shè)的簡(jiǎn)化實(shí)例的空域示意圖如圖1 所示，假設(shè)關(guān)鍵點(diǎn)2 為機(jī)場(chǎng)。

圖1 空域示意圖

1.2 航跡識(shí)別

由于監(jiān)視、運(yùn)行等方面的限制，航跡檢測(cè)半徑r的取值大小會(huì)影響點(diǎn)跡檢測(cè)的結(jié)果，需要根據(jù)實(shí)際情況確定其取值。若r 取值過(guò)大，會(huì)導(dǎo)致以關(guān)鍵圓產(chǎn)生重疊，進(jìn)而使得到的交通量過(guò)大；若r 取值過(guò)小，會(huì)因監(jiān)視設(shè)備的時(shí)間間隔檢測(cè)不到航空器，丟失部分點(diǎn)跡，進(jìn)而使得到的交通量過(guò)小。在進(jìn)行管制扇區(qū)劃設(shè)時(shí)，通過(guò)不斷改變r(jià) 的大小，進(jìn)行大量的劃設(shè)試驗(yàn)，將得到的統(tǒng)計(jì)數(shù)據(jù)與空域內(nèi)總交通量進(jìn)行比對(duì)，認(rèn)為在本文研究的情景下，r 在355.2 m 左右進(jìn)行取值時(shí)，能反映最接近真實(shí)的情況。

1.3 點(diǎn)的靠近程度

文獻(xiàn)［11，13］僅根據(jù)關(guān)鍵點(diǎn)間航空器數(shù)量即管制員的監(jiān)視負(fù)荷作為圖的權(quán)重，由此來(lái)表示圖中點(diǎn)與邊的關(guān)系。這并不能真實(shí)地代表管制員的工作負(fù)荷，且在聚類時(shí)，會(huì)導(dǎo)致航段上航空器數(shù)量相近的邊聚在同一類中，出現(xiàn)扇區(qū)不連續(xù)的情況，這并不符合管制扇區(qū)劃設(shè)的實(shí)際需求。扇區(qū)的連續(xù)性原則示意圖如圖2 所示。

圖2 扇區(qū)連續(xù)性原則示意圖

因此，在描述圖中點(diǎn)之間的關(guān)系時(shí)，不僅要考慮到航段上的監(jiān)視負(fù)荷，還要考慮關(guān)鍵點(diǎn)之間的地理位置關(guān)系。

式（5）為二維空間距離公式，僅用來(lái)計(jì)算空域中航段的長(zhǎng)度，所以不采用三維空間距離公式；其中，x、y 分別代表關(guān)鍵點(diǎn)的橫坐標(biāo)和縱坐標(biāo)，i，j=1，2，…，n。航空器在航路點(diǎn)上通常要向管制員進(jìn)行航空器位置報(bào)告，而兩扇區(qū)的管制員對(duì)航空器的移交需要需要時(shí)間。

其中，lij為兩關(guān)鍵點(diǎn)間的距離；u＞1，可以根據(jù)實(shí)際情況進(jìn)行設(shè)定，目的是強(qiáng)化距離小于8.5 km 的兩關(guān)鍵點(diǎn)之間的聯(lián)系，避免其在聚類時(shí)聚在不同的簇中，使劃設(shè)的管制扇區(qū)滿足協(xié)調(diào)移交的時(shí)間限制。u過(guò)小，達(dá)不到強(qiáng)化的目的；u 過(guò)大會(huì)導(dǎo)致該航段的兩關(guān)鍵點(diǎn)聯(lián)系過(guò)于緊密，在聚類時(shí)有很大概率將其單獨(dú)聚類為一類。

文獻(xiàn)［14］明確指出，若兩個(gè)航路點(diǎn)之間的距離小于8.5 km，那么該航段上不應(yīng)存在扇區(qū)的邊界點(diǎn)；即距離較近的關(guān)鍵點(diǎn)，應(yīng)盡可能地劃分在相同的扇區(qū)內(nèi)，連接航段的兩關(guān)鍵點(diǎn)應(yīng)在同一扇區(qū)中，邊界線應(yīng)盡可能切割距離足夠長(zhǎng)、流量小的航段。不同關(guān)鍵點(diǎn)之間的距離越小，靠近程度越大，關(guān)鍵點(diǎn)的靠近程度pij作為地理信息，反映了空域內(nèi)關(guān)鍵點(diǎn)的靜態(tài)聯(lián)系。

1.4 空域圖關(guān)系的描述

通過(guò)對(duì)關(guān)鍵點(diǎn)位置信息的統(tǒng)計(jì)和航空器航跡數(shù)據(jù)的識(shí)別，分別得到了空域內(nèi)關(guān)鍵點(diǎn)的靜態(tài)聯(lián)系和動(dòng)態(tài)聯(lián)系。關(guān)鍵點(diǎn)之間距離越近，靠近程度越大，靜態(tài)聯(lián)系越大；關(guān)鍵點(diǎn)之間航空器數(shù)量越多，動(dòng)態(tài)聯(lián)系越大。用關(guān)鍵點(diǎn)之間的權(quán)值wij來(lái)描述空域中關(guān)鍵點(diǎn)之間的關(guān)系，

圖1 中標(biāo)注了由式（7）計(jì)算出的假設(shè)空域的關(guān)鍵點(diǎn)之間權(quán)值wij。

2 譜聚類算法及扇區(qū)劃分

對(duì)建立的管制扇區(qū)劃設(shè)模型利用譜聚類算法進(jìn)行聚類，即得到屬于不同扇區(qū)的關(guān)鍵點(diǎn)。借助voronoi圖生成扇區(qū)邊界并進(jìn)行幾何修正，完成扇區(qū)劃分。

文獻(xiàn)［11］沒(méi)有考慮到扇區(qū)間監(jiān)視負(fù)荷的差異；文獻(xiàn)［13］沒(méi)有考慮到協(xié)調(diào)負(fù)荷，且設(shè)計(jì)的算法找不到可行解，不符合管制扇區(qū)劃設(shè)的實(shí)際情況?；诖?，本文利用譜聚類切圖方法，旨在將空中交通的航班量更均衡分配給不同扇區(qū)，同時(shí)還要保證不同扇區(qū)間的航班協(xié)調(diào)移交量盡量小。

2.1 譜聚類算法

譜聚類算法是建立在譜圖理論基礎(chǔ)之上的一種新型聚類算法，它能夠在任意形狀的樣本空間上進(jìn)行聚類，且收斂于全局最優(yōu)解［15］。其基本思想為：首先利用高斯核函數(shù)計(jì)算數(shù)據(jù)之間的歐式距離，并構(gòu)建相似度矩陣，將聚類問(wèn)題轉(zhuǎn)換為圖分割問(wèn)題；再根據(jù)相似度矩陣來(lái)獲取拉普拉斯矩陣，并利用一種連續(xù)的松弛形式將圖分割問(wèn)題轉(zhuǎn)化為拉普拉斯矩陣的譜分解問(wèn)題；最后對(duì)拉普拉斯矩陣建立廣義特征值問(wèn)題，當(dāng)將樣本聚為K 類時(shí)，即取拉普拉斯矩陣前K 個(gè)最小的特征值對(duì)應(yīng)的特征向量，利用經(jīng)典的聚類算法（如K-means 算法）對(duì)其進(jìn)行聚類。

1.4 節(jié)中構(gòu)造的權(quán)重矩陣W 是對(duì)空域中關(guān)鍵點(diǎn)之間關(guān)系的描述，實(shí)際上即為譜聚類算法中的相似度矩陣。對(duì)建立好的空域結(jié)構(gòu)圖論模型執(zhí)行譜聚類算法，譜聚類具體過(guò)程為：

1）計(jì)算度矩陣D：將權(quán)重矩陣W 中同行的元素相加得到度矩陣D，公式為：

2.2 譜聚類切圖

在對(duì)空域內(nèi)的關(guān)鍵點(diǎn)進(jìn)行譜聚類時(shí)，不但要使長(zhǎng)度較短的航段不被扇區(qū)邊界所分割，還要使不同扇區(qū)間關(guān)鍵點(diǎn)的聯(lián)系程度盡可能小。因此，管制扇區(qū)劃設(shè)問(wèn)題的兩個(gè)目標(biāo)是各扇區(qū)內(nèi)的關(guān)鍵點(diǎn)聯(lián)系程度接近和各扇區(qū)間聯(lián)系程度小，分別表現(xiàn)為扇區(qū)間流量的均衡以及總的協(xié)調(diào)負(fù)荷小。實(shí)際上，這是一個(gè)譜聚類Ncut（Normaized cut）切圖問(wèn)題。

再利用K-means 聚類方法對(duì)其進(jìn)行聚類，得到最終的聚類結(jié)果。

譜聚類Ncut 切圖執(zhí)行結(jié)果使得連接不同聚類間邊的權(quán)重之和盡可能小，而同一聚類內(nèi)的邊權(quán)重和盡可能大。這意味著不同聚類之間頂點(diǎn)聯(lián)系程度盡可能小，實(shí)現(xiàn)了切割代價(jià)盡可能小，切割代價(jià)越小，則代表著扇區(qū)間移交航空器需要精力越少，管制員的協(xié)調(diào)負(fù)荷越小；同一聚內(nèi)類頂點(diǎn)聯(lián)系程度越高，則代表這扇區(qū)間的流量越均衡，實(shí)現(xiàn)了管制員監(jiān)視負(fù)荷的差異越小。

圖3 為本文管制扇區(qū)劃分的流程圖。

圖3 管制扇區(qū)劃分的流程圖

圖4 為對(duì)第1.1 節(jié)假設(shè)的空域進(jìn)行譜聚類的結(jié)果示意圖（K=2），其中，實(shí)心圓點(diǎn)和空心圓點(diǎn)表示屬于不同扇區(qū)的關(guān)鍵點(diǎn)。

圖4 譜聚類結(jié)果

對(duì)空域中的關(guān)鍵點(diǎn)生產(chǎn)voronoi 圖，即可得到初步的扇區(qū)邊界。圖5 為voronoi 分扇結(jié)果。

圖5 voronoi 分扇結(jié)果

3 算例分析

譜聚類算法的構(gòu)圖以及切圖思想可以很好地與扇區(qū)劃分的數(shù)學(xué)模型相匹配，是一種專門解決帶有權(quán)重的無(wú)向圖切割問(wèn)題的方法，其在處理稀疏矩陣以及高維度數(shù)據(jù)方面的優(yōu)勢(shì)，使得譜聚類算法很適合用來(lái)解決扇區(qū)劃分問(wèn)題。相較應(yīng)用于扇區(qū)劃分中傳統(tǒng)的聚類方法，該方法有利于在扇區(qū)劃分模型中加入對(duì)管制員的協(xié)調(diào)工作負(fù)荷的考量，有利于不同扇區(qū)間的流量均衡，避免了大協(xié)調(diào)移交量的出現(xiàn)。本文提出的譜聚類算法執(zhí)行劃設(shè)的時(shí)間在15 s 左右，算法的高效滿足了動(dòng)態(tài)扇區(qū)劃設(shè)的實(shí)時(shí)性需求。用該方法，以太原武宿機(jī)場(chǎng)為例，進(jìn)行管制空域的扇區(qū)劃設(shè)，并基于TAAM 軟件，進(jìn)行仿真驗(yàn)證。

3.1 扇區(qū)劃分

選取該地區(qū)某日上午7：00～12：00 的103 架航空器的歷史運(yùn)行數(shù)據(jù)以及空域結(jié)構(gòu)數(shù)據(jù)，利用matlab 軟件繪圖，將航跡數(shù)據(jù)投射在地圖上，得到空域內(nèi)關(guān)鍵點(diǎn)和所有航空器運(yùn)行的點(diǎn)跡，如圖6 所示。

根據(jù)1.1 節(jié)畫(huà)出空域示意圖，結(jié)合空域的邊界以及航路結(jié)構(gòu)，建立關(guān)鍵點(diǎn)和航路結(jié)構(gòu)的無(wú)向圖圖論模型，得到空域結(jié)構(gòu)信息；按照1.2、1.3 節(jié)中提出的方法進(jìn)行數(shù)據(jù)處理，對(duì)航空器點(diǎn)跡數(shù)據(jù)進(jìn)行插值、檢測(cè)得到空域中的動(dòng)態(tài)流量信息，對(duì)關(guān)鍵點(diǎn)位置信息進(jìn)行運(yùn)算，得到空域中的靜態(tài)地理信息；并根據(jù)1.4 節(jié)的式（7），對(duì)空域內(nèi)關(guān)鍵點(diǎn)之間的關(guān)系進(jìn)行描述，即動(dòng)態(tài)信息與靜態(tài)信息的整合，得到權(quán)重矩陣W；再根據(jù)2.2 節(jié)的方法構(gòu)造拉普拉斯矩陣并對(duì)其標(biāo)準(zhǔn)化，按照譜聚類切圖的思想對(duì)關(guān)鍵點(diǎn)進(jìn)行聚類，最后通過(guò)生成voronoi 圖將分扇結(jié)果呈現(xiàn)出來(lái)。

此時(shí)獲得的扇區(qū)邊界線還較為曲折，考慮到扇區(qū)邊界的規(guī)則性，為了避免航空器重復(fù)進(jìn)入同一扇區(qū)的情況，對(duì)于連接不同扇區(qū)的航段，取其中點(diǎn)依次相連，在voronoi 圖基礎(chǔ)上進(jìn)行幾何修正，結(jié)合專家定性分析，適度調(diào)整邊界的走向，然后得到分扇結(jié)果。圖9 為進(jìn)行幾何修正后的最終分扇結(jié)果，修正后的扇區(qū)邊界顯然較未修正的更清晰、更有利于扇區(qū)間的協(xié)調(diào)移交工作。

圖9 最終分扇結(jié)果

3.2 結(jié)果分析

按照本文提出的方法，當(dāng)將空域分為兩個(gè)扇區(qū)時(shí)，關(guān)鍵點(diǎn)4、5、6 和9 屬于同一個(gè)扇區(qū)，關(guān)鍵點(diǎn)1，2，3，7，8，10 和11 屬于另一個(gè)扇區(qū)，此時(shí)總協(xié)調(diào)負(fù)荷小，兩個(gè)扇區(qū)的監(jiān)視負(fù)荷的差異不大，且扇區(qū)邊界與空域中航路結(jié)構(gòu)不會(huì)造成沖突，結(jié)構(gòu)合理。當(dāng)將空域分為3 個(gè)扇區(qū)時(shí)，扇區(qū)間監(jiān)視負(fù)荷的差異與協(xié)調(diào)負(fù)荷均最大，不能將其作為管制扇區(qū)劃設(shè)的方案，分析出現(xiàn)這種情況的原因可能是當(dāng)前太原地區(qū)的空中交通流量還不是很高，兩個(gè)扇區(qū)就能滿足其空中交通流量的需求，分為3 個(gè)扇區(qū)反而會(huì)造成管制資源的浪費(fèi)。

表1 為3 種管制扇區(qū)劃設(shè)方案下對(duì)空中交通量的統(tǒng)計(jì)結(jié)果對(duì)比。

表1 分扇結(jié)果對(duì)比

目前管制扇區(qū)的劃設(shè)雖然不同扇區(qū)的監(jiān)視負(fù)荷相同，但由圖8 可以看出，其存在關(guān)鍵點(diǎn)到扇區(qū)邊界距離過(guò)小的情況，易導(dǎo)致關(guān)鍵點(diǎn)沖突解決工作負(fù)荷和移交工作負(fù)荷增加，且關(guān)鍵點(diǎn)5、6 之間的航段上存在扇區(qū)邊界點(diǎn)，當(dāng)航空器由關(guān)鍵點(diǎn)5 飛至關(guān)鍵點(diǎn)6 時(shí)，存在管制責(zé)任不明確的情況，容易造成管制過(guò)程中扇區(qū)之間頻繁移交，增添額外的協(xié)調(diào)工作負(fù)荷，即空域內(nèi)航路與扇區(qū)邊界存在結(jié)構(gòu)沖突，不符合管制扇區(qū)劃設(shè)的實(shí)際需求。

圖8 太原分扇示意圖

可見(jiàn)在當(dāng)前的流量下，按照本文的方法將空域分為如圖9 的兩個(gè)扇區(qū)時(shí)，管制員的工作負(fù)荷與空域結(jié)構(gòu)都比目前劃設(shè)的扇區(qū)更為合理；若日后流量增大，需要進(jìn)行參數(shù)調(diào)整，同時(shí)考慮劃設(shè)更多的管制扇區(qū)。

3.3 TAAM 仿真

全空域與機(jī)場(chǎng)建模工具軟件TAAM（Total Airspace and Airport Modeller）是一個(gè)從機(jī)位到機(jī)位的快速仿真工具，可以對(duì)空中交通管理過(guò)程進(jìn)行仿真。將太原武宿機(jī)場(chǎng)的基本信息、目前扇區(qū)邊界以及通過(guò)本文方法得到的扇區(qū)邊界輸入TAAM 中，建立空域仿真模型，以同一天的航班時(shí)刻表為基礎(chǔ)進(jìn)行仿真驗(yàn)證，TAAM 輸出的過(guò)扇架次、協(xié)調(diào)負(fù)荷、總工作負(fù)荷以及平均過(guò)扇時(shí)間的仿真結(jié)果如表2所示。由表2 可知，利用本文提出的扇區(qū)劃設(shè)的方法將太原終端區(qū)空域分成兩個(gè)扇區(qū)時(shí)，得到的過(guò)扇架次、扇區(qū)內(nèi)管制員協(xié)調(diào)負(fù)荷以及總的工作負(fù)荷相較于其他兩種情況都更加均衡；其中，仿真得到的過(guò)扇架次和協(xié)調(diào)負(fù)荷，明顯優(yōu)于目前劃設(shè)的管制扇區(qū)，雖然平均過(guò)扇時(shí)間相差接近60 s，可能由此帶來(lái)管制員監(jiān)視負(fù)荷的差異，但反映在管制員總工作負(fù)荷中差異不大。本文進(jìn)行的管制扇區(qū)劃分結(jié)果與仿真結(jié)果一致，說(shuō)明模型是有效的。

表2 TAAM 仿真結(jié)果對(duì)比

4 結(jié)論

從管制空域的航路網(wǎng)絡(luò)結(jié)構(gòu)圖出發(fā)，提出空域頂點(diǎn)間動(dòng)態(tài)靜態(tài)雙聯(lián)系的計(jì)算方法，構(gòu)建空域的無(wú)向圖模型，并利用譜聚類切圖的思想建立了管制扇區(qū)劃設(shè)的數(shù)學(xué)模型，再利用譜聚類算法進(jìn)行求解，得到扇區(qū)間流量更為均衡、協(xié)調(diào)工作負(fù)荷盡量小的結(jié)果，同時(shí)扇區(qū)邊界布局合理，滿足管制扇區(qū)劃設(shè)的要求。進(jìn)行實(shí)例分析并結(jié)合軟件仿真驗(yàn)證本文提出方法的有效性，將結(jié)果與當(dāng)前存在的扇區(qū)進(jìn)行對(duì)比分析，驗(yàn)證了基于譜聚類算法進(jìn)行扇區(qū)劃分方法的合理性和高效性。對(duì)基于譜聚類的管制扇區(qū)劃設(shè)的研究，下一步將利用譜聚類建模的思想，建立最優(yōu)化問(wèn)題，采用智能算法進(jìn)行解算。