基于改進(jìn)GA的滑行道路徑?jīng)_突解脫研究

黃邦菊，史繼龍

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

由于航空器數(shù)量的激增使得機(jī)場(chǎng)場(chǎng)面運(yùn)行需求與容量嚴(yán)重失衡，表現(xiàn)為運(yùn)行效率下降、安全性降低與經(jīng)濟(jì)效益差，同時(shí)也增加了機(jī)場(chǎng)運(yùn)行指揮的工作量。統(tǒng)計(jì)報(bào)告表明，滑行道沖突是機(jī)場(chǎng)嚴(yán)重事故征候的重要一環(huán)，因此如何在保證安全的前提下提高滑行道的運(yùn)行使用效率成為當(dāng)下應(yīng)解決的熱點(diǎn)。

隨著滑行過程中的不確定性對(duì)場(chǎng)面目標(biāo)滑行沖突的影響日益凸顯，研究方向也轉(zhuǎn)移到通過提高場(chǎng)面沖突解脫效率進(jìn)行滑行道路徑規(guī)劃[1-2]。國(guó)內(nèi)外學(xué)者就場(chǎng)面沖突解脫進(jìn)行了大量研究。紀(jì)榮等[3]利用GIS(geographic information system,地理信息系統(tǒng))通過改變進(jìn)場(chǎng)滑行速度或延長(zhǎng)地面等待來實(shí)現(xiàn)沖突解脫；Li等[4]通過A*附加約束條件對(duì)滑行路徑進(jìn)行改進(jìn)；朱新平等[5]利用A-SMGCS滑行道沖突預(yù)測(cè)、避免與控制解決路徑規(guī)劃問題。Pesic[6]等首先提出通過遺傳算法對(duì)滑行道路徑進(jìn)行優(yōu)化；Roling和Visser[7]以混合線性擬合對(duì)簡(jiǎn)單滑行道進(jìn)行路徑研究；Deau等[8]根據(jù)飛行計(jì)劃采用GA對(duì)固定路徑滑行航空器進(jìn)行排序；Clare和Richards[9]將路徑與跑道排序進(jìn)行耦合，構(gòu)建MILP模型實(shí)現(xiàn)對(duì)滑行航空器的全局性決策。盡管上述算法在實(shí)際問題中取得顯著成果，但由于航空器數(shù)量的激增使得計(jì)算量大、相應(yīng)時(shí)間過長(zhǎng)，且未考慮不確定因素的影響。為此在分析滑行路徑優(yōu)化特點(diǎn)的基礎(chǔ)上，結(jié)合遺傳算法全局隨機(jī)搜索最優(yōu)、參數(shù)少收斂速度快與滑動(dòng)時(shí)間窗口的時(shí)間敏感性，對(duì)滑行路徑進(jìn)行優(yōu)化和仿真分析。

1 算法模型構(gòu)建

1.1 滑行路徑模型構(gòu)建

本文以時(shí)間窗內(nèi)所有航空器的總滑行時(shí)間F(x)為目標(biāo)函數(shù)且求該函數(shù)的最小值[10]，建立的函數(shù)式為

(1)

模型約束條件構(gòu)建如下:

(2)

(3)

(4)

(5)

式(2)為交叉沖突或尾隨通出的解脫方式，即航空器i與j在節(jié)點(diǎn)p存在潛在沖突，由于航空器設(shè)定滑行速度相同，即沖突點(diǎn)前存在最小距離間隔就可保證安全；式(3)為對(duì)頭沖突解脫方式，假設(shè)航空器i到達(dá)q點(diǎn)后j才達(dá)到q點(diǎn)，且i與j之間保持一定的安全間隔[11-12]；式(4)、式(5)為滑行時(shí)間與滑行控制。交叉沖突、尾隨沖突、對(duì)頭沖突示意圖如圖1～圖3所示。

圖1 交叉沖突示意圖

圖2 尾隨沖突示意圖

圖3 對(duì)頭沖突示意圖

1.2 基于GA沖突解脫模型構(gòu)建

遺傳算法是可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，以決策變量的編碼作為運(yùn)算對(duì)象，直接以適應(yīng)度函數(shù)邊界作為搜索界限，能夠?qū)︼w行區(qū)場(chǎng)面運(yùn)行進(jìn)行群體智能化處理，其沖突解脫實(shí)現(xiàn)步驟如下：

1)設(shè)定初始化種群，這里種群中含有個(gè)體數(shù)為i，并對(duì)每個(gè)航空器個(gè)體(即染色體)進(jìn)行十進(jìn)制編碼(網(wǎng)絡(luò)節(jié)點(diǎn))處理；令網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為n，則每架航空器的滑行路徑表示為基因編碼串。

2)設(shè)定個(gè)體航空器的適應(yīng)度為

(6)

3)根據(jù)式(2)～式(5)場(chǎng)面滑行約束條件，判定適應(yīng)度是否符合實(shí)際間隔條件約束和終止函數(shù)。若滿足則輸出；反之轉(zhuǎn)到4)。

4)根據(jù)航空器優(yōu)先級(jí)和尾流等級(jí)，判定是否滿足時(shí)間約束條件[13]。如符合則進(jìn)行循環(huán)以求新的適應(yīng)度，反之轉(zhuǎn)到5)。

5)根據(jù)f(x)選擇次生航空器個(gè)體；設(shè)定沖突航空器的選擇概率與個(gè)體適應(yīng)度相關(guān)，設(shè)定算子為

(7)

6)采用交叉概率和變異概率可以隨自適應(yīng)度改變的自適應(yīng)遺傳算法，設(shè)定Pc與Pm為

(8)

(9)

式中：fmax為最大適應(yīng)度；favg為平均適應(yīng)度；f為變異交叉函數(shù)中的較大適應(yīng)值；f′為變異個(gè)體適應(yīng)度;k1、k2、k3、k4為設(shè)定參數(shù)。

7)通過交叉與變異產(chǎn)生新個(gè)體，由此構(gòu)成新的優(yōu)化種群，其流程如圖4所示。

2 實(shí)驗(yàn)仿真分析

選取成都雙流機(jī)場(chǎng)某時(shí)段20架航空器為仿真對(duì)象，將機(jī)場(chǎng)場(chǎng)面抽象為二維網(wǎng)絡(luò)圖G=(V,E)，其中V為場(chǎng)面網(wǎng)絡(luò)集合體，E為滑行道集合，該機(jī)場(chǎng)滑行道路徑如圖5所示，其中網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)為210。鑒于一次性求解所有航空器的優(yōu)化路徑不太現(xiàn)實(shí)，可通過整體條塊分割進(jìn)行處理，其核心為航空器的加入與脫離。本文設(shè)定變步長(zhǎng)的滑動(dòng)時(shí)間窗口進(jìn)行求解，窗口設(shè)定為5，滑動(dòng)步長(zhǎng)根據(jù)脫離上一窗口的航班數(shù)進(jìn)行確定。

圖4 改進(jìn)GA算法流程

采用改進(jìn)遺傳算法進(jìn)行仿真，其中遺傳算法的參數(shù)取值為：i=100，k1=0.5,k2=0.9,k3=0.02,k4=0.05，終止迭代次數(shù)為80；按照雙流國(guó)際機(jī)場(chǎng)運(yùn)行手冊(cè)，設(shè)定滑行速度v=50 km/h，滑行最小安全距離間隔標(biāo)準(zhǔn)見表1。

表2中數(shù)據(jù)為雙流機(jī)場(chǎng)某天(13:55—14:11)的對(duì)應(yīng)相應(yīng)機(jī)型的滑行起點(diǎn)與終點(diǎn)。其中進(jìn)場(chǎng)航空器起點(diǎn)位置為跑道出口，終點(diǎn)為停機(jī)位；反之離場(chǎng)航空器起點(diǎn)為停機(jī)位，終點(diǎn)為跑道等待點(diǎn)，其中進(jìn)場(chǎng)設(shè)為1，離場(chǎng)設(shè)為0。

將所屬航空器的節(jié)點(diǎn)坐標(biāo)代入改進(jìn)GA算法中，并與傳統(tǒng)的FCFS(first come first service)下的滑行時(shí)間進(jìn)行對(duì)比分析，其改進(jìn)前后時(shí)間見表3。

圖5 雙流機(jī)場(chǎng)滑行路徑

表1 航空器滑行道的最小距離和時(shí)間間隔標(biāo)準(zhǔn)

將迭代前后的數(shù)據(jù)導(dǎo)入柱狀圖中，如圖6所示，可以看出改進(jìn)后滑行時(shí)間分別縮短[22.7,9,10.2,12.4,11.4,6.2,16,17.4,20.3,19.7](單位:s),證明改進(jìn)GA的滑行路徑規(guī)劃是有效的，能夠有效縮短航空器在滑行道的滑行時(shí)間，進(jìn)而提高機(jī)場(chǎng)運(yùn)行效率。

表2 航班起始點(diǎn)與終點(diǎn)

表3 航空器改進(jìn)前后滑行時(shí)間 單位:s

圖6 航空器改進(jìn)前后滑行時(shí)間柱狀圖

同時(shí)將約束條件及遺傳算法設(shè)定參數(shù)代入模型進(jìn)行求解。因Rastrigin函數(shù)經(jīng)常用來作智能優(yōu)化測(cè)試單位，因此可利用optimtool工具箱求解，其仿真結(jié)果如圖7、圖8所示。

圖7 改進(jìn)GA全局?jǐn)可⑿詸z驗(yàn)

圖8 改進(jìn)GA收斂最小值檢驗(yàn)

通過圖7、圖8可知，所選取安全間隔范圍大于規(guī)定安全距離間隔，且全局趨向于原點(diǎn)收斂，證明改進(jìn)GA算法在對(duì)變異交叉算子進(jìn)行處理時(shí)所需處理較少，可有效減少反應(yīng)時(shí)間。且隨著迭代次數(shù)增加，全局目標(biāo)函數(shù)均有峰值出現(xiàn)，證明在時(shí)間、距離及相應(yīng)滑行道數(shù)目限制下，不會(huì)因種群敏感性出現(xiàn)目標(biāo)函數(shù)發(fā)散的情況。

3 結(jié)論

本文研究了基于改進(jìn)GA的機(jī)場(chǎng)場(chǎng)面目標(biāo)沖突解脫問題，并建立了基于改進(jìn)GA的滑動(dòng)時(shí)間窗模型。仿真實(shí)驗(yàn)表明改進(jìn)GA從智能優(yōu)化角度上具有自適應(yīng)性與平穩(wěn)性，自身的收斂性相比于傳統(tǒng)GA較強(qiáng)，即能夠?qū)崿F(xiàn)多航空器滑行的實(shí)時(shí)響應(yīng)處理；從時(shí)間與經(jīng)濟(jì)效益角度進(jìn)行考慮，因設(shè)定了時(shí)間窗口和步長(zhǎng)可對(duì)不同方向進(jìn)離場(chǎng)的航空器在滿足管制要求基礎(chǔ)上進(jìn)行調(diào)配處理，可有效減少跑道入侵、滑行道沖突的風(fēng)險(xiǎn)[14]。