趙得存， 賴 欣

(中國民用航空飛行學院 空中交通管理學院， 四川 廣漢 618307)

中國的航線網(wǎng)絡(luò)分為固定(ATS)航線網(wǎng)絡(luò)和臨時航線網(wǎng)絡(luò)，相應的其他國家或者組織也存在類似航線網(wǎng)絡(luò)布局，例如歐洲區(qū)域的航線網(wǎng)絡(luò)除了ATS航線網(wǎng)絡(luò)還有CDR航線網(wǎng)絡(luò)和DCT航線網(wǎng)絡(luò)。由兩種或者兩種以上的航線網(wǎng)絡(luò)組成的航線網(wǎng)絡(luò)稱為混合航線網(wǎng)絡(luò)。航線網(wǎng)絡(luò)是航空公司進行航班走向規(guī)劃的基礎(chǔ)。固定航線作為空中交通運輸主要路線，連接各飛行情報區(qū)，承擔著絕大部分的運輸任務(wù)，臨時航線主要分在限制區(qū)域、樞紐機場附近，作為固定航線的補充。固定航線和臨時航線使用有較大區(qū)別，固定航線可作為航空公司的長期航班運行的走向規(guī)劃基礎(chǔ)，而臨時航線的使用需要航空公司臨時提出申請，并獲得相關(guān)管理部門的批準，但臨時航線具有距離短、繞飛區(qū)域少的優(yōu)勢，使用臨時航線可為航空公司節(jié)省燃油消耗、提高運行效率。例如2019年，共有37.3萬架次航班使用臨時航路，縮短飛行距離1 570萬km。在航路圖中查詢臨時航線由于存在大量的固定航線以及圖幅問題，在查詢過程需要反復對航路圖逐步放大查詢，十分浪費時間，對公司進行航線規(guī)劃產(chǎn)生障礙。因此可見構(gòu)建能夠?qū)潭ê骄€網(wǎng)絡(luò)和臨時航線網(wǎng)絡(luò)可視化的航線網(wǎng)絡(luò)極為重要。

1 相關(guān)理論

1.1 基于復雜網(wǎng)絡(luò)理論的航線網(wǎng)絡(luò)分析

從復雜網(wǎng)絡(luò)[1-3]的角度來分析航線網(wǎng)絡(luò)[4-12]，每一種航線網(wǎng)絡(luò)都有一定的小世界性和無標度性[13-15]，節(jié)點度的分布符合冪律分布。每一種航線網(wǎng)絡(luò)都能夠由圖論中的以下部分組成：

1)網(wǎng)絡(luò)的節(jié)點。無論固定航線網(wǎng)絡(luò)或是臨時航線網(wǎng)還是其他航線網(wǎng)絡(luò)，均以航路點為節(jié)點。

2)節(jié)點度。不同的航線網(wǎng)絡(luò)，節(jié)點有不同的連接方式，但節(jié)點的度都符合冪律分布。

3)網(wǎng)絡(luò)的邊。組成航線的航段為網(wǎng)絡(luò)的邊,且兩節(jié)點之間有且僅有一條邊。

4)無向網(wǎng)絡(luò)。多數(shù)情況下，兩航路點之間是雙向的，即航路點A可以到達航路點B，那么航路點B也可以到達航路點A，即網(wǎng)絡(luò)是雙向的。因此，在進行航線網(wǎng)絡(luò)構(gòu)建時，可以將雙向網(wǎng)絡(luò)抽象為無向網(wǎng)絡(luò)。

以中國固定航線網(wǎng)絡(luò)和臨時航線網(wǎng)絡(luò)為例，節(jié)點度分布見表1，混合航線網(wǎng)絡(luò)節(jié)點和邊數(shù)量統(tǒng)計分析見表2。

根據(jù)表1可知，在臨時航線網(wǎng)絡(luò)中度數(shù)為1或2的節(jié)點數(shù)量占據(jù)總節(jié)點數(shù)量的85%。在固定航線網(wǎng)絡(luò)和混合航線網(wǎng)絡(luò)中度數(shù)為2、3、4、5的節(jié)點數(shù)量分別占據(jù)各自總節(jié)點數(shù)量的89%，符合冪律分布(二八定律)。

表1 混合航線網(wǎng)絡(luò)節(jié)點度統(tǒng)計

表2 混合航線網(wǎng)絡(luò)節(jié)點和邊數(shù)量統(tǒng)計

1.2 桶結(jié)構(gòu)的輪盤算法

根據(jù)上文對航線網(wǎng)絡(luò)的分析，航線網(wǎng)絡(luò)是典型的無標度網(wǎng)絡(luò)，而生成無標度網(wǎng)絡(luò)的經(jīng)典算法主要有簡單輪盤算法、隨機選擇算法、基于桶結(jié)構(gòu)的輪盤算法等。使用簡單輪盤算法構(gòu)建無標度網(wǎng)絡(luò)會出現(xiàn)拒絕式抽樣導致無法正確連邊問題。使用隨機選擇算法在構(gòu)建無標度網(wǎng)絡(luò)時，需要花費較長的時間遍歷圖中所有節(jié)點來進行增長?；谕敖Y(jié)構(gòu)的輪盤算法以分桶的方式既避免了拒絕式抽樣問題又解決了在節(jié)點數(shù)量較大時，圖增長過慢的問題。

基于桶結(jié)構(gòu)的輪盤算法(roulette wheel bucket，RW-bucket)是賭輪盤算法和桶排序結(jié)合形成一種算法，將相同性質(zhì)或相同屬性的個體歸在一個桶內(nèi)，進行統(tǒng)一操作，其操作準則為：各個個體被選中的概率與其適應度大小成正比。進而在使用該算法進行航線網(wǎng)絡(luò)構(gòu)建時需要歸類的個體即為節(jié)點；劃分依據(jù)為節(jié)點度相同歸為同一個桶內(nèi)；個體適應度即為節(jié)點度的大小，節(jié)點度越大則被選中的概率越大；算法的核心為構(gòu)建網(wǎng)絡(luò)圖時的選點和連邊。

基于桶結(jié)構(gòu)的輪盤算法的傳統(tǒng)步驟如下：

1)初始生成一個無向圖G0，節(jié)點集為{v1,v2,…，vm}，邊集為{e1,e2,…，em}。

2)隨機產(chǎn)生一個節(jié)點vk+1和隨機數(shù)r。

3)計算節(jié)點的度，按照度相同原則分成桶。

4)計算桶的概率密度函數(shù)p(Bi)和累積分布函數(shù)P(Bi)滿足

(1)

(2)

5)逐個判定每個桶是否滿足P(Bi)≤r≤P(Bi+1)條件，若不滿足返回步4)，若滿足則在滿足的桶Bi內(nèi)隨機選擇一個節(jié)點vm與vk+1進行相連；與新節(jié)點相連的概率p(vm)滿足

(3)

6)將度變化的節(jié)點重新分配對應的桶內(nèi)。

7)統(tǒng)計節(jié)點個數(shù)和邊數(shù)。

8)判定網(wǎng)絡(luò)圖G中節(jié)點和邊數(shù)是否滿足要求，若滿足則停止，不滿足則轉(zhuǎn)步驟2)。

從上述傳統(tǒng)桶結(jié)構(gòu)的輪盤算法流程可以得出，桶結(jié)構(gòu)的輪盤算法生成網(wǎng)絡(luò)的節(jié)點數(shù)量隨著網(wǎng)絡(luò)的增長而越來越多；度相同的節(jié)點數(shù)量也越來越多，網(wǎng)絡(luò)中節(jié)點的度隨著網(wǎng)絡(luò)增長變得越來越大；網(wǎng)絡(luò)中邊數(shù)也越來越多?？偟膩碚f基于傳統(tǒng)的桶結(jié)構(gòu)的輪盤算法生成的網(wǎng)絡(luò)是沒有邊界限制的。然而混合航線網(wǎng)絡(luò)卻是在節(jié)點數(shù)量、邊數(shù)量、相同節(jié)點數(shù)量、最大節(jié)點度方面有著嚴格的限制。根據(jù)上述分析可見，雖然兩者在結(jié)構(gòu)上具有相似性，但在具體網(wǎng)絡(luò)生成的數(shù)量和生成規(guī)則具有差異性，因此無法直接利用RW-bucket進行混合航線網(wǎng)絡(luò)的構(gòu)建。所以需要在傳統(tǒng)算法的基礎(chǔ)之上對傳統(tǒng)算的構(gòu)建網(wǎng)絡(luò)的增長，連邊進行約束改進，以滿足構(gòu)建混合航線網(wǎng)絡(luò)的要求，此外還需要對邊賦予標簽，進行邊分類模擬混合航線網(wǎng)絡(luò)中固定航線和臨時航線共存的現(xiàn)象，并能夠進行其可視化。

2 桶結(jié)構(gòu)的輪盤算法改進

根據(jù)上文分析，為了更好地進行混合航線構(gòu)建，從固定參數(shù)、節(jié)點來源、連邊限制3個方面對原算法進行改進，使構(gòu)建出的網(wǎng)絡(luò)符合混合航線網(wǎng)絡(luò)結(jié)構(gòu)的特征。對邊賦予標簽，通過辨別邊標簽，實現(xiàn)對混合航線網(wǎng)絡(luò)中的固定航線和臨時航線進行模擬和可視化?；谏鲜鏊枷耄倪M算法執(zhí)行步驟如下：

步驟1：通過設(shè)定節(jié)數(shù)、邊數(shù)和最大節(jié)點度給出一個待增長的初始網(wǎng)絡(luò)圖和生長上限。設(shè)定|N|=a、|B|=b和deg(vj)max=c，a、b、c為常數(shù)。

步驟2：通過從已有的節(jié)點中隨機選取一個節(jié)點當作增長節(jié)點。同時在(0，1)內(nèi)產(chǎn)生一個隨機數(shù)為連邊做依據(jù)。

步驟3：通過桶結(jié)構(gòu)將眾多的節(jié)點統(tǒng)一劃分進行歸類處理。以便于為連邊做準備加快網(wǎng)絡(luò)生長速度。

步驟4：計算桶的概率密度函數(shù)和累積分布函數(shù)。通過計算桶的概率密度函數(shù)和累積分布函數(shù)來避開逐個計算每個節(jié)點的概率密度函數(shù)和累積分布函數(shù)以此提高算法速度，并為連邊提供數(shù)據(jù)支撐。所用公式為

(4)

(5)

步驟5：判定隨機數(shù)是否滿足不等式P(Bi)≤r≤P(Bi+1)，決定增長節(jié)點的連接對象。

步驟6：重新劃分桶和判定網(wǎng)絡(luò)成熟度。統(tǒng)計Bi和|Bi|；判定是否滿足i=c，若滿足，則對應的Bi桶內(nèi)的節(jié)點不允許與其他節(jié)點相連，不滿足進行下一步；判定是否滿足|Bi|=b，若滿足，則Bi桶鎖定不進行任何操作，且Bi-1桶內(nèi)節(jié)點不允許與其他節(jié)點相連，不滿足則進行下一步；統(tǒng)計|N|，判定是否滿足|N|=a，若滿足則停止，不滿足則轉(zhuǎn)步驟2。

步驟7：對已成熟的網(wǎng)絡(luò)中的節(jié)點賦予坐標，邊賦予標簽，并根據(jù)標簽進行著色，以此來模擬混合網(wǎng)絡(luò)中包含固定航線和臨時航線的情況。

算法執(zhí)行步驟中所用符號與意義見表3。改進算法的執(zhí)行流程如圖1所示。

表3 所用符號和意義

圖1 改進的RW-bucket算法流程

3 基于改進算法的混合航線網(wǎng)絡(luò)仿真

為驗證改進RW-bucket算法對構(gòu)建混合航線網(wǎng)絡(luò)的可行性，采用Python軟件對改進RW-bucket算法進行編程，并對兩個情報區(qū)內(nèi)的航線結(jié)構(gòu)數(shù)據(jù)進行統(tǒng)計。根據(jù)統(tǒng)計結(jié)果，對相應情報區(qū)的混合航線網(wǎng)絡(luò)進行構(gòu)建，實現(xiàn)混合航線網(wǎng)絡(luò)的方針，同時實現(xiàn)固定航線和臨時航線的可視化。

驗證飛行情報區(qū)1的航段數(shù)和節(jié)點度分布統(tǒng)計數(shù)據(jù)見表4、表5。

表4 飛行情報區(qū)1節(jié)點和邊數(shù)量統(tǒng)計

表5 飛行情報區(qū)1節(jié)點度統(tǒng)計

根據(jù)統(tǒng)計數(shù)據(jù)執(zhí)行算法，其中a=39，|B|=36，|Bi|={9,8,4,3,2,1,1}，c=7。

根據(jù)Python編程執(zhí)行算法得出驗證飛行情報區(qū)1的混合航線網(wǎng)絡(luò)結(jié)構(gòu)圖，如圖2所示。

虛線代表臨時航線，實線代表固定航線圖2 飛行情報區(qū)1混合航線網(wǎng)絡(luò)模擬圖

圖3為圖2對應的真實航路圖，通過實物對比驗證方法，從節(jié)點連接正確性和航線類別表達的正確性兩方面來檢驗方法的可用性?？梢郧逦鞔_地看出圖2對圖3從節(jié)點連接和航線類別兩方面成功地進行了模擬。圖2完整模擬出圖3的航線結(jié)構(gòu)，并能對固定航線和臨時航線進行可視化區(qū)分。

圖3 飛行情報區(qū)1的真實航線結(jié)構(gòu)

飛行情報區(qū)2的節(jié)點數(shù)量、邊數(shù)量和節(jié)點度分布統(tǒng)計見表6、表7。

那么此時算法中的a=16，|B|=36，|Bi|={11,1,1,1,1,0,1}，c=7。著色邊數(shù)量為8條。

表6 飛行情報區(qū)2節(jié)點和邊數(shù)量統(tǒng)計

表7 飛行情報區(qū)2節(jié)點度統(tǒng)計

根據(jù)Python編程執(zhí)行算法得出飛行情報區(qū)2的混合航線網(wǎng)絡(luò)結(jié)構(gòu)模擬圖，如圖4所示。

虛線代表臨時航線；實線代表固定航線圖4 飛行情報區(qū)2混合航線網(wǎng)絡(luò)模擬圖

圖5為圖4對應的真實航路圖，通過實物對比驗證方法，從節(jié)點連接正確性和航線類別表達的正確性兩方面來檢驗方法的可用性?？梢郧逦鞔_地看出圖4對圖5從節(jié)點連接和航線類別兩方面成功地進行了模擬。圖4完整模擬出圖5的航線結(jié)構(gòu)，并能對固定航線和臨時航線進行可視化區(qū)分。

圖5 飛行情報區(qū)2的真實航線結(jié)構(gòu)

以上是在小范圍進行的驗證，為了說明該方法也適用于大范圍的航線可視化，將飛行情報區(qū)1、2所在的完整情報區(qū)的航線網(wǎng)絡(luò)利用該方法進行可視化，如圖6、圖7所示。

圖6 情報區(qū)1所在的完整情報區(qū)A的航線 網(wǎng)絡(luò)結(jié)構(gòu)

圖7 情報區(qū)2所在的完整情報區(qū)B的航線網(wǎng)絡(luò)結(jié)構(gòu)

圖6、圖7中圓形區(qū)域分別對應飛行情報區(qū)1、2的航線結(jié)構(gòu)，由于實際航路圖圖幅問題無法進行實物對比驗證地展示，因此從節(jié)點數(shù)量和固定航線以及臨時航線所包含的航段數(shù)量對模擬網(wǎng)絡(luò)和實際航路圖進行比較，見表8。

表8 對比驗證結(jié)果

從表8中可以明確看出模擬結(jié)果與實際航路圖所包含數(shù)據(jù)一致，且在與實際航路進行實物對比驗證得出模擬結(jié)果的航線網(wǎng)絡(luò)結(jié)構(gòu)和連接與實際網(wǎng)路一致。綜上和以上驗證可以得出該方法能夠?qū)嶋H航路圖進行模擬構(gòu)建并對固定航線和臨時航線進行可視化區(qū)分。

4 結(jié)語

研究了中國航線網(wǎng)絡(luò)中的航線類型，介紹了固定航線和臨時航線的作用，分析了固定航線和臨時航線在航路圖中存在的查詢矛盾，提出了構(gòu)建能夠?qū)潭ê骄€網(wǎng)絡(luò)和臨時航線網(wǎng)絡(luò)可視化的航線網(wǎng)絡(luò)的方法。從復雜無標度網(wǎng)絡(luò)角度對中國的航線網(wǎng)絡(luò)進行研究，總結(jié)航線網(wǎng)絡(luò)的特點，針對航線網(wǎng)絡(luò)存在的特點和構(gòu)建要求，對構(gòu)建航線網(wǎng)絡(luò)的算法進行比較篩選。得出使用RW-bucket算法進行航線網(wǎng)絡(luò)，為了能夠更為貼合航線網(wǎng)絡(luò)的構(gòu)建要求，對RW-bucket進行改進。從中國航空資料匯編中獲得航路數(shù)據(jù)，使用改進后的方法進行模擬構(gòu)建，將構(gòu)建結(jié)果采用實物對比驗證的方法，與實際航路圖對應的部分進行從節(jié)點連接和航線類別表達兩方面來評價方法的適用性。經(jīng)過對比驗證后，結(jié)構(gòu)表明，該方法能夠正確地表達節(jié)點連接問題和航線類別可視化問題。

綜上，本文提出了一種構(gòu)建對固定航線網(wǎng)絡(luò)和臨時航線網(wǎng)絡(luò)可視化的航線網(wǎng)絡(luò)的方法，該算法采用對節(jié)點先分桶后統(tǒng)計再連接的方法，避免了在構(gòu)建航線網(wǎng)絡(luò)出現(xiàn)的“拒絕式抽樣問題”，并且通過桶結(jié)構(gòu)存儲節(jié)點，進一步降低了算法復雜度。通過對航線進行標簽化，在算法實現(xiàn)過程中通過判定標簽類型，對固定航線和臨時航線進行可視化區(qū)分。該方法可助情報人員對航線類型快速判定出航線類別，其次提高臨時航線在航班走向規(guī)劃時的使用頻率，充分發(fā)揮臨時航線具有的截彎取直、節(jié)省飛行時間、降低運行成本的優(yōu)勢。