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

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

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

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

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

1 模型建立

1.1 終端區(qū)

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

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

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

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

假設(shè)變量：

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

i為飛機序號；

j為緊隨i飛機之后的飛機序號；

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

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

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

Pi為第i架飛機；

D為總延誤時間；

tj為飛機j理想著陸時間；

H為重型飛機；

M為中型飛機；

L為輕型飛機；

A為超重型飛機。

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

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

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

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

2 遺傳算法流程

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

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

（2）種族優(yōu)劣評價：計算種群P（t）中個體的適應(yīng)度。

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

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

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

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

3 仿真實例分析

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

3.1 單跑道飛機進(jìn)場排序

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

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

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

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

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

由表1可知，假定第一架飛機正點到達(dá)，不考慮飛機在空中的延誤，取種群大小為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)行對比，得到表2。

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

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

3.2 單跑道飛機離場排序

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

圖2 離場排序工作流程

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

表3 離場15架飛機名稱、類型及預(yù)計到達(dá)時間

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

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

總延誤時間為36.3 min，對應(yīng)排序為13/01/02/11/08/15/04/12/09/10/03/05/14/07/06。

4 結(jié)束語

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