基于機(jī)器學(xué)習(xí)的進(jìn)離場(chǎng)航空器排序優(yōu)化研究

張洪楊，劉子彤，趙世豪，劉媛媛，馮曉康，張召悅

（中國(guó)民航大學(xué)，天津 300300）

終端區(qū)作為航班進(jìn)離場(chǎng)的主要區(qū)域，其空域結(jié)構(gòu)之復(fù)雜、航跡交織之密集是民航運(yùn)輸業(yè)發(fā)展的瓶頸所在。一般來(lái)說(shuō)，在民航空域不擴(kuò)張的情況下，擴(kuò)大機(jī)場(chǎng)容量的主要方法有新建航站樓，增加跑道數(shù)量或者對(duì)進(jìn)離場(chǎng)飛行程序進(jìn)行增加和優(yōu)化，重塑航班次序等，但這些方法需要大量時(shí)間和資金，多方進(jìn)行溝通協(xié)調(diào)，短期內(nèi)難以滿足需求。相比之下，通過(guò)調(diào)整航班進(jìn)離港次序的方式來(lái)提升機(jī)場(chǎng)容量顯得更加合理高效。

終端區(qū)航班排序技術(shù)一直以來(lái)受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。國(guó)內(nèi)外對(duì)航空器排序算法的研究有約束位置交換算法，滑動(dòng)時(shí)間窗算法和遺傳算法等。Chandrasekar等依據(jù)機(jī)場(chǎng)跑道的運(yùn)行模態(tài)、分布等提出了進(jìn)離港航空器協(xié)同調(diào)度，通過(guò)分支定界法進(jìn)行精確求解；Ahmed等提出了一種協(xié)同進(jìn)化遺傳算法，用于求解飛機(jī)航空器進(jìn)離場(chǎng)的跑道決策與飛機(jī)排序優(yōu)化的聯(lián)合問(wèn)題。在歐美發(fā)達(dá)國(guó)家開發(fā)了進(jìn)離港輔助決策系統(tǒng)，例如AMAN、DMAN系統(tǒng)及德國(guó)的COMPAS系統(tǒng)。國(guó)內(nèi)相較國(guó)外稍滯后，張啟錢等提出基于滾動(dòng)時(shí)域的遺傳算法模型；張軍峰等采用分支定界法對(duì)規(guī)定的時(shí)間窗內(nèi)航空器進(jìn)行優(yōu)化仿真排序。綜上，本文研究的主要內(nèi)容可以概括為以下幾點(diǎn)：介紹終端區(qū)的基本結(jié)構(gòu)、根據(jù)先到先服務(wù)算法在單跑道模型上計(jì)算飛機(jī)的總延誤時(shí)間、通過(guò)運(yùn)用遺傳算法實(shí)現(xiàn)單跑道模型優(yōu)化的求解及將仿真算法與優(yōu)化算法進(jìn)行比較分析。

1 模型建立

1.1 終端區(qū)

終端區(qū)流量管理的主要措施是流量排序，機(jī)場(chǎng)終端區(qū)航路網(wǎng)絡(luò)作為保障民航運(yùn)輸?shù)淖詈笠粋€(gè)組成部分，是保障空中交通高效運(yùn)行的空中“最后一公里”。

終端區(qū)的主要結(jié)構(gòu)包括進(jìn)離場(chǎng)點(diǎn)、起始進(jìn)近定位點(diǎn)、中間定位點(diǎn)、最后進(jìn)近定位點(diǎn)和對(duì)應(yīng)航道及機(jī)場(chǎng)跑道。航班穿越管制區(qū)移交點(diǎn)到達(dá)終端區(qū)時(shí)，要理順航路與進(jìn)近的關(guān)系，通過(guò)調(diào)整高度、速度及姿態(tài)對(duì)準(zhǔn)進(jìn)場(chǎng)點(diǎn)，當(dāng)航班量過(guò)大時(shí)需要在等待區(qū)域等待進(jìn)場(chǎng)，此時(shí)在進(jìn)場(chǎng)排序和計(jì)量區(qū)邊界的進(jìn)場(chǎng)點(diǎn)就會(huì)形成等待隊(duì)列，空中交通管制員也會(huì)在這個(gè)階段為航空器進(jìn)行進(jìn)場(chǎng)排序。進(jìn)場(chǎng)航班需匯集到同一航線上，然后依次消失高度和完成航跡的對(duì)正依次到達(dá)起始、中間進(jìn)近定位點(diǎn)。在到達(dá)最后進(jìn)近定位點(diǎn)之后，不再改變航班次序，按照例行程序降落在跑道上。通過(guò)對(duì)機(jī)場(chǎng)終端區(qū)進(jìn)行網(wǎng)絡(luò)建模，就可以知道終端區(qū)網(wǎng)絡(luò)中各航路、各飛行程序的運(yùn)行特性，有利于對(duì)機(jī)場(chǎng)終端區(qū)空域結(jié)構(gòu)進(jìn)行有效分析，做到充分高效地使用有限的終端區(qū)空域資源。

1.2 航空器進(jìn)場(chǎng)排序模型建立

針對(duì)規(guī)劃終端區(qū)飛機(jī)進(jìn)場(chǎng)順序，基于多架次航班單跑道降落，以總延誤時(shí)間最小為目標(biāo)函數(shù)，采用先到先服務(wù)算法，使用遺傳算法進(jìn)行求解。

假設(shè)變量：

n為劃設(shè)終端區(qū)范圍內(nèi)需要排序的飛機(jī)總數(shù)；

i為飛機(jī)序號(hào)；

j為緊隨i飛機(jī)之后的飛機(jī)序號(hào)；

ETAi為第i架飛機(jī)預(yù)計(jì)到達(dá)時(shí)間；

STAi為第i架飛機(jī)實(shí)際到達(dá)時(shí)間；

Tij為前架飛機(jī)i與后架飛機(jī)j必須保持的最小安全時(shí)間間隔；

Pi為第i架飛機(jī)；

D為總延誤時(shí)間；

tj為飛機(jī)j理想著陸時(shí)間；

H為重型飛機(jī)；

M為中型飛機(jī)；

L為輕型飛機(jī)；

A為超重型飛機(jī)。

根據(jù)國(guó)際民航組織的最新規(guī)定，各型號(hào)飛機(jī)之間的尾流距離間隔（單位：km）矩陣T如下。

根據(jù)以上假設(shè)變量，建立出如下模型：將飛機(jī)的ETA（預(yù)計(jì)到達(dá)時(shí)間）、機(jī)型、呼號(hào)及飛機(jī)各個(gè)機(jī)型的尾流間隔矩陣T依次輸入。假設(shè)在某一段時(shí)間，有n架飛機(jī)進(jìn)入規(guī)定的飛機(jī)排序區(qū)，對(duì)這n架飛機(jī)的序列進(jìn)行調(diào)整，使之在最短時(shí)間內(nèi)進(jìn)行降落。不考慮空中延誤時(shí)間，假設(shè)飛機(jī)一架一架連續(xù)著陸，并且不同類型的飛機(jī)按照規(guī)定的尾流間隔保持安全距離，若第一架飛機(jī)未延誤即STA1=ETA1，則第二架飛機(jī)的實(shí)際到達(dá)時(shí)間STA2=STA1+T12，則第二架飛機(jī)延誤時(shí)間為STA2-ETA2。

根據(jù)以上假設(shè)變量，建立出如下模型：將飛機(jī)的ETA（預(yù)計(jì)到達(dá)時(shí)間）、機(jī)型、呼號(hào)及飛機(jī)各個(gè)機(jī)型的尾流間隔矩陣T依次輸入。假設(shè)在某一段時(shí)間，有n架飛機(jī)進(jìn)入規(guī)定的飛機(jī)排序區(qū)，對(duì)這n架飛機(jī)的序列進(jìn)行調(diào)整，使之在最短時(shí)間內(nèi)進(jìn)行降落，且飛機(jī)i最早的降落時(shí)間為Ei，最遲降落時(shí)間為Ki。不考慮空中延誤時(shí)間，STA為實(shí)際到達(dá)時(shí)間，假設(shè)飛機(jī)連續(xù)著陸，并且不同類型的飛機(jī)按照規(guī)定的尾流間隔保持安全距離，建立數(shù)學(xué)模型如下。

公式（2）保證排序的合理性，即實(shí)際到達(dá)時(shí)間在可接受范圍內(nèi)；公式（4）表示飛機(jī)實(shí)際到達(dá)時(shí)間，同時(shí)也滿足尾流間隔要求；公式（5）（6）（7）代表飛機(jī)連續(xù)且存在，目標(biāo)函數(shù)（1）表示求解航空器連續(xù)進(jìn)離場(chǎng)的最小總延誤時(shí)間。

2 遺傳算法流程

遺傳算法于20世紀(jì)70年代被提出，該算法是基于生物學(xué)上的進(jìn)化、變異而提出的，其基本思想是模擬達(dá)爾文自然選擇和遺傳學(xué)機(jī)理中的生物進(jìn)化及變異過(guò)程。在需要進(jìn)行大量航班排序的情況下，傳統(tǒng)的遍歷算法耗時(shí)較長(zhǎng)，采用遺傳算法進(jìn)行復(fù)雜模型運(yùn)算的時(shí)候可以較快地取得較好的優(yōu)化結(jié)果。其流程大致如下。

（1）初始：設(shè)置遺傳代數(shù)基準(zhǔn)時(shí)間t=0，隨機(jī)生成M個(gè)個(gè)體作為初始種群P（0），并設(shè)置可接受最大遺傳代數(shù)為T。

（2）種族優(yōu)劣評(píng)價(jià)：計(jì)算種群P（t）中個(gè)體的適應(yīng)度。

（3）選擇：對(duì)群體做選擇函數(shù)變換，把競(jìng)爭(zhēng)優(yōu)勝的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代，以上操作基于群體中個(gè)體的種族優(yōu)劣評(píng)價(jià)。

（4）交叉：對(duì)群體做交叉函數(shù)變換。

（5）染色體變異：群體做變異算子運(yùn)算。即模擬生物界染色體交叉變異可能產(chǎn)生優(yōu)良后代，對(duì)個(gè)體的某些基因座上的數(shù)值變化。群體P（t）經(jīng)過(guò)選擇、交叉、染色體變異運(yùn)算之后得到下一代群體P（t+1）。

（6）終止輸出：當(dāng)t=T，仿真結(jié)束，輸出整個(gè)遺傳過(guò)程中的具有最大適應(yīng)度個(gè)體。

3 仿真實(shí)例分析

在本文中，采用遺傳算法與先到先服務(wù)的總延誤時(shí)間分別對(duì)飛機(jī)進(jìn)場(chǎng)與離場(chǎng)進(jìn)行對(duì)比。

3.1 單跑道飛機(jī)進(jìn)場(chǎng)排序

進(jìn)場(chǎng)排序運(yùn)用終端區(qū)空域，建立四維坐標(biāo)，根據(jù)航空器的相對(duì)位置和ETA（預(yù)計(jì)到達(dá)時(shí)間）精確時(shí)序間隔，優(yōu)化排序，從而降低總體延誤時(shí)間，減小終端區(qū)空域壓力，如圖1所示。

圖1 終端區(qū)示意圖

首先，對(duì)于單跑道飛機(jī)進(jìn)行建模排序，以某個(gè)機(jī)場(chǎng)上空終端區(qū)為例，根據(jù)不同機(jī)型飛機(jī)在終端區(qū)的平均飛行速度，對(duì)尾流間隔（單位：s）進(jìn)行時(shí)間維度的估算，得到矩陣如下。

仿真以15架飛機(jī)進(jìn)行排序，表1包括飛機(jī)類型及預(yù)計(jì)到達(dá)時(shí)間。

表1 進(jìn)場(chǎng)15架飛機(jī)名稱、類型及預(yù)計(jì)到達(dá)時(shí)間

由表1可知，假定第一架飛機(jī)正點(diǎn)到達(dá)，不考慮飛機(jī)在空中的延誤，取種群大小為200，交叉概率為0.8，變異概率為0.1，終止代數(shù)為150。得到新排序結(jié)果為：01/05/03/04/06/02/08/10/09/11/07/15/14/12/13；與采用先到先服務(wù)的排序結(jié)果進(jìn)行對(duì)比，得到表2。

表2 遺傳算法和先到先服務(wù)法排序結(jié)果對(duì)比

由表2可看出，遺傳算法排序的總延誤時(shí)間為20.7 min，平均延誤時(shí)間為1.32 min；先到先服務(wù)算法排序的總延誤時(shí)間為49.15 min，平均延誤時(shí)間為3.28 min。所以采用遺傳算法時(shí)，15架飛機(jī)隊(duì)列排序總延誤時(shí)間比先到先服務(wù)算法節(jié)省28.45 min，使用遺傳算法后除少數(shù)飛機(jī)延誤時(shí)間較長(zhǎng)，其余飛機(jī)著陸時(shí)間均優(yōu)于先到先服務(wù)排序著陸，提高運(yùn)行效率。

3.2 單跑道飛機(jī)離場(chǎng)排序

相較于進(jìn)場(chǎng)排序，離場(chǎng)排序是一個(gè)逆序推導(dǎo)過(guò)程。其目標(biāo)是根據(jù)尾隨間隔和停機(jī)位置等參數(shù)，縮小總體間隔、合理運(yùn)用跑道來(lái)優(yōu)化排序。航空器的離場(chǎng)不僅僅需要管制單位的排序，還需要與航空公司協(xié)調(diào)，更加繁雜。其主要工作流程如圖2所示。

圖2 離場(chǎng)排序工作流程

以15架航空器為例，隨機(jī)分配停機(jī)位置，假設(shè)跑道運(yùn)行情況良好，表3給出待起飛飛機(jī)編號(hào)預(yù)計(jì)起飛時(shí)間STD。表4給出了離場(chǎng)排序結(jié)果，離場(chǎng)排序延誤時(shí)間為21.8 min。

表3 離場(chǎng)15架飛機(jī)名稱、類型及預(yù)計(jì)到達(dá)時(shí)間

表4 離場(chǎng)排序結(jié)果

假設(shè)第一架飛機(jī)按時(shí)正常推出，不考慮地面等待延誤，取種群大小為200交叉概率為0.8，變異概率為0.1，終止代數(shù)為150。

總延誤時(shí)間為36.3 min，對(duì)應(yīng)排序?yàn)?3/01/02/11/08/15/04/12/09/10/03/05/14/07/06。

4 結(jié)束語(yǔ)

隨著中國(guó)民航事業(yè)的不斷發(fā)展，終端區(qū)容量已不能滿足日益增加的航班流量，對(duì)終端區(qū)流量進(jìn)行排序規(guī)劃，調(diào)整航班進(jìn)離港次序逐漸成為主流。本文通過(guò)運(yùn)用遺傳算法對(duì)航空器隊(duì)列次序進(jìn)行優(yōu)化設(shè)計(jì)，以航空器總延誤時(shí)間最小為目標(biāo)函數(shù)，將求解結(jié)果與先到先服務(wù)算法所求結(jié)果進(jìn)行對(duì)比。結(jié)果表明，通過(guò)遺傳算法優(yōu)化后的航空器次序優(yōu)于先到先服務(wù)航空器次序，可提高航空器運(yùn)行效率，從而更加有效地利用終端區(qū)空域，達(dá)到了經(jīng)濟(jì)、綠色和高效的管制效果。