基于改進(jìn)桶結(jié)構(gòu)輪盤(pán)算法的混合航線網(wǎng)絡(luò)仿真

趙得存， 賴(lài) 欣

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

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

1 相關(guān)理論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

(3)

6)將度變化的節(jié)點(diǎn)重新分配對(duì)應(yīng)的桶內(nèi)。

7)統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)和邊數(shù)。

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

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

2 桶結(jié)構(gòu)的輪盤(pán)算法改進(jìn)

根據(jù)上文分析，為了更好地進(jìn)行混合航線構(gòu)建，從固定參數(shù)、節(jié)點(diǎn)來(lái)源、連邊限制3個(gè)方面對(duì)原算法進(jìn)行改進(jìn)，使構(gòu)建出的網(wǎng)絡(luò)符合混合航線網(wǎng)絡(luò)結(jié)構(gòu)的特征。對(duì)邊賦予標(biāo)簽，通過(guò)辨別邊標(biāo)簽，實(shí)現(xiàn)對(duì)混合航線網(wǎng)絡(luò)中的固定航線和臨時(shí)航線進(jìn)行模擬和可視化。基于上述思想，改進(jìn)算法執(zhí)行步驟如下：

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

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

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

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

(4)

(5)

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

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

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

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

表3 所用符號(hào)和意義

圖1 改進(jìn)的RW-bucket算法流程

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

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

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

表4 飛行情報(bào)區(qū)1節(jié)點(diǎn)和邊數(shù)量統(tǒng)計(jì)

表5 飛行情報(bào)區(qū)1節(jié)點(diǎn)度統(tǒng)計(jì)

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

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

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

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

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

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

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

表6 飛行情報(bào)區(qū)2節(jié)點(diǎn)和邊數(shù)量統(tǒng)計(jì)

表7 飛行情報(bào)區(qū)2節(jié)點(diǎn)度統(tǒng)計(jì)

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

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

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

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

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

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

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

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

表8 對(duì)比驗(yàn)證結(jié)果

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

4 結(jié)語(yǔ)

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

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