離港飛機(jī)滑行路徑優(yōu)化與仿真

邢志偉 ，徐銘怡，羅 曉 ，羅 謙

（1.中國民航大學(xué)電子信息與自動(dòng)化學(xué)院，天津 300300；2.中國民航局第二研究所信息技術(shù)分公司，成都 100142）

隨著中國航空業(yè)的快速發(fā)展，航空流量密度迅速增大，又因機(jī)場地面資源、跑道、滑行道和停機(jī)位等條件限制，導(dǎo)致地面滑行過程中發(fā)生沖突的熱點(diǎn)區(qū)域增多，引起航班延誤與機(jī)場場面交通擁堵等現(xiàn)象，影響了航空運(yùn)輸業(yè)的正常發(fā)展。在空域資源短缺、機(jī)場擴(kuò)張受限、機(jī)場基礎(chǔ)設(shè)施有限等情況下，優(yōu)化可變滑行時(shí)間以充分利用現(xiàn)有資源成為解決航空流量密度大時(shí)機(jī)場場面交通擁堵及航班延誤等問題的首要選擇。相關(guān)研究中，李楠等[1]采用A*算法得到使總時(shí)間最短的滑行路徑以提高機(jī)場場面運(yùn)行效率。谷潤平等[2]使用改進(jìn)后的D*算法，動(dòng)態(tài)預(yù)測飛機(jī)的滑行路徑，緩解了機(jī)場場面交通擁堵現(xiàn)象。Lee等[3]提出以離港延遲的航班罰函數(shù)和以最短滑行時(shí)間為目標(biāo)去優(yōu)化滑行距離的MILP模型。Levy等[4]利用機(jī)場場面監(jiān)視數(shù)據(jù)得到各跑道、滑行道的利用率完成對(duì)飛機(jī)滑行時(shí)間的預(yù)測。鐘石泉等[5]提出核心路徑法，構(gòu)建具有能力限制與距離限制的數(shù)學(xué)規(guī)劃模型，實(shí)現(xiàn)了離場滑行目標(biāo)路徑規(guī)劃。仉俊峰等[6]利用圖論的方法解決了從起點(diǎn)到終點(diǎn)尋找最優(yōu)路徑的策略。綜上所述，國內(nèi)外在機(jī)場場面有限的條件下，對(duì)緩解機(jī)場場面交通壓力方面的研究取得了一定成果，但現(xiàn)有的離港飛機(jī)滑行路徑優(yōu)化算法未能充分考慮實(shí)際滑行問題中等待時(shí)間的情況，未能有效解決提出的問題。

針對(duì)機(jī)場條件限制、機(jī)場場面交通壓力大等關(guān)鍵問題：首先，研究智慧機(jī)場高效運(yùn)行的考察指標(biāo)；其次，通過優(yōu)化航空器滑行時(shí)間來提高整體協(xié)同決策，縮短多架飛機(jī)從停機(jī)位到跑道端口前之間的可變滑行時(shí)間，對(duì)飛機(jī)離港的滑行路徑進(jìn)行優(yōu)化[7]；最后，提出基于元胞自動(dòng)機(jī)的方法對(duì)機(jī)場場面拓?fù)浣＃⒗酶倪M(jìn)的蒙特卡洛算法對(duì)所建模型進(jìn)行求解[8]。

1 機(jī)場場面元胞自動(dòng)機(jī)模型建立

通過分析機(jī)場場面特性，根據(jù)元胞傳輸自動(dòng)機(jī)基本理論，利用有向網(wǎng)絡(luò)拓?fù)鋱D的結(jié)構(gòu)布局，依據(jù)民航場面滑行標(biāo)準(zhǔn)將機(jī)場場面分為以下3部分交通流運(yùn)輸模型。

1.1 一般滑行道元胞模型

飛機(jī)在停機(jī)位和跑道之間根據(jù)分配好的路徑進(jìn)行滑行，如圖1所示。在第t+1時(shí)刻元胞i的存量可表示為

其中：qi-1（t）為元胞i-1的流出流率；qi（t）為元胞i的流出流率；Ni（t）為元胞i的存量；dT為單位仿真時(shí)間步長。

圖1 一般滑行道元胞傳輸Fig.1 Cell transfer on general taxiing path

根據(jù)元胞特性可知，下游元胞可接受的流量和元胞的自身流量會(huì)約束上游元胞的流出量。上游元胞流出量qi-1（t）dT計(jì)算為

其中：li-1為元胞i-1長度；為元胞i-1的平均速度；Ci為元胞i容納飛機(jī)的最大數(shù)量，即

式中：pij是前機(jī)型為i、后機(jī)型為j的概率；Dij是前機(jī)型為i、后機(jī)型為j的安全間隔規(guī)定。

同理可計(jì)算qi（t）dT。

1.2 機(jī)坪元胞模型

將機(jī)坪元胞設(shè)定為離港飛機(jī)機(jī)坪元胞，由于在離港元胞與進(jìn)港一般滑行道元胞之間存在交點(diǎn)，會(huì)使機(jī)場場面更為復(fù)雜，如圖2所示。

圖2 機(jī)坪元胞傳輸Fig.2 Apron cell transfer

機(jī)坪離港元胞iD在時(shí)間片內(nèi)的最大流出量、第i+1個(gè)元胞的最大流出量及飛機(jī)推出量分別表示為

1.3 匯聚元胞傳輸模型

由于飛機(jī)推出后沿著滑行道滑行至跑道端頭時(shí)，離港交通流會(huì)在跑道和滑行道的交匯口產(chǎn)生匯聚，如圖3所示。

圖3 匯聚元胞傳輸Fig.3 Cross cell transfer

假設(shè)元胞i所能接收的流量為Ri（t）=Ci-Ni（t）；元胞i-1所能傳輸?shù)淖畲罅髁繛閘i-1；元胞i-2所能傳輸?shù)淖畲罅髁繛镾i-2，i（t）=Ni-2（t）×元胞i-1和元胞i-2的流量為

其中，βi-1（t）、βi-2（t）為第t時(shí)間步長內(nèi)上游元胞i-1和元胞i-2存量所占的比例，即

1.4 約束條件

1）跑道約束 每個(gè)離港航班必須分配且只能分配一條跑道，即

其中：φ=|R|為跑道數(shù)量；R為跑道集合；當(dāng)航班i進(jìn)港時(shí)分配到跑道r時(shí)，pir=1，否則pir=0。

2）停機(jī)位約束 每個(gè)離港航班必須分配且只能分配一個(gè)停機(jī)位，即

其中：m=|G|為可用停機(jī)位總量；G為可用停機(jī)位集合；當(dāng)把航班i分配到停機(jī)位k上時(shí)，yik=1，否則yik=0。

3）最小間隔約束 離港飛機(jī)在機(jī)場場面滑行過程中必須滿足一定的安全間隔。定義0-1決策變量對(duì)航空器進(jìn)行位置識(shí)別，即航班f在t時(shí)刻到達(dá)j節(jié)點(diǎn)，需使用的最小間隔約束定義為

其中：Af為進(jìn)港航班集合；Df為離港航班集合;依據(jù)管制原則，每架航班都有一個(gè)由一系列的節(jié)點(diǎn)pf構(gòu)成的優(yōu)選路徑集合Pf，從而pf∈Pf；設(shè)某起點(diǎn)j的滑行道的滑行鏈路長為L，最小間隔規(guī)定為D，Cj=「L/D」表示起點(diǎn)為j的鏈路容量。

4）超越限制約束 若前慢后快的2架航班連續(xù)進(jìn)入某一具有高容量值的滑行道，需滿足先進(jìn)先出的原則。在一條滑行道鏈路的實(shí)際運(yùn)行中不可能出現(xiàn)允許速度快的航班超越速度慢航班的情況。因此，所采用的方法是將超越限制約束轉(zhuǎn)化成容量限制約束，即將各鏈路的容量值設(shè)為1，有Cj（t）=1，這樣就使得2架航班不可能同時(shí)出現(xiàn)在一條鏈路中。對(duì)于容量大于1的滑行道鏈路，可人為添加節(jié)點(diǎn)，也可滿足每條鏈路的容量不大于1，又可提高運(yùn)行效率[9]。

2 蒙特卡洛算法優(yōu)化求解

2.1 隨機(jī)數(shù)的生成

蒙特卡洛算法是一類基于概率論處理方法，可用來對(duì)非線性和離散系統(tǒng)進(jìn)行后驗(yàn)概率分布的估計(jì)，具體可描述為：通過一組依據(jù)重要性采樣得到的帶有權(quán)值的樣本集合來估計(jì)研究對(duì)象的未來概率分布，樣本會(huì)進(jìn)行周期性的數(shù)據(jù)更新[10]。在預(yù)測階段，首先對(duì)已知的機(jī)場數(shù)據(jù)進(jìn)行初始化，根據(jù)機(jī)場交通流運(yùn)輸模型對(duì)機(jī)場交通進(jìn)行算法預(yù)測；在濾波更新階段，濾除不符合機(jī)場模型的樣本數(shù)據(jù)，然后對(duì)數(shù)據(jù)進(jìn)行二次篩選，篩除不滿足機(jī)場模型約束條件的數(shù)據(jù)，獲取機(jī)場元胞模型的數(shù)據(jù)；最后對(duì)機(jī)場進(jìn)離港流量分析。仿真流程如圖4所示。

圖4 仿真流程Fig.4 Simulation procedure

在對(duì)已知分布進(jìn)行采樣的過程中，隨機(jī)數(shù)被看作已知量[11]。乘同余法是一種典型的計(jì)算機(jī)偽隨機(jī)數(shù)生成方法。其實(shí)現(xiàn)形式是：對(duì)于任一初始值xi，以下可得到偽隨機(jī)數(shù)序列 ξi，即

其中：x0為隨機(jī)種子，即初始值；a為乘子；M為模數(shù)。

2.2 蒙特卡洛優(yōu)化求解的實(shí)現(xiàn)

首先將連續(xù)時(shí)間分割為離散的時(shí)間單元t，ot表示接收到的元胞觀測信息，lt表示在t時(shí)刻的位置狀態(tài)情況；用以表示前一個(gè)t-1時(shí)刻的位置情況來預(yù)測當(dāng)前t時(shí)刻位置情況的方程p（lt|lt-1），稱為狀態(tài)轉(zhuǎn)移方程；用以表示位置信息位于lt的概率方程p（lt|ot），稱為觀測方程[12]。

第一階段 預(yù)測階段。飛機(jī)滑行的元胞自動(dòng)機(jī)模型最大速度Vmax已知，假設(shè)lt-1為t-1時(shí)刻的樣本，則t時(shí)刻的位置信息lt是以前一時(shí)刻的位置信息lt-1為起點(diǎn)，以飛機(jī)滑行允許的最大滑行速度Vmax所處的位置點(diǎn)為終點(diǎn)的線段上任意一點(diǎn)。d（lt，lt-1）表示兩點(diǎn)之間的實(shí)際距離。假設(shè)滑行過程服從均勻分布[0，Vmax]，由此狀態(tài)轉(zhuǎn)移方程為

第二階段 過濾與更新階段。因?yàn)樵詣?dòng)機(jī)模型的設(shè)定，飛機(jī)的滑行只能以元胞為單位進(jìn)行位置更新，可更新的位置信息用S來表示，每個(gè)位置的可運(yùn)動(dòng)長度為 r，可得到當(dāng)滿足條件 d（lt，s）≤r時(shí)保留，否則被過濾掉[13]，其中 s∈S。

第三階段 序列重要性采樣階段。重要性采樣的核心是找到一個(gè)概率分布已知、容易采樣且與樣本有相似概率分布的重要性函數(shù)q[14]。在蒙特卡洛算法中，重要性函數(shù)q設(shè)定為狀態(tài)轉(zhuǎn)移方程p（lt|lt-1），則預(yù)測下一時(shí)刻t的位置信息為

對(duì)以上權(quán)值進(jìn)行標(biāo)準(zhǔn)化處理后可得到

其中，在蒙特卡洛算法的定位過程中，N通常設(shè)定為采樣的最大值Nthreshold。

3 滑行路徑模型仿真與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)來源與分析

用于實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)浜蛿?shù)據(jù)來源于國內(nèi)某大型樞紐機(jī)場的布局結(jié)構(gòu)和實(shí)際運(yùn)行數(shù)據(jù)，局部網(wǎng)絡(luò)拓?fù)鋱D如圖5所示。

圖5 國內(nèi)某大型樞紐機(jī)場局部網(wǎng)絡(luò)拓?fù)銯ig.5 Partial network topology of one domestic hub airport

用于實(shí)驗(yàn)分析的數(shù)據(jù)選取該機(jī)場在2017年1～3月的生產(chǎn)數(shù)據(jù)，統(tǒng)計(jì)計(jì)算后可知平均每架飛機(jī)所用的平均滑行時(shí)間約為21.39 min。選取這3個(gè)月實(shí)際運(yùn)行數(shù)據(jù)中的某一天從各停機(jī)位推出的航班總架次為762架。為便于分析研究，規(guī)定以每15 min的時(shí)間間隔為一個(gè)時(shí)隙，在07：00至22：00這15 h的繁忙時(shí)段內(nèi)，離港航班平均11.75架/15 min；當(dāng)日的空閑時(shí)段內(nèi)，離港航班平均0.42架/15 min。

3.2 仿真結(jié)果對(duì)比

各停機(jī)位在每一個(gè)時(shí)隙都會(huì)相繼推出新的航班，進(jìn)入滑行道系統(tǒng)的離港航班會(huì)逐漸增加，離港需求也會(huì)產(chǎn)生積累，造成航班之間的滑行沖突。為避免滑行沖突的產(chǎn)生，同時(shí)也為了驗(yàn)證模型的有效性，利用蒙特卡洛算法在對(duì)模型進(jìn)行計(jì)算時(shí)需滿足最小間隔約束條件，此條件的成立可通過蒙特卡洛優(yōu)化算法中狀態(tài)方程進(jìn)行監(jiān)控。

從停機(jī)位推出的航班將會(huì)從1、2、3這3個(gè)滑行道節(jié)點(diǎn)進(jìn)入滑行道系統(tǒng)，分別對(duì)從這3個(gè)節(jié)點(diǎn)進(jìn)入滑行道的航班進(jìn)行分析仿真。依據(jù)管制中心為航班分配的滑行路徑與運(yùn)用建模仿真后的滑行路徑為離港航班重新生成滑行道滑行時(shí)間，通過比較仿真結(jié)果與實(shí)際運(yùn)行數(shù)據(jù)后得到3個(gè)節(jié)點(diǎn)的滑行時(shí)間對(duì)比，如圖6、圖7和圖8所示。

圖6 從1號(hào)節(jié)點(diǎn)進(jìn)入滑行道的航班滑行時(shí)間Fig.6 Taxiing time of flights from Node 1

圖7 從2號(hào)節(jié)點(diǎn)進(jìn)入滑行道的航班滑行時(shí)間Fig.7 Taxiing time of flights from Node 2

圖8 從3號(hào)節(jié)點(diǎn)進(jìn)入滑行道的航班滑行時(shí)間Fig.8 Taxiing time of flights from Node 3

運(yùn)用元胞自動(dòng)機(jī)分模塊建模后使用蒙特卡洛算法優(yōu)化求解，離港飛機(jī)的平均滑行時(shí)間從21.39 min降低至19.27 min，滑行效率平均提升了9.9%，總的滑行時(shí)間降低至407.04 min。除個(gè)別航班的滑行路徑優(yōu)化效果不明顯外，整體航班滑行時(shí)間在優(yōu)化滑行路徑后，地面滑行時(shí)間有所減少，對(duì)于滑行時(shí)間高于均值的航班優(yōu)化效果更為顯著，有效地避免了地面滑行道的擁堵，可為離港航班選擇盡量最優(yōu)的滑行路徑，使其盡快到達(dá)跑道端頭等待起飛。

4 結(jié)語

首先，針對(duì)飛機(jī)在地面滑行過程中產(chǎn)生沖突的熱點(diǎn)區(qū)域逐漸增多、造成航班延誤與機(jī)場場面交通擁堵加劇的問題，提出了對(duì)飛機(jī)離場路徑進(jìn)行優(yōu)化的必要性；其次，針對(duì)國內(nèi)某大型機(jī)場，根據(jù)機(jī)場場面特性利用元胞傳輸自動(dòng)機(jī)原理建立機(jī)場場面離場交通流數(shù)學(xué)模型；最后，通過對(duì)蒙特卡洛算法的優(yōu)化，對(duì)建立的機(jī)場場面交通流模型進(jìn)行求解，利用實(shí)際機(jī)場運(yùn)行數(shù)據(jù)對(duì)模型進(jìn)行仿真驗(yàn)證。對(duì)滑行路徑重新優(yōu)化后，能減少可變滑行時(shí)間，相比于機(jī)場現(xiàn)行的滑行路徑方式，其在每個(gè)時(shí)隙內(nèi)的滑行流暢度、平均離港滑行時(shí)間和機(jī)場通行量等各方面都體現(xiàn)出極大的優(yōu)越性。從而緩解了高峰時(shí)段內(nèi)機(jī)場的交通擁堵，平衡滑行道負(fù)載，高效利用滑行道系統(tǒng)，均衡機(jī)場場面交通流，進(jìn)而減少航班延誤，達(dá)到為機(jī)場運(yùn)行提升工作效率、節(jié)約經(jīng)濟(jì)成本、減少環(huán)境污染和提高旅客滿意度的目的。