蔣 昕，胡明華，張 穎，田 文（.南京航空航天大學(xué)民航學(xué)院，江蘇　南京2006；2.中船重工第709研究所，湖北　武漢430074）

?

基于飛行受限區(qū)劃設(shè)的航班改航研究

蔣 昕1，2，胡明華1，張 穎1，田 文1
（1.南京航空航天大學(xué)民航學(xué)院，江蘇南京210016；2.中船重工第709研究所，湖北武漢430074）

摘要：危險(xiǎn)天氣是影響飛行安全，導(dǎo)致航班延誤的重要原因。在對(duì)危險(xiǎn)天氣影響下的飛行受限區(qū)進(jìn)行劃設(shè)的基礎(chǔ)上，采用一元線性回歸預(yù)測(cè)模型和一種改進(jìn)的飛行受限區(qū)邊界預(yù)測(cè)方法，實(shí)現(xiàn)對(duì)飛行受限區(qū)的位置及邊界的動(dòng)態(tài)預(yù)測(cè)，并以所預(yù)測(cè)的飛行受限區(qū)作為約束，在考慮飛行性能和安全的基礎(chǔ)上，以最短改航距離、最小轉(zhuǎn)彎角、最少轉(zhuǎn)彎點(diǎn)為優(yōu)化目標(biāo)建立改航路徑規(guī)劃模型，采用遺傳算法求解。仿真結(jié)果表明：所規(guī)劃出的改航路徑能避讓飛行受限區(qū)并滿足安全、經(jīng)濟(jì)以及減少管制員工作負(fù)荷的目標(biāo)。

關(guān)鍵詞：飛行受限區(qū)域；位置預(yù)測(cè)；邊界預(yù)測(cè)；遺傳算法；改航

隨著航空運(yùn)輸業(yè)的快速發(fā)展，航班的大量延誤也隨之而來(lái)，危險(xiǎn)天氣是威脅航空器安全導(dǎo)致航班延誤的重要原因。改航作為改善空域資源的重要手段，可以避免不必要的地面等待，有效降低由于天氣原因帶來(lái)的航班延誤。為了在危險(xiǎn)天氣下合理利用空域資源，降低航班延誤，需要對(duì)改航策略進(jìn)行深入研究。

改航問(wèn)題的研究開(kāi)始于1993年，經(jīng)過(guò)20多年的發(fā)展，國(guó)內(nèi)外已取得了一些具有代表性的研究成果。1993年，Dixon和Weidner建立了在網(wǎng)格改航環(huán)境下的改航策略[1]；2002年，宋柯等研究了基于已有航路點(diǎn)的A*搜索算法[3]；2009年，徐肖豪等研究了基于人工勢(shì)場(chǎng)算法的改航路徑規(guī)劃方法[4]；2011年，Maritin O Nicholes等人提出了協(xié)同改航路徑規(guī)劃的研究[5]；2012年，Christine Taylor和Craig Wanke使用模擬退火算法規(guī)劃改航路徑，在考慮改航路徑可操作性的前提下對(duì)航班進(jìn)行路徑規(guī)劃，并對(duì)生成的改航路徑進(jìn)行評(píng)估[2]；2012年，孟令航等研究了不確定強(qiáng)對(duì)流天氣下動(dòng)態(tài)改航路徑規(guī)劃方法[6]。

從以上的研究成果可以看出，前期學(xué)者們著重于改航的路徑規(guī)劃，未充分考慮危險(xiǎn)天氣的等級(jí)和運(yùn)動(dòng)趨勢(shì)等方面對(duì)航路的影響。借鑒前人研究，進(jìn)一步對(duì)危險(xiǎn)天氣區(qū)域進(jìn)行精確的劃設(shè)和預(yù)測(cè)，將預(yù)測(cè)的飛行受限區(qū)作為約束，充分考慮航空器性能以及飛行安全等其他限制因素，建立改航路徑規(guī)劃的數(shù)學(xué)模型，并采用遺傳算法對(duì)模型進(jìn)行求解。

1 飛行受限區(qū)的劃設(shè)和預(yù)測(cè)

飛行危險(xiǎn)天氣包括暴雨、雷暴、冰雹等，這些危險(xiǎn)天氣會(huì)給航空器飛行帶來(lái)安全隱患，造成航班延誤，影響空域系統(tǒng)的運(yùn)行。為了減少危險(xiǎn)天氣下的航班延誤，降低經(jīng)濟(jì)損失，對(duì)飛行受限區(qū)域進(jìn)行準(zhǔn)確的劃設(shè)和預(yù)測(cè)就顯得十分重要。

根據(jù)雷達(dá)回波圖對(duì)飛行受限區(qū)進(jìn)行劃設(shè)，結(jié)合飛行受限區(qū)的歷史數(shù)據(jù)，利用一元線性回歸預(yù)測(cè)方法，對(duì)飛行受限區(qū)的移動(dòng)進(jìn)行精確預(yù)測(cè)，同時(shí)提出一種飛行受限區(qū)邊界預(yù)測(cè)的新方法。

1.1 飛行受限區(qū)劃設(shè)

文獻(xiàn)[7]指出，當(dāng)雷達(dá)回波等級(jí)≥41 dBZ時(shí)，航空器需要避讓；因此，認(rèn)為雷達(dá)回波等級(jí)≥41 dBZ的區(qū)域?yàn)槲ｋU(xiǎn)天氣區(qū)域。根據(jù)氣象雷達(dá)回波圖，通過(guò)圖像處理技術(shù)分離出回波等級(jí)≥41 dBZ的危險(xiǎn)天氣區(qū)域，并采用凸多邊形劃設(shè)飛行受限區(qū)。對(duì)劃設(shè)的飛行受限區(qū)，飛行受限區(qū)劃設(shè)步驟如下：

1）提取危險(xiǎn)天氣數(shù)據(jù)。對(duì)雷達(dá)反射率圖進(jìn)行處理，獲得每個(gè)反射率等級(jí)的RGB顏色值，并對(duì)雷達(dá)反射率圖進(jìn)行遍歷，保存反射率等級(jí)≥41 dBZ的像素點(diǎn)，這些像素點(diǎn)構(gòu)成的區(qū)域即為危險(xiǎn)天氣區(qū)域，同時(shí)根據(jù)雷達(dá)所在位置的經(jīng)緯度坐標(biāo)以及分辨率，確定每個(gè)危險(xiǎn)天氣像素點(diǎn)對(duì)應(yīng)的經(jīng)緯度坐標(biāo)。

2）圖片二值化。對(duì)危險(xiǎn)天氣區(qū)域圖片進(jìn)行二值化處理，凸顯危險(xiǎn)天氣區(qū)域，灰度化背景。

3）輪廓檢索。調(diào)用OpenCV中的cvFindCounters( )函數(shù)，在上一步得到的二值圖像中檢索危險(xiǎn)天氣區(qū)域輪廓；

4）多邊形逼近。調(diào)用OpenCV中的cvApproxPoly( )函數(shù)，對(duì)上一步得到的輪廓集用指定精度的多邊形逼近，并生成逼近后的簡(jiǎn)單多邊形輪廓集。

5）生成凸包多邊形。對(duì)上一步得到的簡(jiǎn)單多邊形輪廓集中的每個(gè)簡(jiǎn)單多邊形，調(diào)用MATLAB中的ConvexHull( )函數(shù)，求得每個(gè)簡(jiǎn)單多邊形的凸包，這些凸多邊形，即為需要避讓的天氣區(qū)域。

對(duì)于上述操作得到的飛行受限區(qū)，還需要進(jìn)行特殊處理：

1）去噪處理。根據(jù)航空器性能數(shù)據(jù)庫(kù)，取420節(jié)作為航空器飛行速度，對(duì)于尺寸小于7 mile的飛行受限區(qū)（即在飛行受限區(qū)內(nèi)以420節(jié)速度飛行1 min），可以忽略不計(jì)。

2）合并處理。根據(jù)我國(guó)允許航空器繞飛的規(guī)定：在兩個(gè)云體邊界之間的最小距離不少于20 km的情況下，航空器可以從中間通過(guò)[8]；因此，將飛行受限區(qū)之間的距離小于20 km的飛行受限區(qū)合并成一個(gè)。

1.2 飛行受限區(qū)移動(dòng)預(yù)測(cè)模型

在前期研究中，多數(shù)學(xué)者把危險(xiǎn)天氣假設(shè)成不變化的多邊形，少部分學(xué)者簡(jiǎn)單考慮到危險(xiǎn)天氣線性移動(dòng)情況[9]，但這些都是在假設(shè)危險(xiǎn)天氣移動(dòng)速度和方向已知的情況下進(jìn)行研究的，然而實(shí)際上并不能方便的得知危險(xiǎn)天氣的移動(dòng)速度。本文結(jié)合歷史數(shù)據(jù)，利用一元線性回歸預(yù)測(cè)方法，對(duì)飛行受限區(qū)的移動(dòng)進(jìn)行精確預(yù)測(cè)。

利用墨卡托投影將飛行受限區(qū)的經(jīng)、緯度坐標(biāo)轉(zhuǎn)為屏幕坐標(biāo)，將飛行受限區(qū)域的質(zhì)心坐標(biāo)作為強(qiáng)對(duì)流單體云團(tuán)的位置。根據(jù)不斷更新的氣象雷達(dá)數(shù)據(jù)，研究飛行受限區(qū)域沿x、y方向移動(dòng)與時(shí)間的關(guān)系，建立飛行受限區(qū)域移動(dòng)預(yù)測(cè)模型。

由于本文使用的氣象雷達(dá)數(shù)據(jù)更新頻率是5 min，以預(yù)報(bào)的起始時(shí)間t0為基準(zhǔn)，將預(yù)報(bào)時(shí)間ti（i=1，2，3，…）轉(zhuǎn)化為預(yù)報(bào)時(shí)刻Ti（Ti=1，2，3，…）：

根據(jù)強(qiáng)對(duì)流天氣單體云團(tuán)在過(guò)去多個(gè)時(shí)刻的質(zhì)心位置，發(fā)現(xiàn)時(shí)間T分別與云團(tuán)質(zhì)心的位置x和y有著特殊的關(guān)系，可以近似表示為一條直線。采用一元線性回歸分析，根據(jù)n個(gè)歷史時(shí)刻Ti（i=1，2，…，n）云團(tuán)質(zhì)心的位置xi和yi，將x-T，y-T擬合成x=kx×T+bx，y=kyT+by兩條直線，其中kx，ky為擬合直線x-T，y-T的斜率，bx，by為擬合直線x-T，y-T的截距。在未來(lái)時(shí)刻Tn+j（j=1，2，…），強(qiáng)對(duì)流天氣單體云團(tuán)的位置為

1.3 飛行受限區(qū)域邊界預(yù)測(cè)

在前期研究中，多數(shù)學(xué)者認(rèn)為強(qiáng)對(duì)流單體云團(tuán)以已知的速度或加速度膨脹或收縮[9]。然而，在云團(tuán)實(shí)際運(yùn)動(dòng)中，云團(tuán)膨脹或收縮的速度或加速度很難直接獲取。提出一種新的飛行受限區(qū)域邊界預(yù)測(cè)方法，在未知云團(tuán)膨脹或收縮的速度或加速度時(shí)，根據(jù)歷史飛行受限區(qū)域邊界變化預(yù)測(cè)未來(lái)飛行受限區(qū)域邊界。

將飛行受限區(qū)域邊界變化視為勻速，根據(jù)當(dāng)前飛行受限區(qū)域Ft和前一時(shí)刻飛行受限區(qū)域Ft-1的邊界，預(yù)測(cè)未來(lái)飛行受限區(qū)域Ft+j（j=1，2，…）的邊界。預(yù)測(cè)步驟如下：

輸入：當(dāng)前時(shí)刻飛行受限區(qū)域Fα的x個(gè)頂點(diǎn)坐標(biāo)pt1，…，ptx以及質(zhì)心坐標(biāo)Ot（x，y），前一時(shí)刻飛行受限區(qū)域Ft-1的頂點(diǎn)坐標(biāo)p1t-1，…，pβt－1以及質(zhì)心坐標(biāo)Ot-1（x，y），未來(lái)t＋i時(shí)刻飛行受限區(qū)域Ft＋i質(zhì)心位置的預(yù)測(cè)坐標(biāo)O（x，y）t＋i（i=1，2，…）；

1）分別計(jì)算Ft、Ft-1的質(zhì)心坐標(biāo)由Ot（x，y）、Ot-1（x，y）移動(dòng)到未來(lái)時(shí)刻t＋i（i=1，2，…）Ft+i的質(zhì)心位置后Ot＋i（x，y），頂點(diǎn)pt1，…，ptnp1t-1，…，pβt－1的位置坐標(biāo)，記p1t，…，pαtp1t-1，…，pβt－1，頂點(diǎn)p1t，…，pαtp1t-1，…，pβt－1構(gòu)成經(jīng)Ft、Ft-1移動(dòng)后的多邊形Ft、Ft-1；

2）以O(shè)t＋i（x，y）為中心，向Ft的頂點(diǎn)，…，做射線Ot＋1（x，y），…，Ot＋1（x，y），射線Ot＋1（x，y），…，Ot＋1（x，y）分別與多邊形Ft-1相交于點(diǎn)q1，…，qα；

3）計(jì)算Ft邊界相對(duì)于Ft-1的變化值，xI=（x）-qI（x）（I＝1，…，α），yI=（y）-qI（y）（I＝1，…，α）其中（x）、（y）為頂點(diǎn)的x、y坐標(biāo)值，qI（x）、qI（y）為交點(diǎn)的x、y坐標(biāo)值；

5）順序連接點(diǎn)pt+i1，…，pt+iα，即形成飛行受限區(qū)域Ft+j，如圖1所示。

圖1 飛行受限區(qū)域邊界預(yù)測(cè)示意圖Fig.1 Prediction diagram of flow constrained area boundary

采用精確度DaF和偏差度DdF對(duì)預(yù)測(cè)的飛行受限區(qū)域邊界進(jìn)行評(píng)估[5]。其中，精確度用來(lái)評(píng)估飛行受限區(qū)域劃設(shè)的準(zhǔn)確性，指標(biāo)越大，準(zhǔn)確性越好；偏差度用來(lái)評(píng)估飛行受限區(qū)域劃設(shè)的安全性，指標(biāo)越小，安全性越好。假設(shè)當(dāng)前時(shí)刻為t，預(yù)測(cè)未來(lái)t+i時(shí)刻飛行受限區(qū)域?yàn)镕ft+i，實(shí)際觀測(cè)的飛行受限區(qū)域?yàn)镕at+i，則

1.4 固定時(shí)段內(nèi)的飛行受限區(qū)

2009年，李雄在文獻(xiàn)[10]中提出，假設(shè)航班在改航起始點(diǎn)的時(shí)刻為ts，改航結(jié)束點(diǎn)的時(shí)刻為td，則

式中：σR為實(shí)施改航后增加的航程與原計(jì)劃航路航程百分比的估計(jì)值，大多數(shù)情況下是0.2；DR是改航開(kāi)始點(diǎn)到改航結(jié)束點(diǎn)之間的航程；Vh是巡航速度，一般為420節(jié)，本文取800 km·h-1。

根據(jù)上式，在確定改航起始點(diǎn)和結(jié)束點(diǎn)之后，利用預(yù)估的改航時(shí)間td和1.2節(jié)的移動(dòng)預(yù)測(cè)模型以及1.3節(jié)的邊界預(yù)測(cè)模型，預(yù)測(cè)改航過(guò)程中飛行受限區(qū)的位置以及邊界，將改航過(guò)程中由于飛行受限區(qū)移動(dòng)形成的所有受限區(qū)合并，得到改航所在時(shí)段內(nèi)的飛行受限區(qū)。

2 改航模型與算法

以單個(gè)航班的改航作為研究對(duì)象，進(jìn)行改航路徑規(guī)劃，除了考慮避開(kāi)飛行受限區(qū)外，還要考慮到飛行成本、飛機(jī)性能、飛行員工作負(fù)荷等因素。選取最短改航距離，最小轉(zhuǎn)彎角度，最少轉(zhuǎn)彎點(diǎn)為優(yōu)化目標(biāo)建立改航路徑規(guī)劃模型，并采用遺傳算法對(duì)模型求解。

2.1 改航模型

在實(shí)際管制運(yùn)行中，出于航路飛行安全因素以及飛行員操作負(fù)荷考慮，在繞飛危險(xiǎn)天氣區(qū)域時(shí)航向的改變量不應(yīng)超過(guò)飛行性能所允許的最大角度，為了航空器能順利完成2次轉(zhuǎn)彎，飛行航班的轉(zhuǎn)彎半徑不應(yīng)小于最小轉(zhuǎn)彎半徑，由于改航點(diǎn)數(shù)量決定管制指揮的次數(shù)，為了減輕管制員的工作負(fù)荷，在實(shí)施改航的過(guò)程中，盡可能地減少改航點(diǎn)數(shù)量[11]。因此，將改航路徑長(zhǎng)度、改航的轉(zhuǎn)彎角度以及改航點(diǎn)數(shù)量作為約束條件，將改航路徑最短，轉(zhuǎn)彎點(diǎn)數(shù)量最少，轉(zhuǎn)彎角度變化最小作為優(yōu)化目標(biāo)建立改航路徑規(guī)劃模型。為了實(shí)現(xiàn)對(duì)多個(gè)目標(biāo)的綜合處理，將各個(gè)指標(biāo)值進(jìn)行無(wú)量綱化處理，通過(guò)線性加權(quán)轉(zhuǎn)化為單目標(biāo)進(jìn)行求解。由此建立的改航數(shù)學(xué)模型如下：

參數(shù)定義：CL，CT，CA分別代表距離代價(jià)，轉(zhuǎn)彎角數(shù)量代價(jià)，轉(zhuǎn)彎角度變化代價(jià)；ω1，ω2，ω3分別代表距離代價(jià)，轉(zhuǎn)彎角數(shù)量代價(jià)，轉(zhuǎn)彎角度變化代價(jià)的權(quán)重；ps，pi，pD：分別代表改航起始點(diǎn)，改航過(guò)程中的轉(zhuǎn)彎點(diǎn)，改航結(jié)束點(diǎn)；D（pi，pi+1）Fj

兩個(gè)改航點(diǎn)之間路徑距飛行受限區(qū)域的最小距離；Dmin為允許改航路徑偏離飛行受限區(qū)域的最小距離，通常取10 km；d（ps，pD）為改航起始點(diǎn)到改航結(jié)束點(diǎn)之間原航路距離；d（pi，pi+1）為改航過(guò)程中兩個(gè)轉(zhuǎn)彎點(diǎn)之間的距離；dmin為改航過(guò)程中兩個(gè)轉(zhuǎn)彎點(diǎn)之間的最短允許距離，通常取7.4 km；NT為改航路徑中轉(zhuǎn)彎角的個(gè)數(shù)；Nmax為改航路徑中允許最大的轉(zhuǎn)彎角數(shù)量，通常取8個(gè)；θ為改航過(guò)程中轉(zhuǎn)彎角的大??；θmax為改航過(guò)程中允許的最大轉(zhuǎn)彎角度，通常取90°；Fj為第j個(gè)飛行受限區(qū)。

目標(biāo)函數(shù)（7）說(shuō)明當(dāng)目標(biāo)函數(shù)取最小值時(shí)，可以獲得改航的最優(yōu)路徑，式（8）～式（10）分別對(duì)距離代價(jià)、轉(zhuǎn)彎角個(gè)數(shù)代價(jià)、轉(zhuǎn)彎角度變化代價(jià)進(jìn)行了歸一化處理，并保證：CL越小，改航后的路徑長(zhǎng)度越短；CT越小，轉(zhuǎn)彎點(diǎn)個(gè)數(shù)越少；CA越小，轉(zhuǎn)彎角變化越小。

約束條件（11），（12）保證系數(shù)權(quán)重之和為1且為正值；式（13）保證改航路徑安全性和可行性；式（14）～式（16）限制改航距離，最大轉(zhuǎn)彎角度以及最大轉(zhuǎn)彎點(diǎn)個(gè)數(shù)。

2.2 改航算法

遺傳算法(Genetic Algorithm)是一類借鑒生物界的進(jìn)化規(guī)律演化而來(lái)的隨機(jī)化搜索方法。由于該算法不受搜索空間的限制性假設(shè)的約束，以及算法本身固有的并行性特點(diǎn)，采用遺傳算法能有效的解決路徑規(guī)劃問(wèn)題[12]。

當(dāng)航空器飛行過(guò)程中受到危險(xiǎn)天氣影響而無(wú)法按照預(yù)定航路飛行時(shí)，采取改航策略，重新為航空器規(guī)劃處一條新的航路。為了實(shí)施改航策略，我們做出如下假設(shè)：①航空器改航可以簡(jiǎn)化成一個(gè)二維平面，將航空器視為一個(gè)運(yùn)動(dòng)的質(zhì)點(diǎn)；②改航的起始點(diǎn)和結(jié)束點(diǎn)已知，航空器的以恒定的巡航速度飛行；③飛行受限區(qū)在二維空間中用多邊形表示；④將二維空間網(wǎng)格化處理建立改航環(huán)境模型，改航起始點(diǎn)的坐標(biāo)為（0，0）。

2.2.1 遺傳算法參數(shù)設(shè)置

1）路徑編碼：在改航環(huán)境模型中，改航路徑是由一系列轉(zhuǎn)彎點(diǎn)按照航空器運(yùn)動(dòng)的先后順序連接而形成，為了直觀的顯示航空器位置，方便遺傳算法的交叉和變異操作，將改航的路徑中轉(zhuǎn)彎點(diǎn)的坐標(biāo)（xi，yi）作為遺傳算法中染色體的一個(gè)基因，則一條改航路徑中的所有轉(zhuǎn)彎點(diǎn)序列（x1，y1）……（xi，yi）構(gòu)成一個(gè)染色體。

2）初始種群生成：由于式（14）～式（16）中約束條件限制，為了保證初始種群中的每個(gè)個(gè)體滿足最短航路長(zhǎng)度、最大轉(zhuǎn)彎點(diǎn)個(gè)數(shù)以及最大轉(zhuǎn)彎角度限制，初始種群個(gè)體需要按如下規(guī)則生成：①隨機(jī)生成轉(zhuǎn)彎點(diǎn)個(gè)數(shù)，保證轉(zhuǎn)彎點(diǎn)個(gè)數(shù)滿足最大轉(zhuǎn)彎點(diǎn)個(gè)數(shù)約束限制；②在搜索空間中，為每個(gè)轉(zhuǎn)彎點(diǎn)在環(huán)境空間中隨機(jī)生成位置，這些位置組成染色體的基因；③對(duì)染色體的基因利用修復(fù)算子進(jìn)行修復(fù)，保證染色體滿足最短航路和最大轉(zhuǎn)彎角限制（修復(fù)算子詳細(xì)介紹見(jiàn)7）。

3）適應(yīng)度函數(shù)：在遺傳算法中，適應(yīng)度高的個(gè)體相對(duì)于適應(yīng)度低的個(gè)體遺傳到下一代的概率大。由于改航策略模型求解的目標(biāo)函數(shù)是改航成本最小問(wèn)題，因此需要對(duì)目標(biāo)函數(shù)進(jìn)行轉(zhuǎn)換，生成遺傳算法所需要的適應(yīng)度函數(shù)。取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，計(jì)算中為了避免改航成本為0時(shí)造成適應(yīng)度函數(shù)分母無(wú)意義的情況，給分母加上一個(gè)正整數(shù)1，則對(duì)于染色體x的適應(yīng)度函數(shù)為

其中C（x）為染色體x的目標(biāo)函數(shù)。同時(shí)，采用修復(fù)算子使改航路徑滿足式（14）～（16）的約束限制，為了滿足式（13）的約束限制，引入罰函數(shù)。對(duì)于與飛行受限區(qū)有交點(diǎn)的改航路徑，采用罰函數(shù)，對(duì)C（x）進(jìn)行修正，修正公式如下：

上式，保證當(dāng)改航路徑與飛行受限區(qū)有交點(diǎn)時(shí)的改航成本C（x）遠(yuǎn)大于無(wú)交點(diǎn)時(shí)的改航成本C（x），因此，該路徑染色體的適應(yīng)度函數(shù)非常小，被遺傳到下一代的概率幾乎為0。

4）選擇算子：為了滿足對(duì)于選擇算子的要求，采用輪盤(pán)賭和精英保留策略進(jìn)行選擇操作。通過(guò)輪盤(pán)賭方法選擇個(gè)體進(jìn)行交叉和變異操作，保證個(gè)體被選擇的概率與其適應(yīng)度值成正比，精英保留策略通過(guò)將每代的最優(yōu)個(gè)體進(jìn)行保留，直接遺傳到下一代，來(lái)保證遺傳算法的全局收斂性。

5）交叉算子：靜態(tài)改航路徑規(guī)劃算法采用單點(diǎn)交叉的方式進(jìn)行交叉操作，過(guò)程如下：對(duì)于父親個(gè)體改航路徑中的NT個(gè)轉(zhuǎn)彎點(diǎn)，從［1，NT－1］中隨機(jī)產(chǎn)生一個(gè)轉(zhuǎn)彎點(diǎn)作為交叉點(diǎn)O1，同理從母親個(gè)體的改航路徑中隨機(jī)選擇一個(gè)轉(zhuǎn)彎點(diǎn)作為交叉點(diǎn)O2，將父親O1點(diǎn)后的路徑與母親個(gè)體O2點(diǎn)后的路徑進(jìn)行交換，形成兩個(gè)新的子代個(gè)體。對(duì)生成的新個(gè)體，采用修復(fù)算子進(jìn)行修復(fù)，以保證滿足約束限制。

圖2為兩條改航路徑R1和R2，對(duì)應(yīng)的轉(zhuǎn)彎角數(shù)量均為3，進(jìn)行交叉操作：在路徑R1中隨機(jī)選擇一個(gè)轉(zhuǎn)彎作為交叉點(diǎn)O1＝RondomNum[1，2]，這里O1=2；在路徑R2中隨機(jī)選擇一個(gè)轉(zhuǎn)彎作為交叉點(diǎn)O2＝RondomNum [1，2]，這里O2=1；將路徑R1的交叉點(diǎn)O1之后的路徑與路徑R2的交叉點(diǎn)O2之后的路徑交換后，形成新的路徑如圖3所示。

圖2 雙親個(gè)體路徑示意圖Fig. 2 Parents individual path diagram

圖3 交叉操作后子代個(gè)體路徑示意圖Fig. 3 Cross operation progeny path diagram

在圖2，圖3中PS，PD為改航路徑的起始點(diǎn)和結(jié)束點(diǎn)，細(xì)線和粗線分別代表兩條改航路徑。

圖4 改變坐標(biāo)變異操作示意圖Fig. 4 Operation diagram of changing coordinate

6）變異算子：為了更好的進(jìn)行變異，增加遺傳算法的局部搜索能力，保證變異的多樣性，采用啟發(fā)式變異，通過(guò)改變某一個(gè)轉(zhuǎn)彎點(diǎn)的坐標(biāo)，刪除某一個(gè)轉(zhuǎn)彎點(diǎn)和增加一個(gè)轉(zhuǎn)彎點(diǎn)三種方法進(jìn)行變異操作。對(duì)生成的新個(gè)體，采用修復(fù)算子進(jìn)行修復(fù)，以保證滿足約束限制。圖4，圖6分別為改變轉(zhuǎn)彎點(diǎn)坐標(biāo)、增加轉(zhuǎn)彎點(diǎn)以及刪除轉(zhuǎn)彎點(diǎn)的操作示意圖：

圖5 刪除坐標(biāo)點(diǎn)變異操作示意圖Fig. 5 Operation diagram of deleting coordinate

圖6 增加坐標(biāo)點(diǎn)變異操作示意圖Fig. 6 Operation diagram of adding coordinate

圖4表示轉(zhuǎn)彎點(diǎn)P2改變坐標(biāo)變?yōu)檗D(zhuǎn)彎點(diǎn)P2′形成新的改航路徑；圖5表示刪除轉(zhuǎn)彎點(diǎn)P2形成新的改航路徑；圖6表示在轉(zhuǎn)彎點(diǎn)P2與P3之間增加新的轉(zhuǎn)彎點(diǎn)PNT形成新的改航路徑。

7）修復(fù)操作：為了滿足約束條件的限制，引入修復(fù)算子，對(duì)改航路徑進(jìn)行修復(fù)，確保得到可行解。每當(dāng)產(chǎn)生新的個(gè)體時(shí)，均需要進(jìn)行修復(fù)操作。修復(fù)操作如下：①對(duì)染色體中的每個(gè)轉(zhuǎn)彎點(diǎn)（即改航路徑中的每個(gè)轉(zhuǎn)彎點(diǎn)）按照坐標(biāo)x值的大小排序，保證改航路徑無(wú)回路；②對(duì)排序后的染色體，判斷相鄰2個(gè)轉(zhuǎn)彎點(diǎn)之間的距離，對(duì)于小于7.4 km的兩個(gè)轉(zhuǎn)彎點(diǎn)，刪除其中一個(gè)，保證滿足最小航段距離限制，同時(shí)對(duì)多個(gè)在同一條直線的轉(zhuǎn)彎點(diǎn)，進(jìn)行刪除操作，保證每個(gè)點(diǎn)均為轉(zhuǎn)彎點(diǎn)；③對(duì)染色體的轉(zhuǎn)彎點(diǎn)個(gè)數(shù)進(jìn)行判斷，對(duì)于長(zhǎng)度大于最大轉(zhuǎn)彎點(diǎn)個(gè)數(shù)的染色體，隨機(jī)刪除其中的一個(gè)轉(zhuǎn)彎點(diǎn)，保證滿足最大轉(zhuǎn)彎點(diǎn)個(gè)數(shù)的限制；④檢查染色體中每個(gè)轉(zhuǎn)彎點(diǎn)所對(duì)應(yīng)的轉(zhuǎn)彎角度，若存在不滿足最大轉(zhuǎn)彎角度限制的轉(zhuǎn)彎點(diǎn)，則對(duì)該轉(zhuǎn)彎點(diǎn)進(jìn)行微調(diào)，使其滿足最大轉(zhuǎn)彎的約束限制。

3 算例分析

3.1 飛行受限區(qū)算例分析

根據(jù)某氣象雷達(dá)數(shù)據(jù)顯示，2015年4月2日17:37至18:22之間，東北方向有一大面積強(qiáng)對(duì)流天氣。根據(jù)17:37至17:52之間的歷史氣象雷達(dá)數(shù)據(jù)，將危險(xiǎn)天氣轉(zhuǎn)為飛行受限區(qū)域，其歷史預(yù)報(bào)時(shí)間、飛行受限區(qū)對(duì)應(yīng)的質(zhì)心經(jīng)緯度以及利用墨卡托投影轉(zhuǎn)為屏幕坐標(biāo)的位置如表1所示：

利用1.2節(jié)的模型，對(duì)該危險(xiǎn)天氣未來(lái)30 min內(nèi)的位置移動(dòng)進(jìn)行預(yù)測(cè)，然后根據(jù)位置預(yù)測(cè)結(jié)果利用1.3節(jié)的飛行受限區(qū)域邊界預(yù)測(cè)方法，對(duì)未來(lái)30 min內(nèi)的飛行受限區(qū)域邊界進(jìn)行預(yù)測(cè)。

根據(jù)移動(dòng)預(yù)測(cè)和邊界預(yù)測(cè)結(jié)果生成飛行受限區(qū)域，利用1.3節(jié)中評(píng)估模型對(duì)預(yù)測(cè)生成的飛行受限區(qū)進(jìn)行評(píng)估，則預(yù)測(cè)和評(píng)估結(jié)果如表2所示。從表中可以得出隨著預(yù)測(cè)的時(shí)間推移，預(yù)測(cè)的精確性下降，偏差度升高的結(jié)論。因此，本文所采用的預(yù)測(cè)模型適用于短時(shí)段內(nèi)的預(yù)測(cè)，為了保證改航的安全，預(yù)測(cè)模型應(yīng)該應(yīng)用于實(shí)時(shí)戰(zhàn)術(shù)改航策略中。

3.2 改航算例分析

假設(shè)一架航班將預(yù)計(jì)17:40到達(dá)改航起始點(diǎn)，在實(shí)施該航后，預(yù)計(jì)17:58到改航結(jié)束點(diǎn)。利用網(wǎng)格法對(duì)環(huán)境建模，同時(shí)設(shè)定改航最短轉(zhuǎn)彎半徑不小于7.4 km，改航最大轉(zhuǎn)彎角度不大于，改航最大轉(zhuǎn)彎點(diǎn)個(gè)數(shù)不大于8個(gè)，航空器距離危險(xiǎn)天氣距離不小于10 km。

表1 歷史飛行受限區(qū)中心移動(dòng)位置Tab.1 Center location of history flow constrained area

表2 飛行受限區(qū)預(yù)測(cè)結(jié)果及評(píng)估結(jié)果Tab. 2 Forecast and assessment results of flow constrained area

參數(shù)設(shè)定如下：初始種群大小N=30，種群代數(shù)G=200，種群交叉概率pc=0.8，種群變異概率pm=0.1。目標(biāo)函數(shù)中，距離的權(quán)重ω1=0.8，轉(zhuǎn)彎點(diǎn)權(quán)重系數(shù)ω3=0.1，轉(zhuǎn)彎角權(quán)重系數(shù)ω4=0.1。

基于改航模型及算法求得的結(jié)果如圖7所示，其中多邊形區(qū)域?yàn)轱w行受限區(qū)，實(shí)線段代表原始航路，虛線段為模型規(guī)劃的改航路徑。

規(guī)劃結(jié)果表明，算法能夠在對(duì)受到危險(xiǎn)天氣影響的航線進(jìn)行約束處理后，自動(dòng)繞飛飛行受限區(qū)，找到相對(duì)代價(jià)最小的改航路徑。算法執(zhí)行過(guò)程中，適應(yīng)度值隨迭代次數(shù)變化如圖8所示，從中可以看出算法運(yùn)行90代后自動(dòng)終止，小于設(shè)定的最大進(jìn)化代數(shù)，能保證結(jié)果收斂。

圖7 改航路徑規(guī)劃結(jié)果Fig. 7 Route planning result

圖8 適應(yīng)度變化曲線Fig.8 Fit curve

對(duì)于求得的改航路徑，分別從改航距離，轉(zhuǎn)彎點(diǎn)個(gè)數(shù)以及轉(zhuǎn)彎角度進(jìn)行評(píng)估，評(píng)估結(jié)果如表3所示，其中改航起始點(diǎn)到改航結(jié)束點(diǎn)的原始路徑長(zhǎng)度為195 km，改航后的路徑長(zhǎng)度為212.6 km，增加了約9.2%。

由仿真結(jié)果表明，遺傳算法所得的改航路徑能實(shí)現(xiàn)改航路徑最短，轉(zhuǎn)彎點(diǎn)最少，轉(zhuǎn)彎角度最小的優(yōu)化目標(biāo)，并且規(guī)避了飛行受限區(qū)域。

表3 改航路徑評(píng)估結(jié)果Tab.3 Reroute assessment results

4 結(jié)論

本文首先對(duì)航班飛行受限區(qū)域的劃設(shè)與預(yù)測(cè)進(jìn)行研究，采用一元線性回歸預(yù)測(cè)模型和邊界預(yù)測(cè)算法對(duì)飛行受限區(qū)域進(jìn)行實(shí)時(shí)準(zhǔn)確的預(yù)測(cè)，然后將預(yù)測(cè)結(jié)果應(yīng)用于危險(xiǎn)天氣下的航空器改航，以預(yù)測(cè)的飛行受限區(qū)域作為改航避讓區(qū)域建立單個(gè)航班的改航模型，充分考慮航線結(jié)構(gòu)、航空器性能等其他限制因素，以最短改航距離、最小轉(zhuǎn)彎角、最少轉(zhuǎn)彎點(diǎn)為優(yōu)化目標(biāo)建立模型。通過(guò)遺傳算法對(duì)改航模型進(jìn)行求解，利用罰函數(shù)以及修復(fù)算子保證生成滿足約束條件的可行路徑。仿真結(jié)果表明：采用該方法可以在危險(xiǎn)天氣下實(shí)時(shí)精確地規(guī)劃出一條安全、經(jīng)濟(jì)、減輕管制員工作負(fù)荷的改航路徑。

參考文獻(xiàn)：

[1] DIXON M，WEINER G. Automated aircraft routing through weather impacted airspace [C]//IEEE International Conference on Robotics and Automation，Leuven，Belgium，1998：1725-1730.

[2] TAYLOR C，WANKE C. Dynamically generating operationally acceptable route alternatives using simulated annealing [J]. Air Traffic Control Quarterly，2012，20（1）：97.

[3]宋柯.空中交通流量管理改航策略初步研究[D].南京：南京航空航天大學(xué)，2002.

[4]徐肖豪，李成功，趙嶷飛，等.基于人工勢(shì)場(chǎng)算法的改航路徑規(guī)劃[J].交通運(yùn)輸工程報(bào)，2009，9（6）：64-68.

[5] MARTIN O. NICHOLES, CHEN NEE CHUAH，WU S. FELIX ,et al. Inter-domain collaborative routing（IDCR）：Server selection for optimal client performance[J]. Copmuter Communications，2011，34：1798-1809.

[6]孟令航，徐肖豪，李善梅，等.不確定強(qiáng)對(duì)流天氣下動(dòng)態(tài)改航路徑規(guī)劃[J].西南交通大學(xué)學(xué)報(bào)，2012，47（4）：686-691.

[7] BOKADIA S，VALASEK J. Severe weather avoidance using informed heuristic search[C]//AIAA Guidance，Navigation and Control Conference，Montreal，Canada，2001：11-19.

[8]董襄寧.飛行的組織與實(shí)施[R].南京航空航天大學(xué)：民航學(xué)院，2003.

[9]王興隆，徐肖豪，李慧.改航策略中雷暴飛行受限區(qū)劃設(shè)方法[J].科學(xué)技術(shù)與工程，2013，13（10）：2906-2910.

[10]李雄.飛行危險(xiǎn)天氣下的航班改航路徑規(guī)劃研究[D].南京：南京航空航天大學(xué)，2009.

[11]林歡.航空器動(dòng)態(tài)改航的自動(dòng)化處理技術(shù)比較[J].中國(guó)西部科技，2011，10（29）：34-35.

[12]陳冬華.旅行商問(wèn)題推廣及其混合智能算法[J].華東交通大學(xué)學(xué)報(bào)，2011，28（2）：102-106.

（責(zé)任編輯 姜紅貴）

Research of Flight Reroute Based on Flow Constrained Area

Jiang Xin1，2，Hu Minghua1，Zhang Ying1，Tian Wen1
（1.College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China；2 . The 709th Research Institute , China Shipbuilding Industry Corporation , Wuhan 430074，China )

Abstract：Dangerous weather affects flight safety and is an important reason for flight delay. By establishing flow constrained area under dangerous weather, using a linear regression forecast model and proposing an improved method, this study forecasted the location and boundary of flow constrained area dynamically. Adopting the predicted low constrained area as the constraints and taking flight performance and safety into account, it established a reroute model and applied the genetic algorithm by setting the shortest path of reroute, the least turning points and minimum average turning angle as the optimization goal. The simulation results showed that the designed route can avoid flight constrained area and achieve the goals of security, economy and reduce controllers’workload.

Key words：flow constrained area；location forecast；boundary forecast；genetic algorithm；reroute

中圖分類號(hào)：V355

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1005-0523（2016）03-0060-08

收稿日期：2015-11-19

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（71301074）

作者簡(jiǎn)介：蔣昕（1991—），女，碩士研究生，主要研究方向?yàn)榭罩薪煌髁抗芾怼?/p>

通訊作者：胡明華（1962—）,男，教授，博士生導(dǎo)師，主要研究方向?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理。