航路網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)優(yōu)化與“三區(qū)”避讓設(shè)計(jì)方法

許有臣，朱衍波（民航數(shù)據(jù)通信有限責(zé)任公司，北京 100091）

航路網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)優(yōu)化與“三區(qū)”避讓設(shè)計(jì)方法

許有臣，朱衍波
（民航數(shù)據(jù)通信有限責(zé)任公司，北京 100091）

針對(duì)提高空中交通航路網(wǎng)絡(luò)運(yùn)行效率的問題，本文提出了航路網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)優(yōu)化與“三區(qū)”避讓設(shè)計(jì)相結(jié)合的網(wǎng)絡(luò)設(shè)計(jì)方法。首先，給出了航路網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)優(yōu)化與“三區(qū)”避讓設(shè)計(jì)的模型，并利用遺傳算法對(duì)航路網(wǎng)絡(luò)設(shè)計(jì)問題進(jìn)行了求解；應(yīng)用分析表明：優(yōu)化設(shè)計(jì)后的航路網(wǎng)絡(luò)相比現(xiàn)行航路網(wǎng)絡(luò)，在運(yùn)行成本、非直線系數(shù)、連接度、可達(dá)性等性能指標(biāo)上均有大幅改善，從而證明該方法的正確性。

空中交通管理；航路網(wǎng)絡(luò)；拓?fù)浣Y(jié)構(gòu)；優(yōu)化設(shè)計(jì)；遺傳算法

中國(guó)現(xiàn)行的航路網(wǎng)絡(luò)是隨著社會(huì)、經(jīng)濟(jì)、政治、軍事的發(fā)展而逐步形成的，其形成是一個(gè)緩慢而漸進(jìn)的過程。在此過程中各種因素的不平衡發(fā)展和相互制約導(dǎo)致了航路網(wǎng)結(jié)構(gòu)日趨偏離初始的最優(yōu)化設(shè)計(jì)。由于以前我國(guó)民用航空運(yùn)輸不發(fā)達(dá)，這種偏離所造成的運(yùn)輸矛盾并不突出。但隨著全國(guó)民航運(yùn)輸?shù)目焖僭鲩L(zhǎng)與航路需求的多元化發(fā)展，全國(guó)航路網(wǎng)逐步暴露出其結(jié)構(gòu)性缺陷[1]。目前彌補(bǔ)航路網(wǎng)缺陷采取的是進(jìn)行局部、小范圍的調(diào)整方式，無法從根本上解決現(xiàn)行有限的航路網(wǎng)與航空市場(chǎng)日益增長(zhǎng)的需求這一矛盾。

本文運(yùn)用遺傳算法等定量化的分析方法，對(duì)航路網(wǎng)結(jié)構(gòu)進(jìn)行重新優(yōu)化設(shè)計(jì)，在保障空中飛行安全的同時(shí)，合理分配交通流量，從總體上提高航路網(wǎng)的整體容量，實(shí)現(xiàn)空域結(jié)構(gòu)的靈活使用，提高空域的整體運(yùn)行效能，減少航班延誤與飛行沖突，緩解航路擁堵現(xiàn)象，降低航空公司運(yùn)行成本，從而為公共航空運(yùn)輸創(chuàng)造良好的運(yùn)行環(huán)境，滿足國(guó)民經(jīng)濟(jì)和航空事業(yè)持續(xù)、健康、快速發(fā)展的需要。

1 航路網(wǎng)規(guī)劃關(guān)鍵技術(shù)

1.1 關(guān)鍵節(jié)點(diǎn)確定技術(shù)

1.1.1 問題描述

航路網(wǎng)是由基于航路點(diǎn)組成的網(wǎng)絡(luò)，對(duì)航路網(wǎng)進(jìn)行優(yōu)化，實(shí)際就是確定航路點(diǎn)的過程。航路點(diǎn)可以分為2種：固定點(diǎn)和移動(dòng)點(diǎn)。其中，移動(dòng)點(diǎn)由于其位置不固定，其位置的合適與否將對(duì)網(wǎng)絡(luò)整體性能構(gòu)成決定性的影響，因此，這種點(diǎn)就成為本研究的關(guān)鍵點(diǎn)。為了方便論述，本節(jié)假定航路網(wǎng)中有兩個(gè)移動(dòng)節(jié)點(diǎn)T1、T2，其他點(diǎn)都是固定點(diǎn)，因此，航路網(wǎng)的優(yōu)化問題也就可以歸結(jié)為確定這兩個(gè)移動(dòng)點(diǎn)（關(guān)鍵點(diǎn)）的問題。對(duì)于此類問題的求解，可以考慮采用遺傳算法來進(jìn)行求解。

1.1.2 基本遺傳算法簡(jiǎn)介

在過去30多年中，人們對(duì)模擬自然過程的算法產(chǎn)生了越來越濃厚的興趣。而計(jì)算性能的不斷提高不僅對(duì)這些算法本身的發(fā)展起到了巨大的推動(dòng)作用，同時(shí)也使它們具有越來越重要的實(shí)用價(jià)值。進(jìn)化算法是一類基于自然選擇和遺傳變異等生物演化機(jī)制的全局性概率搜索算法，包括遺傳算法（GA）、進(jìn)化規(guī)劃（EP）、進(jìn)化策略（ES）3種方法。進(jìn)化計(jì)算是一類模擬生物進(jìn)化過程與機(jī)制求解問題的自組織，自適應(yīng)人工智能技術(shù)。這類技術(shù)的核心思想源于這樣的基本認(rèn)識(shí)：生物進(jìn)化過程本身是一個(gè)自然的，并行發(fā)生的，穩(wěn)健的優(yōu)化過程。這一優(yōu)化過程的目標(biāo)是對(duì)環(huán)境的適應(yīng)性，生物種群通過優(yōu)勝劣汰及遺傳變異來達(dá)到進(jìn)化的目的。依達(dá)爾文的自然選擇和孟德爾的遺傳變異理論，生物進(jìn)化是通過繁殖、變異、競(jìng)爭(zhēng)和選擇4種基本形式實(shí)現(xiàn)的。如何把待解決的問題理解為對(duì)某個(gè)目標(biāo)函數(shù)的全局優(yōu)化，則進(jìn)化計(jì)算即是建立在模擬上述生物進(jìn)化過程基礎(chǔ)上的隨機(jī)搜索優(yōu)化技術(shù)?？偟膩碚f，進(jìn)化計(jì)算通過不斷迭代逐步改進(jìn)當(dāng)前解，直至最后搜索到最優(yōu)解或者滿意解。在進(jìn)化算法中，采用了模擬生物系統(tǒng)的進(jìn)化機(jī)制，從一組解（群體）出發(fā)，以類似自然選擇和有性繁殖的方式，在繼承原有優(yōu)良基因的基礎(chǔ)上，生成具有良好性能指標(biāo)的下一代解的群體。

與其他啟發(fā)式搜索方法（如爬山法，模擬退火法，Monte-Carlo方法）一樣，進(jìn)化算法在形式上也是一種迭代方法。它從選定的初始解出發(fā)，通過不斷迭代逐步改進(jìn)當(dāng)前解，直至最后搜索到最優(yōu)解或者滿意解。在進(jìn)化算法中，采用了模擬生物系統(tǒng)的進(jìn)化機(jī)制，從一組解（群體）出發(fā)，以類似自然選擇和有性繁殖的方式，在繼承原有優(yōu)良基因的基礎(chǔ)上，生成具有良好性能指標(biāo)的下一代解的群體。進(jìn)化計(jì)算用于優(yōu)化問題的一般過程如下：

第一步 隨機(jī)給定一組初始解；

第二步 評(píng)價(jià)當(dāng)前這組解的性能；

第三步 根據(jù)評(píng)價(jià)結(jié)果，從當(dāng)前解中選擇一定數(shù)量的解作為基因操作的對(duì)象；

第四步 對(duì)所選的解進(jìn)行基因操作（雜交/交叉、突變/變異），得到一組新的解；

第五步 返回到第二步，對(duì)該組新的解進(jìn)行評(píng)價(jià)；若當(dāng)前解滿足要求或進(jìn)化過程達(dá)到一定次數(shù)，計(jì)算結(jié)束，否則轉(zhuǎn)到第三步繼續(xù)進(jìn)行。

遺傳算法屬于進(jìn)化算法的一種?？梢园央y解的問題看成是對(duì)潛在解空間的一種搜索，對(duì)“最好”解的搜索及優(yōu)化過程。對(duì)于小空間，經(jīng)典的窮舉法已經(jīng)足夠，而對(duì)于大空間就可以考慮使用遺傳算法等。

遺傳算法借用了遺傳學(xué)和生物學(xué)中的一些名詞。一個(gè)群體中的個(gè)體稱為串或染色體，一個(gè)染色體的個(gè)體稱為單倍體。染色體的基本單位是基因，每個(gè)基因控制一個(gè)或幾個(gè)遺傳特征。某一特征的基因位于染色體的特定位置稱為位（locus）。每個(gè)基因型（可看作單個(gè)染色體）代表一個(gè)問題在特定染色體意義下的潛在解，一個(gè)發(fā)生在染色體群上的進(jìn)化對(duì)應(yīng)一個(gè)潛在解空間的搜索。

給定一個(gè)優(yōu)化任務(wù)，首先要將其轉(zhuǎn)化為可解的整體優(yōu)化問題。整體優(yōu)化問題的定義為：給定非空集合S作為搜索空間，f為目標(biāo)函數(shù)，任務(wù)（fx）是在S中找到至少一個(gè)使得目標(biāo)函數(shù)最大化的點(diǎn)。函數(shù)值f*= （fx*）+∞稱為一個(gè)整體極大值，當(dāng)且僅當(dāng)?x∈S，（fx）≤（fx*）時(shí)，x*∈S成為一個(gè)整體極大解。要有參數(shù)空間以及評(píng)價(jià)函數(shù)，遺傳算法以編碼空間代替原始的參數(shù)空間，以適應(yīng)度函數(shù)作為評(píng)價(jià)依據(jù)。針對(duì)不同的問題適應(yīng)度有不同的含義，因此其適應(yīng)函數(shù)也不同。在編碼群體的基礎(chǔ)上進(jìn)行算子操作進(jìn)行搜索?？梢钥闯?，遺傳算法必須包含以下5個(gè)要素：對(duì)問題潛在解的遺傳表達(dá)；產(chǎn)生潛在解初始群體的方法；扮演環(huán)境作用的、用“適應(yīng)值”評(píng)價(jià)解的優(yōu)劣的評(píng)價(jià)函數(shù)；改變后代構(gòu)成的各種遺傳算子；各種控制參數(shù)：群體規(guī)模、應(yīng)用遺傳算子的概率等。

1.1.3 基于單目標(biāo)約束的關(guān)鍵節(jié)點(diǎn)優(yōu)化模型

關(guān)鍵節(jié)點(diǎn)優(yōu)化問題可以抽象為單目標(biāo)約束優(yōu)化問題，目標(biāo)函數(shù)為航空運(yùn)行成本，約束是關(guān)鍵節(jié)點(diǎn)的可搜索空間[2-7]。在既定機(jī)隊(duì)型號(hào)和規(guī)模的前提下，航空運(yùn)行成本可以間接表征為航路網(wǎng)絡(luò)運(yùn)行成本，亦即總的飛行里程數(shù)（飛行流量X航段長(zhǎng)度）進(jìn)行表示。模型具體表達(dá)式如下所示。

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

其中fi、fj為單位時(shí)間上航路i、j上的飛機(jī)流量；m為與關(guān)鍵節(jié)點(diǎn)T1相關(guān)的航段數(shù)目；n為與關(guān)鍵節(jié)點(diǎn)T2相關(guān)的航段數(shù)目；Xi、Yi為與關(guān)鍵節(jié)點(diǎn)T1相關(guān)的航段端點(diǎn)位置橫縱坐標(biāo)；Xj、Yj為與關(guān)鍵節(jié)點(diǎn)T2相關(guān)的航段端點(diǎn)位置橫縱坐標(biāo)；XT1、YT1對(duì)應(yīng)關(guān)鍵節(jié)點(diǎn)T1的位置橫縱坐標(biāo)（直角坐標(biāo)系下）；XT2、YT2對(duì)應(yīng)關(guān)鍵節(jié)點(diǎn)T2的位置坐標(biāo)（直角坐標(biāo)系下）；給定非空集合ST1、ST2作為關(guān)鍵點(diǎn)T1、T2的可搜索空間。

上述表達(dá)式（1）中，目標(biāo)函數(shù)中前一部分表示與關(guān)鍵節(jié)點(diǎn)T1相關(guān)的航段（共m段）的運(yùn)行成本總和，后一部分表述與關(guān)鍵節(jié)點(diǎn)T2相關(guān)的航段（共n段）的運(yùn)行成本總合；兩者加和最小化，即要求關(guān)鍵節(jié)點(diǎn)的選擇位置，滿足運(yùn)行成本最小。約束條件包括兩關(guān)鍵節(jié)點(diǎn)的位置取值范圍。

1.1.4 基于基本GA算法的單目標(biāo)優(yōu)化模型求解

針對(duì)此單目標(biāo)約束優(yōu)化模型，求解方法有很多，本章采用的遺傳算法具有隱式并行性和全局搜索性兩大主要特點(diǎn)，作為強(qiáng)有力且應(yīng)用廣泛的隨機(jī)搜索和優(yōu)化方法，遺傳算法可能是當(dāng)今影響最廣泛的進(jìn)化計(jì)算方法之一。

遺傳算法實(shí)現(xiàn)過程中的關(guān)鍵要素通常包括決策變量的編解碼方法、適應(yīng)值函數(shù)的選取、遺傳算子等，本求解過程中，關(guān)鍵節(jié)點(diǎn)優(yōu)化模型的GA算法實(shí)現(xiàn)的關(guān)鍵因素具體如下：

1）決策變量的編碼，此處決策變量為T1，T2的位置信息，即（Xi，Yi，Xj，Xj），本文采用浮點(diǎn)型編碼，即編碼值代表決策變量的實(shí)際取值。

2）適應(yīng)值函數(shù)是與目標(biāo)函數(shù)相關(guān)的評(píng)價(jià)函數(shù)，此處目標(biāo)函數(shù)始終為正，因此直接以目標(biāo)函數(shù)為適應(yīng)值函數(shù)。

3）遺傳變異算子包括選擇算子，交叉算子和變異算子。選擇算子作用在于從當(dāng)前代群體中選擇出一些較優(yōu)個(gè)體，將其復(fù)制至下一代群體中，本模型中選擇為比例選擇算子，個(gè)體被選中并遺傳到下一代的概率與該個(gè)體的適應(yīng)度大小成比例。交叉算子采用單點(diǎn)交叉算子；變異算子采用基本位變異算子。

4）進(jìn)化終止條件采用進(jìn)化代數(shù)為200代；種群個(gè)體數(shù)目取每代個(gè)體50個(gè)。

通過上述設(shè)置，處理，實(shí)現(xiàn)關(guān)鍵節(jié)點(diǎn)模型的GA算法求解，即可得到T1，T2對(duì)應(yīng)優(yōu)化方案下的決策變量值。

1.2“三區(qū)”避讓技術(shù)

1.2.1 問題描述

在航路網(wǎng)絡(luò)規(guī)劃過程中，需要考慮一定的空域限制。這些空域限制是指“三區(qū)”，即禁飛區(qū)、限制區(qū)、危險(xiǎn)區(qū)。本文所涉及的航路主干網(wǎng)絡(luò)設(shè)計(jì)不考慮不同時(shí)間段的具體航路，只是從宏觀、全局進(jìn)行航路網(wǎng)絡(luò)設(shè)計(jì)，因此針對(duì)“三區(qū)”，本文以禁飛區(qū)看待，即在“三區(qū)”內(nèi)，飛機(jī)無法穿越、無法布設(shè)航路網(wǎng)絡(luò)?！叭齾^(qū)”避讓優(yōu)化設(shè)計(jì)問題的目標(biāo)在于，使得所設(shè)計(jì)的航路滿足飛機(jī)交通流量需求的同時(shí)保證航路主干網(wǎng)絡(luò)最優(yōu)，并且滿足“三區(qū)”（禁飛區(qū)、限制區(qū)、危險(xiǎn)區(qū)）限制要求，即航路不能穿過三區(qū)。

基于上述描述，“三區(qū)”避讓問題轉(zhuǎn)化為以下幾個(gè)問題：空域的規(guī)劃建模，即以一定方法描述“三區(qū)”以外的可用空域；“優(yōu)化”航路主干網(wǎng)絡(luò)的數(shù)學(xué)描述，即優(yōu)化航路主干網(wǎng)絡(luò)的數(shù)學(xué)建模，“優(yōu)化”航路主干網(wǎng)絡(luò)通常通過多個(gè)網(wǎng)絡(luò)性能指標(biāo)定義，因此該數(shù)學(xué)模型為多目標(biāo)約束優(yōu)化模型；優(yōu)化航路主干網(wǎng)絡(luò)模型的求解算法，該算法需要對(duì)多目標(biāo)問題具有良好適應(yīng)性與求解效率。針對(duì)以上問題，下文給出具體描述。

“三區(qū)”避讓的目的是滿足空域可用性要求，同時(shí)保證航路主干網(wǎng)絡(luò)的性能。航路主干網(wǎng)優(yōu)化模型的目標(biāo)函數(shù)通過網(wǎng)絡(luò)性能指標(biāo)體現(xiàn)，因此目標(biāo)函數(shù)與網(wǎng)絡(luò)優(yōu)化指標(biāo)密不可分。

1）航路網(wǎng)絡(luò)性能參數(shù)優(yōu)化指標(biāo)概念

衡量網(wǎng)絡(luò)優(yōu)化的指標(biāo)包括：網(wǎng)絡(luò)運(yùn)行成本、網(wǎng)絡(luò)連接度、網(wǎng)絡(luò)沖突系數(shù)、網(wǎng)絡(luò)非直線系數(shù)、網(wǎng)絡(luò)可達(dá)性指標(biāo)及航路利用率指標(biāo)等。

2）航路主干網(wǎng)絡(luò)的多目標(biāo)優(yōu)化模型

a.優(yōu)化航路主干網(wǎng)絡(luò)定義

優(yōu)化網(wǎng)絡(luò)的指標(biāo)包括網(wǎng)絡(luò)運(yùn)行成本、沖突指標(biāo)等，在諸多指標(biāo)中，網(wǎng)絡(luò)運(yùn)行成本及網(wǎng)絡(luò)運(yùn)行安全性是最重要的衡量指標(biāo)，此處以網(wǎng)絡(luò)運(yùn)行成本及網(wǎng)絡(luò)運(yùn)行安全性指標(biāo)作為目標(biāo)函數(shù)，量化航路主干優(yōu)化網(wǎng)絡(luò)；而其他性能參數(shù)指標(biāo)可以作為航路網(wǎng)絡(luò)布局方案的評(píng)價(jià)指標(biāo)，以便與現(xiàn)狀進(jìn)行對(duì)比分析。

b.航路主干網(wǎng)絡(luò)的多目標(biāo)優(yōu)化模型

一層航路主干網(wǎng)絡(luò)用有向圖G（N，L，C）表示，其中網(wǎng)絡(luò)節(jié)點(diǎn)集合為N（xi）（包括固定城市節(jié)點(diǎn)和中間節(jié)點(diǎn)），L（li）為所有的有向邊構(gòu)成的集合，C表示航路網(wǎng)過渡網(wǎng)絡(luò)各邊通行能力的集合。變量定義為：fi為網(wǎng)絡(luò)邊/航段的流量；Li為網(wǎng)絡(luò)邊的長(zhǎng)度；ci為網(wǎng)絡(luò)邊/航段的容量；Nc為網(wǎng)絡(luò)中間節(jié)點(diǎn)集合；P={p1（x，y），p2（x，y），…，pk（x，y）}為網(wǎng)絡(luò)節(jié)點(diǎn)位置坐標(biāo)集合；V為航路飛機(jī)平均速度；X為雷達(dá)管制下側(cè)向間隔標(biāo)準(zhǔn)；αij為邊ij夾角；Pi為滿足“三區(qū)”限制，在航路布設(shè)過程中產(chǎn)生的中間節(jié)點(diǎn)。

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

約束條件

該多目標(biāo)約束優(yōu)化模型是以航路主干網(wǎng)絡(luò)安全性與成本效益為目標(biāo)函數(shù)、以“三區(qū)”限制表示為約束。目標(biāo)函數(shù)中Pc為航路主干網(wǎng)絡(luò)的潛在沖突系數(shù)，反映網(wǎng)絡(luò)安全性指標(biāo)；Q為航路主干網(wǎng)絡(luò)運(yùn)行成本指標(biāo)，以飛行總里程表征；約束條件反映在航路路徑選擇必須在鏈接圖規(guī)劃建模中的“三區(qū)”鏈接線上，以滿足三區(qū)避讓要求。

1.2.2 基于NSGA2的多目標(biāo)優(yōu)化模型求解

多目標(biāo)問題求解方法很多，針對(duì)上述多目標(biāo)約束優(yōu)化模型，采用NSGA2算法。這是一種基于Paroet最優(yōu)概念的遺傳算法，是眾多的多目標(biāo)優(yōu)化遺傳算法之中體現(xiàn)Golbderg思想最直接的方法[8-10]。求解流程如圖1所示。

圖1 NSGA2算法流程圖Fig.1 NSGA2 flow chart

以上NSGA2算法過程為：針對(duì)“三區(qū)”避讓優(yōu)化模型的可行解集，并進(jìn)行種群編碼及初始化操作，對(duì)該代種群進(jìn)行遺傳變異產(chǎn)生子代種群，合并父代與子代種群，進(jìn)行非支配排序，并根據(jù)擁擠度進(jìn)行選擇，對(duì)所選擇的個(gè)體進(jìn)行交叉變異操作，依次循環(huán)，直至終止條件，解碼輸出求得解集。針對(duì)本模型，實(shí)現(xiàn)的關(guān)鍵因素如下。

1）模型決策變量編碼及種群初始化

在帶有三區(qū)的航路主干網(wǎng)絡(luò)規(guī)劃空間建?；A(chǔ)上，對(duì)模型決策變量進(jìn)行編碼，模型的決策變量為需求城市對(duì)間的路徑，起點(diǎn)至終點(diǎn)的路徑為P0P1P2…PnPn+1，其中P0表示起點(diǎn)，Pn+1表示終點(diǎn)，要得到的最優(yōu)路徑是對(duì)Pi（i=1，2，…，n）的位置在三區(qū)鏈接線上進(jìn)行調(diào)整，從而得到航路在規(guī)劃空間上滿足網(wǎng)絡(luò)最優(yōu)準(zhǔn)則的布局網(wǎng)絡(luò)[11]。

Pi點(diǎn)在三區(qū)頂點(diǎn)Pi1，Pi2所組成的鏈接線上移動(dòng)，則其具體位置可通過Pi1，Pi2（分別對(duì)應(yīng)三區(qū)的頂點(diǎn)位置信息）進(jìn)行表達(dá)，表達(dá)如式（4）所示。對(duì)于每個(gè)城市需求對(duì)間的路徑都如此處理，共同構(gòu)成模型的決策變量，構(gòu)成航路主干網(wǎng)絡(luò)布局的一個(gè)可行解編碼，然后通過隨機(jī)數(shù)對(duì)種群進(jìn)行初始化。

2）交叉變異算子

該模型對(duì)決策變量的編碼是浮點(diǎn)型編碼，即實(shí)值編碼，因此交叉算子選擇實(shí)值編碼遺傳算法的SBX （simulated binary crossover）交叉，變異算子選擇多項(xiàng)式變異[12-13]。具體實(shí)現(xiàn)流程如下：

SBX：該交叉算子是仿真二進(jìn)制交叉，為

式中：p1k，p2k表示選擇的父代個(gè)體；c1k，c2k表示子代個(gè)體；βk為具有一定概率分布的隨機(jī)數(shù)，其分布可以通過隨機(jī)數(shù)u∈（0，1）按照下述公式產(chǎn)生

PM：多項(xiàng)式變異算子如下

式中：pk表示選擇的父代個(gè)體，其父代基因值上下限分別為pku、pkl，ck表示子代個(gè)體，δk是由下述多項(xiàng)式分布公式產(chǎn)生的較小變量

式中：γk是（0，1）間隨機(jī)數(shù)；ηm是變異分布概率。

3）進(jìn)化終止條件

進(jìn)化終止條件可根據(jù)需求及算法結(jié)果人為選擇，此處選擇進(jìn)化次數(shù)為200次最為終止條件。

2 實(shí)際應(yīng)用分析

基于以上方法，筆者所在項(xiàng)目組協(xié)助中國(guó)民航局空中交通管理局完成了面向2030年的航路網(wǎng)絡(luò)規(guī)劃方案的制定（根據(jù)2010年冬春季班機(jī)時(shí)刻表數(shù)據(jù)對(duì)骨干航路網(wǎng)絡(luò)規(guī)劃方案進(jìn)行流量分配，城市對(duì)航線取規(guī)劃網(wǎng)絡(luò)中的最短路徑）。為有效量化骨干航路網(wǎng)絡(luò)規(guī)劃方案的優(yōu)劣性，建立了綜合反映航路網(wǎng)絡(luò)技術(shù)性能、經(jīng)濟(jì)效益及環(huán)境效益的航路網(wǎng)絡(luò)規(guī)劃方案評(píng)價(jià)指標(biāo)體系。基于該指標(biāo)體系的評(píng)估結(jié)果如表1所示。相比現(xiàn)行骨干航路網(wǎng)，規(guī)劃航路網(wǎng)的網(wǎng)絡(luò)連接度提高了20.4%，周運(yùn)行成本下降了5.19%，非直線系數(shù)下降了5.32%，沖突系數(shù)下降了10.34%，航路利用率（繁忙程度）下降了6.7%，航班可達(dá)性提高了1.26%。這些指標(biāo)說明規(guī)劃航路網(wǎng)絡(luò)的總體性能提升比較顯著，符合總體目標(biāo)要求。

表1 規(guī)劃航路網(wǎng)絡(luò)主要性能指標(biāo)評(píng)估結(jié)果Tab.1 Assessment of designed air route network′s key performance metrics

3 結(jié)語(yǔ)

本文在對(duì)全國(guó)航路網(wǎng)規(guī)劃的問題進(jìn)行理論抽象的基礎(chǔ)上，提出了“關(guān)鍵節(jié)點(diǎn)”優(yōu)化設(shè)計(jì)與“三區(qū)”避讓優(yōu)化設(shè)計(jì)相結(jié)合的網(wǎng)絡(luò)設(shè)計(jì)方法；構(gòu)建了基于基本GA的關(guān)鍵節(jié)點(diǎn)優(yōu)化模型和基于NSGA2的多目標(biāo)優(yōu)化模型，并給出模型求解方法。經(jīng)過對(duì)規(guī)劃航路網(wǎng)絡(luò)的主要性能指標(biāo)進(jìn)行全面評(píng)估表明：網(wǎng)絡(luò)連接度、沖突系數(shù)、非直線系數(shù)等均有較大幅度提升；本文所述的航路網(wǎng)絡(luò)優(yōu)化算法能夠提高航路網(wǎng)絡(luò)的整體利用效率，降低網(wǎng)絡(luò)復(fù)雜度，提高空域利用的靈活性。

[1]民航數(shù)據(jù)公司.我國(guó)航路網(wǎng)絡(luò)規(guī)劃計(jì)劃研究報(bào)告[R].北京:中國(guó)民航總局空管局，2007.

[2] SMITH M J.Existence uniqueness and stability of traffic equilibria[J]. Transportation Research，1979，13B（4）:295-303.

[3]ZHANG XIE，LIU BO，ZHANG JUN，et al.Optimization of Sequencing for Arrival Aircraft Based on Approach Routes[C].The 10th International IEEE Conference on Intelligent Transportation Systems，2007:3-5.

[4]SIDDIQUEE M W.MATHEMATICAL AIDS in Air Route Network Design[C].IEEE Conference on Decision and Control including the 12th Symposium on Adaptive Processes，1973:651-654.

[5] KARIM MEHADHEBI.A methodology for the Design of a Route Network[J].ATM Seminar 2000，2000:30-34.

[6]THOMAS RIVIèRE.Redesign of the European Route Network for Sector-Less[C].23rd Digital Avionics Systems Conference，2004:32-35.

[7] RIVIèRE T，BRISSET P.Shortest Path in Planar Graph and Air Route network[R].JFPC，2005:23-25.

[8]關(guān)志華.非支配排序遺傳算法（NSGA）算子分析[J].管理工程學(xué)報(bào)，2004，12（1）:2-3.

[9]蔣騰旭.智能優(yōu)化算法概述[J].人工智能及識(shí)別技術(shù)，2007:2-3.

[10]袁亞湘.非線性優(yōu)化計(jì)算方法[M].北京：科學(xué)出版社，2008:26-30.

[11]WATTS D J，STROGATZ S H.Collective dynamics of‘small-world’networks[J].Nature，1998:440-442.

[12]周 明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防工業(yè)出版社，2005:128-136.

[13]茍先太，金煒東.有約束優(yōu)化中遺傳算法的應(yīng)用 [J].西南交通大學(xué)學(xué)報(bào)，1997，32（4）:15-23.

（責(zé)任編輯：黃 月）

Methodology of key network nodes optimization and re-stricted airspace avoiding

XU You-chen，ZHU Yan-bo
（Aviation Data Communication Corp oration，Beijing 100191，China）

To solve the problem of improving the air route network （ARN）efficiencies，this paper proposes a methodology of key network nodes optimization and the restricted airspace avoiding.Firstly，the model of key network nodes optimization and the re-stricted airspace avoiding is established.Then，genetic algorithm（GA）is used to solve this model.Finally，practical applications analysis shows that the optimized ARN is better than current ARN on the performance metrics such as the operating cost，the non linear indicator，the connectivity，the reachability，etc.It is proved that the optimization method is efficient and correct by the actual cases.

air traffic management；air route network；topological structure；optimization design；genetic algorithm（GA）

V355.1；X951

A

1674－5590（2013）01－0041－05

2012-05-04；

2012-08-20

國(guó)家科技支撐計(jì)劃項(xiàng)目（2011BAH24B08）

許有臣（1975—），遼寧大連人，工程師，碩士，研究方向?yàn)榭沼蚬芾砼c航行情報(bào).