基于復雜度加權(quán)的Voronoi圖扇區(qū)邊界劃分研究

王莉莉 ，胡 婧 ，高 崢

（1.中國民航大學空中交通管理學院，天津 300300；2.民航天津空管分局，天津 300300）

空域管理部門通常將空域劃分為若干個扇區(qū)，每個扇區(qū)設(shè)立一個管制席位，進行空中交通的指揮和協(xié)調(diào)工作。近年來，隨著民航業(yè)的迅猛發(fā)展以及飛行運行總架次的日益增長，空中交通管制員在其管轄范圍內(nèi)指揮的飛機數(shù)量越來越多，管制員的工作負荷越來越大，致使空中交通管制系統(tǒng)面臨著越來越嚴峻的挑戰(zhàn)，對飛行安全帶來不利影響。有些扇區(qū)的管制員工作負荷量較少，而有些扇區(qū)的管制員工作負荷量卻很大，扇區(qū)的管制員工作負荷不均衡的原因在于目前扇區(qū)的劃分缺乏科學合理的規(guī)劃，因此，如何在劃分扇區(qū)時進行綜合優(yōu)化，確?？沼騽澐值目茖W、合理和有效，成為民航空中交通管制領(lǐng)域不少學者研究關(guān)注的一個重要課題。

國內(nèi)外很多研究人員對最優(yōu)扇區(qū)劃分問題進行了研究：首先，國際民航組織（ICAO）頒布了“DORATASK”和“MBB”管制員評估法，此類方法是通過對管制員工作負荷的分類以及一定的時間間隔觀察管制員的活動來確定工作負荷[1-2]；Huy Trandac等通過建立平面的Voronoi多邊形和采用啟發(fā)式優(yōu)化算法，確定了二維扇區(qū)劃分結(jié)果[3]；2003年，韓松臣、張明提出了以導航臺、航線交叉點和空域邊界上的航路點為節(jié)點的蛻變的Voronoi圖，應用模擬退火算法獲得優(yōu)化的扇區(qū)邊界線[4-6]；2009年，中國民航大學的戴福青提出了基于Power圖和空中交通復雜度的多機場劃設(shè)方法，分別對多機場地區(qū)終端區(qū)分高低兩層扇區(qū)進行研究，以扇區(qū)結(jié)構(gòu)特征為約束條件，采用遍歷搜索算法搜索尋優(yōu)找到最終優(yōu)化的扇區(qū)[7-8]。

本文提出考慮導航臺、航線交叉點和空域邊界上的航路點的分布，采用加權(quán)Voronoi圖將空域劃分為有限單元，與普通Voronoi圖不同，在加入扇區(qū)單元航跡數(shù)目以及導航臺影響能力不同而設(shè)置不同權(quán)值的基礎(chǔ)上，根據(jù)各有限單元的工作負荷，建立了扇區(qū)優(yōu)化模型，使扇區(qū)單元組合更加合理；提出統(tǒng)計復雜度值時，添加考慮飛行速度的變化以及不同天氣情況等因素對扇區(qū)規(guī)劃的影響，使復雜度統(tǒng)計值更加完善，最后采用生長算法對空域中的加權(quán)Voronoi多邊形進行優(yōu)化組合，以加快計算速度。

1 加權(quán)Voronoi圖

一般Voronoi圖是假設(shè)除了生成元的位置外，其他都是相同的；而空管實際運行情況則不然，比如在一些空域扇區(qū)單元內(nèi)航跡較多，而一些扇區(qū)單元內(nèi)航跡很少，如果還設(shè)置相同的權(quán)值進行劃分是不合理的。因此由不同的權(quán)值反映不同生成元的性質(zhì)更加合適，更加貼近實際情況，所以引入加權(quán)Voronoi圖。

定義設(shè)生成元集合S={p1，…，pn}?R2（2≤n≤∞），權(quán)值集合為 W={w1，…，wn}，wi為生成元 pi的權(quán)值（i=1，2，…，n），則加權(quán) Voronoi圖定義為

式中：daw（p，pi）為加權(quán)距離。加權(quán)距離下的pi控制區(qū)域記作V（pi）=∩Dom（pi，pj），其中Dom（pi，pj）={p|daw（p，pi）＜daw（p，pj）}，i≠j；Vorw（P，dw，R2）={V（p1），…，V（pn）}為帶權(quán)集{w1，…，wn}的集合 P 生成的加權(quán) Voronoi圖，集合Vor（Pi）定義成與Pi關(guān)聯(lián)的加權(quán)Voronoi域。

圖1為廈門管制區(qū)空域結(jié)構(gòu)，圖2為基于此空域結(jié)構(gòu)生成的Voronoi圖，圖3為加權(quán)后的Voronoi圖。圖2與圖3相比而言，如果不加入一定的權(quán)重值，空域邊界上的導航臺或位置點作為生成元生成的Voronoi區(qū)域較小，不符合飛越該空域邊界所需負荷較大的特點。圖3中的黑點代表生成元，序號1、2、3等為扇區(qū)單元序號，共分為12個扇區(qū)單元；從圖1中的空域結(jié)構(gòu)圖可以看出航跡，導航臺的覆蓋范圍和使用情況不同，以DO導航臺為生成元為例，背臺和向臺飛行的航跡較多，航路結(jié)構(gòu)復雜，其權(quán)重值應較大。因此，綜合上述因素為其賦值不同的權(quán)值wi分別代表它們的不同影響能力。本文在加入權(quán)重值基礎(chǔ)上使得隨后的實例二維平面空域扇區(qū)最優(yōu)邊界的尋找更加符合實際。

圖1 廈門管制空域結(jié)構(gòu)圖Fig.1 Structure of Xiamen controlled airspace

圖2 Voronoi圖Fig.2 Voronoi diagram

圖3 加權(quán)Voronoi圖Fig.3 Weighted Voronoi diagram

2 扇區(qū)容量的確定

2.1 空中交通復雜度模型

為了精確量化管制員所面臨的并要解決的交通狀況的困難程度，以往大多都是以統(tǒng)計管制員負荷或者雷達軌跡搜索到的詳盡的飛行數(shù)據(jù)資料的方法進行研究，而目前以空中交通復雜度進行研究更好。其優(yōu)勢在于復雜度模型避免了早期直接的管制員工作負荷模型中帶來的主觀工作負荷難以測量的弱點，直接利用航空器速度、航向等交通流內(nèi)部屬性對空域狀態(tài)的復雜程度進行客觀的描述，能較好地兼顧扇區(qū)空域資源的靈活使用和管制員工作負荷影響，實現(xiàn)扇區(qū)資源的有效利用。

2.1.1 空中交通復雜度的數(shù)據(jù)統(tǒng)計

本文根據(jù)影響空中交通復雜度的因素，結(jié)合扇區(qū)的結(jié)構(gòu)特征建立了空中交通復雜度模型，嘗試使用結(jié)合扇區(qū)飛機流量的空中交通復雜度標準來作為評估標準，間接反映扇區(qū)容量。復雜度只限于交通狀況本身的特性，與以往管制員工作負荷的統(tǒng)計不同，避免了管制員指揮飛行器時的個體差異，具有客觀性。

扇區(qū)單元復雜度用以下4個元素進行衡量：

1）飛行速度的變化：航空器以不同航速在飛行時會造成管制員的工作強度。如在程序飛行中當前后航空器之間的飛行速度相差大于80 km/h時，飛行間隔為2 min，而如果速度小的航空器在前，速度大的在后同高度飛行時，應保證在到達著陸機場上空或者改變高度層以前要有10 min的縱向間隔，這給管制員造成的不同的工作難度，可表示為

式中：ws為飛行速度權(quán)系數(shù)；Ti，Tj為不同航速的航空器通過扇區(qū)單元的時間；T為航空器平均穿越扇區(qū)單元所用的時間。

2）飛行狀態(tài)的變化：飛行狀態(tài)一般有起飛、降落和飛越，管制員對其中任何單一的狀態(tài)調(diào)配都比它們的混合狀態(tài)簡單；因為調(diào)配所發(fā)指令數(shù)不同，工作強度不一樣，可表示為

式中：wf為飛行狀態(tài)權(quán)系數(shù)；Ti，Tj，Tk為航空器在 3 種飛行狀態(tài)下通過扇區(qū)單元所需要的時間；T為航空器平均穿越扇區(qū)單元所用的時間；Ti∩Tj∩Tk表示航空器在混合狀態(tài)下穿越扇區(qū)所用時間。

3）飛機類型的不同[8]：調(diào)度同一類型的飛機要比調(diào)度不同類型飛機容易很多。所以每個扇區(qū)單元的復雜度值要考慮飛機類型權(quán)重系數(shù)wap。根據(jù)尾流間隔把飛機分為重型機、中型機和輕型機，可表示為

式中：Ti，Tj，Tk為3種航空器在同一時段內(nèi)穿越扇區(qū)所需時間；T為航空器平均穿越扇區(qū)單元所用的時間。

4）天氣情況的不同：氣象條件的不同會給管制員在調(diào)配工作方面帶來不同的難度。天氣越惡劣，航空器在通過一片扇區(qū)時管制員需要投入工作的時間和精力越多。所以空中交通復雜度要考慮天氣情況權(quán)重系數(shù)。設(shè)天氣情況權(quán)重系數(shù)為ww。其中惡劣天氣情況有顛簸、積冰、雷暴、風切變等，可表示為

式中：Ti為不同惡劣天氣情況下航空器通過扇區(qū)所用時間；T為航空器平均穿越扇區(qū)單元所用的時間。

2.1.2 空中交通復雜度計算

以導航臺為中心的扇區(qū)單元的空中交通復雜度值為

據(jù)上述數(shù)據(jù)統(tǒng)計，計算出在一天24小時內(nèi)廈門管制底層空域各扇區(qū)單元空中交通復雜度，如圖4所示。圖中2號扇區(qū)靠近廈門進近，所以復雜度值大；3號、4號扇區(qū)單元復雜度值也較大，因為靠近福州進近；5號、6號、7號、8號和11號扇區(qū)單元遠離進近所以復雜度值較?。豢拷湟纳竭M近的9、10號扇區(qū)復雜度值也較大；1、12號扇區(qū)因為航路網(wǎng)結(jié)構(gòu)復雜，所以復雜度值也較大。

2.1.3 扇區(qū)單元管制員工作負荷

式中：Wload為扇區(qū)單元管制員工作負荷；TC為空中交通復雜度值；N為通過扇區(qū)單元的航空器架次數(shù)。

以扇區(qū)12單元為例，在11點到14點的高峰時段內(nèi)，空中交通復雜度值TC為1.3，而在這個高峰時期該扇區(qū)單元的流量N為18，工作負荷Wload為23.4。

根據(jù)空中交通復雜度值的計算間接算出廈門管制底層空域各扇區(qū)單元管制員工作負荷，如圖5所示。

圖4 扇區(qū)單元各小時段內(nèi)的空中交通復雜度值Fig.4 Air traffic complexity of sector unit in each period

圖5 各扇區(qū)單元的管制員平均每小時管制負荷Fig.5 Average hourly controller workload in each sector unit

2.2 扇區(qū)邊界尋找算法

通過上述空中交通復雜度模型的建立以及扇區(qū)單元管制員工作負荷的計算，為了加快得到最優(yōu)的扇區(qū)邊界，針對本組合問題，結(jié)合生長算法的優(yōu)點，所以提出一種先采用生長算法得到信息素，并調(diào)用該信息素進行優(yōu)化求解的方式來得到全局最優(yōu)解。這樣大大加快了求解速度。下面以劃分為2個扇區(qū)為例，給出流程圖如圖6所示。

圖6 生長算法流程圖Fig.6 Flowchart of growing algorithm

3 實例分析

通過上述管制員工作負荷統(tǒng)計得到，繁忙時段11：00—14：00內(nèi)總管制負荷較高，為廈門空管站使新劃分的扇區(qū)能應對未來流量增加一倍的要求，重新對底層空域進行扇區(qū)劃分：

1）以目前的管制空域結(jié)構(gòu)為基礎(chǔ)，拆除原始低層空域中扇區(qū)的邊界線和該邊界線上用于扇區(qū)移交的報告點。得到未劃設(shè)扇區(qū)的原始空域結(jié)構(gòu)，如圖7粗黑線所示；

2）以原始空域圖中的航路點和航路交叉點為節(jié)點建立的Voronoi圖形成的扇區(qū)邊界較為參差不齊，因為未加入權(quán)值的扇區(qū)單元生成是隨機的，不具有客觀合理性，所以較為多邊形化。加入了生成元對應扇區(qū)單元的權(quán)值后扇區(qū)邊界較為圓滑，滿足扇區(qū)邊界的約束條件。加權(quán)后的Voronoi圖，如圖7細黑線所示；

3）計算每一個扇區(qū)單元的管制工作負荷，獲取有限元的相鄰列表。再利用生長算法得到劃分后的扇區(qū)仿真，如圖8所示，分為3個扇區(qū)。

圖7 管制空域結(jié)構(gòu)圖Fig.7 Controlled airspace structure

圖8 仿真后的扇區(qū)優(yōu)化圖Fig.8 Optimization sector plot after simulation

4 結(jié)語

本文分析了影響扇區(qū)管制員工作負荷的復雜度因素，并建立了空中交通復雜度模型來間接計算扇區(qū)容量，避免了主觀分析法的不全面性。通過算例仿真分析驗證了其可行性：①利用加權(quán)Voronoi圖所畫出的扇區(qū)考慮到了工作負荷的影響，使分塊后得到的扇區(qū)比普通的Voronoi圖更精準，同時滿足方便扇區(qū)協(xié)調(diào)移交約束條件。②利用生長算法在連續(xù)性約束下可更快速準確的進行仿真計算，此算法計算量比較小，較快的得到扇區(qū)邊界。

本文的研究還有很多不足之處，一方面如何在復雜度計算中綜合眾多的因素來得到更準確的權(quán)值；另一方面對未來空域復雜度的變化沒有做出一定的預測判斷，這些都值得進一步的研究。

[1]PAWLAK W S，GOEL V，ROTHENBERG D B，et al.Comparision of Algorithms for the Dynamic Resectorization of Airspace[C]//AIAA Guidance Navigation，and Control Conference and Exhibit.Reston，VA：American Institute of Aeronautics and Astronautics，1998：67-74.

[2]LAUDEMAN I V，SHELDEN S G，BRANSTROM R，et al.Dynamic density：An Air Traffic Management Metric，NASA-T M-1998-112226[R].Moffett Field，CA：NASA Ames Research Center，1998.

[3]HUY TRANDAC，DUONG V.Optimized Sectorization of Airspace with Constraints[C]//In 5th Eurocontrol/FAA ATM R & D Seminar，2003：23-27.

[4]韓松臣，胡明華，蔣 兵.扇區(qū)容量與管制員工作負荷的關(guān)系研究[J].空中交通管理，2000（6）：42-45.

[5]韓松臣，張 明.依據(jù)管制工作負荷的扇區(qū)優(yōu)化新方法[J].南京航空航天大學學報，2004，36（1）：91-96.

[6]張 明.管制扇區(qū)的最優(yōu)劃分方法研究[J].南京航空航天大學學報，2004，（3）：308-312.

[7]李 錚.終端區(qū)扇區(qū)劃設(shè)方法研究[D].天津：中國民航大學，2009.

[8]戴福青，洪蘭收.空域交通復雜度計算方法研究[J].中國民航大學學報，2010，28（3）：1-4.

[9]何 毅.空中交通復雜度參數(shù)模型研究[D].上海：同濟大學，2007.