基于滾動(dòng)模糊時(shí)間窗的場面動(dòng)態(tài)路徑規(guī)劃

謝春生，盧菲菲，楊群亭

(中國民航大學(xué)空中交通管理學(xué)院，天津 300300)

隨著民航業(yè)的蓬勃發(fā)展，機(jī)場航班量不斷增加，機(jī)場場面擁堵問題日益突顯，成為制約機(jī)場運(yùn)行效率與安全水平的關(guān)鍵因素。因此合理規(guī)劃機(jī)場場面滑行路徑，對于機(jī)場發(fā)展具有重大意義。

關(guān)于機(jī)場地面滑行問題，迄今已有多位學(xué)者展開相關(guān)研究。傳統(tǒng)算法方面，谷潤平等[1]使用改進(jìn)的 D* 算法研究場面動(dòng)態(tài)滑行問題；李睿馨[2]運(yùn)用Dijkstra算法構(gòu)建多因素約束的滑行路徑模型優(yōu)化機(jī)場場面滑行路徑；劉帆等[3]建立機(jī)場路網(wǎng)有向圖，并使用 A*算法進(jìn)行場面滑行動(dòng)態(tài)規(guī)劃求解。智能算法方面；姜雨等[4]構(gòu)建場面航空器滑行時(shí)空協(xié)同優(yōu)化模型，基于遺傳算法研究滑行成本與滑行沖突對場面航空器滑行路徑的影響；馮程等[5]設(shè)計(jì)了基于禁忌搜索算法的優(yōu)化模型，研究滑行路徑規(guī)劃與停機(jī)位分配聯(lián)合問題的解決方法。建模方面，Xiao等[6]提出面向彩色滑行道Petri網(wǎng)模型以解決基于先進(jìn)場面活動(dòng)引導(dǎo)和控制系統(tǒng)(advanced surface movement guidance and control system，A-SMGCS)的飛機(jī)無沖突滑行路線規(guī)劃問題；趙天宇等[7]提出沖突解脫策略并基于航空器油耗最小的無沖突路徑規(guī)劃算法對場面滑行問題求解；沈建凱等[8]基于 Q 學(xué)習(xí)對管制員管制行為建模，檢測沖突集合并預(yù)估沖突，提前預(yù)判分配路線避讓沖突得到最優(yōu)滑行路徑。以上研究從成本、沖突等方面研究滑行路徑規(guī)劃問題，卻未探究機(jī)場運(yùn)行中滑行時(shí)間不確定對路徑規(guī)劃造成的影響，而解決滑行時(shí)間不確定問題對路徑規(guī)劃和提高機(jī)場的運(yùn)行效率均具有重要意義。

在基于模糊規(guī)則系統(tǒng)的基礎(chǔ)上，現(xiàn)構(gòu)建機(jī)場滑行時(shí)間預(yù)測模型，將滾動(dòng)時(shí)間窗和模糊時(shí)間窗算法相結(jié)合，對滑行路徑進(jìn)行動(dòng)態(tài)優(yōu)化，以期降低機(jī)場地面滑行沖突，提高機(jī)場運(yùn)行效率與安全水平。

1 基于 Mamdani 模糊規(guī)則系統(tǒng)的滾動(dòng)模糊時(shí)間窗口算法

1.1 Mamdani模糊規(guī)則系統(tǒng)

(1)

本節(jié)聚焦機(jī)場地面滑行路線優(yōu)化問題，基于此系統(tǒng)相關(guān)數(shù)據(jù)輸入和輸出的模糊集，以語言變量解釋基礎(chǔ)系統(tǒng)的形式模擬預(yù)測機(jī)場不同運(yùn)行場景中的滑行時(shí)間。將這些解釋變量輸入與之相關(guān)的隸屬度函數(shù)，模糊化后導(dǎo)入推理單元；在推理單元中賦予推理規(guī)則并設(shè)置聚合方法將輸入映射至輸出模糊集中；基于去模糊化運(yùn)算方法獲得量化數(shù)值，進(jìn)而描述機(jī)場不同運(yùn)行場景中滑行時(shí)間的狀態(tài)。Mamdani-FBRS預(yù)測滑行時(shí)間的輸入主要包括以下5個(gè)解釋變量：總滑行距離、總轉(zhuǎn)彎角度、進(jìn)離場類型(二進(jìn)制值0/1)、機(jī)場交通量和跑道的運(yùn)行模式[9]。

總滑行距離DS：指在停機(jī)位和跑道之間航空器滑行的距離。

總轉(zhuǎn)彎角度AS：以最短路徑上相鄰弧線之間的總角偏差計(jì)算。滑行速度是由航空器必須實(shí)現(xiàn)的總轉(zhuǎn)彎量所限制的，總轉(zhuǎn)彎量越大，滑行速度越慢。

進(jìn)離場類型(二進(jìn)制值0/1)：進(jìn)場航空器為0，離場航空器為1。

機(jī)場的交通量N/Q：分為兩大類：在某個(gè)時(shí)間段場面上正在移動(dòng)的航空器數(shù)量N和停止移動(dòng)的航空器數(shù)量為Q。其中，NA為場面上滑行的移動(dòng)航空器中進(jìn)場航空器的數(shù)量；ND為場面上滑行的移動(dòng)航空器中離場航空器的數(shù)量；QA為場面上停止航空器中進(jìn)場航空器的數(shù)量；QD為場面上停止航空器中離場航空器的數(shù)量。

跑道的運(yùn)行模式：包括隔離運(yùn)行和獨(dú)立運(yùn)行。

輸出變量包括總滑行時(shí)間TS、等待時(shí)間TH和沖突次數(shù)NB。

基于Mamdani-FBRS[9]系統(tǒng)構(gòu)建機(jī)場場面滑行模型，利用數(shù)據(jù)驅(qū)動(dòng)提供航空器的滑行時(shí)間估值，先從包含航空器運(yùn)動(dòng)的歷史數(shù)據(jù)集中識(shí)別并獲取隸屬函數(shù)參數(shù)的初始值，結(jié)合K-means算法與遺傳算法[10]，后通過誤差反向傳播算法[11]加以調(diào)整，以達(dá)到提高M(jìn)amdani-FBRS的估算精度，從而形成自適應(yīng)的Mamdani-FBRS，以達(dá)到更好預(yù)測模糊滑行時(shí)間的目的。對于機(jī)場場面滑行中的不確定性，通過航空器穿越機(jī)場布局圖上某條滑行道的模糊時(shí)間，借助不同的λ量化機(jī)場滑行中的不確定性，且通過文中定義能近似表示模糊集Bi的隸屬函數(shù)，進(jìn)一步量化不確定性，達(dá)到更好的動(dòng)態(tài)優(yōu)化滑行路線的目的。

1.2 滾動(dòng)模糊時(shí)間窗算法

滾動(dòng)模糊時(shí)間窗算法首先對航空器次序采用滾動(dòng)窗口進(jìn)行預(yù)處理，基于Ravizza等[12]的算法基礎(chǔ)，給定航空器ai的滑行請求Qi=(Vstart,Vend,τrw)，其中，τrw為機(jī)場分配給該航空進(jìn)入跑道的時(shí)刻。在G上找到從頂點(diǎn)Vstart到終點(diǎn)Vend的無沖突路線Ri，且滿足時(shí)間窗口最小滑行時(shí)間T的要求。算法找到通往終點(diǎn)節(jié)點(diǎn)的路線Ri就會(huì)終止，并將Ri分配給航空器ai。算法中用到的變量參數(shù)如表1所示。

表1 變量匯總

在運(yùn)行中，機(jī)場基本按照先到先服務(wù)的原則(first come first service，F(xiàn)CFS)為飛機(jī)排序。為有效利用機(jī)場場面滑行資源，本節(jié)采用滾動(dòng)窗口為航空器分配相應(yīng)的滑行次序，在一定程度上減少航空器等待、延誤時(shí)間及停止次數(shù)，以提高機(jī)場的運(yùn)行效率。

滾動(dòng)窗口考慮w架航空器等待，獨(dú)立于所使用的最短路徑算法，對航空器的排列進(jìn)行單獨(dú)搜索，并根據(jù)不同的潛在順序?yàn)楹娇掌鞣峙浠新肪€[13]。檢查窗口內(nèi)w個(gè)航空器的排列組合，所有排列組合里的航空器1～w都將被考慮且分配路線。按照每個(gè)組合所規(guī)定的順序，從中選擇最快的航空器滑行路線組合，并使其固定。之后窗口滾動(dòng)到航空器w+1～2w，在此范圍內(nèi)，考慮航空器的所有排列組合，同時(shí)考慮先前航空器的路線。依次進(jìn)行，窗口每次向前滾動(dòng)w架航空器，并將路線分配給航空器，然后將其固定，同時(shí)使后續(xù)航空器避開先前航空器。假定航空器分配的使用跑道時(shí)間是固定的。在滾動(dòng)窗口的基礎(chǔ)上，再采用模糊時(shí)間窗算法對航空器的路線進(jìn)行動(dòng)態(tài)調(diào)整，找到航空器從起始點(diǎn)到終點(diǎn)的更優(yōu)化路徑。模糊時(shí)間算法步驟如下。

(1)設(shè)置H,ψ(v)=?；?v∈V創(chuàng)建一個(gè)新標(biāo)簽L=(Vstart,τrw,nil)。

(2)將帶有τrw的標(biāo)簽L分別存儲(chǔ)在H和集合ψ(vstart)中。

(4)如果VL=Vend，從L開始向前搜索重構(gòu)Vstart到Vend的路線并存儲(chǔ)在R，算法結(jié)束。

(8)對于R的起始第一條滑行道eL，設(shè)置πin=?，初始化起始時(shí)間，πin←τstart。

1.3 離場航空器滑行路線

針對離場航空器的滑行路線，滾動(dòng)模糊時(shí)間窗算法在開始執(zhí)行搜索離場航空器的滑行路線時(shí)，與進(jìn)場航空器不同，它是從停機(jī)位開始往前搜索路徑，通過跑道時(shí)間τrw和滑行時(shí)間來確定航空器的機(jī)位推出時(shí)間。本節(jié)假定跑道時(shí)間τrw為開始時(shí)間τstart(航空器從停機(jī)位開始滑行的時(shí)刻)減去航空器估計(jì)的滑行時(shí)間，滑行時(shí)間是從機(jī)位到跑道的最短路徑的時(shí)間(使用經(jīng)典的Dijkstra算法計(jì)算)。而針對用于分配路線的航空器推出時(shí)間τout，只考慮模糊集的模態(tài)值(即最大值)，故基于二分法迭代來確定航空器的最晚推出時(shí)間，旨在找到一條可行的路線Ri，其中航空器的推出時(shí)間在航空器分配的跑道時(shí)間之前，使航空器停在機(jī)位上的時(shí)間較長，以達(dá)到節(jié)約燃油和滑行進(jìn)程中等待時(shí)間。

使用滾動(dòng)模糊時(shí)間窗算法搜索滑行路線的進(jìn)程中，若算法未能搜索到滑行路線，則直接將τstart減去10 min作為推出時(shí)間。如果能搜索到滑行路徑且τout比τrw晚時(shí)，若搜索不到最佳路徑Rbest，則將τstart提前τrw-τout差值tinc作為推出時(shí)間；若能找到最佳路徑Rbest，則只需給τstart提前τrw-τout差值tinc的1/2作為推出時(shí)間。若能找到最佳路徑Rbest且τout比τrw早，那么τstart就推后τout-τrw差值tinc的1/2作為推出時(shí)間。重復(fù)上述搜索滑行路徑的進(jìn)程，直至τout≡τrw或者達(dá)到規(guī)定的循環(huán)次數(shù)，最后找到Rbest或者沒有滑行路徑Ri。具體流程圖如圖1所示。

圖1 離場路徑搜索流程

2 機(jī)場運(yùn)行模型設(shè)計(jì)

機(jī)場布局用有向圖G=(V,E)表示，滑行道E代表滑行道，頂點(diǎn)V代表停機(jī)位、交叉點(diǎn)和中間點(diǎn)。一條滑行道e∈E有一組權(quán)值Te，表示穿越滑行道e的時(shí)間。對于某一架特定航空器的滑行時(shí)間teL∈Te取決于先前滑行的滑行道、機(jī)場運(yùn)行模式和航空器進(jìn)離港類型。

滾動(dòng)模糊時(shí)間窗算法的流程如圖2所示。

圖2 滾動(dòng)模糊時(shí)間窗算法的流程圖

算法中關(guān)于每條滑行道的使用時(shí)間為任意一個(gè)時(shí)間段內(nèi)每條滑行道只允許一架航空器通過，且將由每條滑行道與之相關(guān)聯(lián)的時(shí)間窗口來實(shí)現(xiàn)；此時(shí)間窗可以指定滑行道e作為路線一部分時(shí)的使用時(shí)間。一架航空器只會(huì)分配一條路線，這條路線包含一系列的時(shí)間窗，以確保航空器沿其滑行沒有沖突。此外，為避免沖突，航空器間的最小間隔設(shè)置為60 m，以滿足同一滑行道上連續(xù)航空器的分離。為確保滑行航空器的安全，在G上進(jìn)行路線規(guī)劃之前，找到每條滑行道e的沖突滑行道集Conf(e)，這些滑行道都是與e共用一個(gè)頂點(diǎn)或者在滑行道e60 m的范圍內(nèi)通過。當(dāng)一架航空器在滑行道e上時(shí)，滑行道e的沖突滑行道集Conf(e)的時(shí)間窗就會(huì)更新，以防止其他航空器與之沖突。

3 算法應(yīng)用實(shí)例

根據(jù)某機(jī)場飛行計(jì)劃，隨機(jī)選擇航班，通過復(fù)制航班軌跡，獲得不同流量水平的滑行數(shù)據(jù)。復(fù)制的航班雖使用原來的跑道，但進(jìn)入跑道時(shí)間存在2 min的偏移。此外，通過這種方式，分別創(chuàng)建了95%、100%、110%、115%、120%和125%倍于原始飛機(jī)(725架)架次的集合，從而得到了從低密度交通流(低密度95%)，到實(shí)際運(yùn)營交通流(中密度100%)，再到高密度的交通流(高密度125%)的運(yùn)行場景。

在不同交通流密度下，分別采用BREEON’S法[14]和滾動(dòng)模糊時(shí)間窗算法進(jìn)行路徑規(guī)劃，以研究不同機(jī)位的滑行時(shí)間及平均滑行時(shí)間變化。并基于不確定度為1，統(tǒng)計(jì)分析在低、中和高3種交通流密度下的航空器滑行沖突次數(shù)和等待時(shí)間結(jié)果。

3.1 滑行時(shí)間

在這3種交通流場景中，通過設(shè)置不同的不確定度，即不確定度分別為0.2、0.4、0.6和0.8，分別采用BREEON’S法和滾動(dòng)模糊窗口法進(jìn)行路徑規(guī)劃，進(jìn)而比較每個(gè)機(jī)位的進(jìn)港滑行時(shí)間、離港滑行時(shí)間和總滑行時(shí)間，以及三者的變化情況與趨勢。

圖3～圖5為低密度95%、中密度100%和高密度125%的實(shí)驗(yàn)場景下，基于不同不確定度分別采用BREEON’S法和滾動(dòng)模糊窗口法時(shí)，各機(jī)位的平均滑行時(shí)間結(jié)果。其中，BREEON’SA表示BREEON’S法進(jìn)港；RFTWA表示滾動(dòng)模糊窗法進(jìn)港；BREEON’SD表示BREEON’S法離港；RFTWD表示滾動(dòng)模糊窗法離港；BREEON’S表示BREEON’S法進(jìn)離港；RFTW表示滾動(dòng)模糊窗法進(jìn)離港。由圖3～圖5可知，航空器流量的增加導(dǎo)致各機(jī)位進(jìn)港滑行時(shí)間、離港滑行時(shí)間和總滑行時(shí)間增加。其中，在相同的不確定度下，基于BREEON’S法各機(jī)位的進(jìn)港滑行時(shí)間、離港滑行時(shí)間和總滑行時(shí)間均高于滾動(dòng)模糊窗口法，平均高出2～3 min；在不同的不確定度下，滑行時(shí)間結(jié)果的變化趨勢一致，結(jié)果證明滾動(dòng)模糊窗口法對路徑優(yōu)化的有效性。

圖3 低密度95%不同機(jī)位滑行時(shí)間圖

圖4 中密度100%不同機(jī)位滑行時(shí)間圖

圖5 高密度125%不同機(jī)位滑行時(shí)間圖

此外，在這3種交通流場景中分別采用BREEON’S法和滾動(dòng)模糊窗口法進(jìn)行路徑優(yōu)化時(shí)，對比分析基于0.2、0.4、0.6和0.8的不確定度中不同機(jī)位的平均滑行時(shí)間，結(jié)果如圖6所示。

圖6 3種密度交通流下不同機(jī)位平均滑行時(shí)間圖

在低密度場景使用BREEON’S方法時(shí)，不同機(jī)位平均滑行時(shí)間的中位數(shù)隨著不確定度的增大而繼續(xù)增加。當(dāng)不確定度為0.2時(shí)不同機(jī)位平均滑行時(shí)間中位數(shù)為4.5 min，不確定度為0.4時(shí)為5.1 min，不確定度為0.6時(shí)為7.2 min，不確定度為0.8時(shí)為7.5 min；且不同機(jī)位平均滑行時(shí)間的變化區(qū)間范圍較大，平均滑行時(shí)間最大值與最小值之間的時(shí)間跨度較廣。基于滾動(dòng)模糊時(shí)間窗法時(shí)，不確定度的增加導(dǎo)致不同機(jī)位平均滑行時(shí)間的中位數(shù)亦增加；此外，不同不確定度下的中位數(shù)略高于BREEON’S法，但不同機(jī)位平均滑行時(shí)間的變化區(qū)間范圍小于BREEON’S法，而且平均滑行時(shí)間的最大值和最小值之間的時(shí)間跨度也小于它。原因是低密度流量下，場面航空器的滑行順暢，故兩種方法的滑行時(shí)間結(jié)果相差甚微。

隨著航空器流量的增加，不同機(jī)位的平均滑行時(shí)間相應(yīng)增加。滾動(dòng)模糊時(shí)間窗法通過提前排序，減少了航空器在場內(nèi)滑行過程中停車的等待時(shí)間，進(jìn)而可以相對減少平均滑行時(shí)間。通過圖6(b)和圖6(c)可知，滾動(dòng)模糊時(shí)間窗法隨航空器流量增長而平均路徑優(yōu)化效果提升。

3.2 滑行沖突

針對場面航空器滑行的擁堵問題，基于不確定度為1且在低、中和高3種交通流場景下，研究使用BROWNLEE’S法和滾動(dòng)模糊時(shí)間窗口法優(yōu)化航空器擁堵時(shí)的路徑，以及統(tǒng)計(jì)分析滑行中所發(fā)生的沖突次數(shù)和滑行中的等待時(shí)間。具體數(shù)據(jù)結(jié)果如表2所示。

依據(jù)表2中的數(shù)據(jù)進(jìn)行分析可知，沖突次數(shù)和等待時(shí)間隨航空器流量密度的增加而增加。當(dāng)采用BREEON’S法時(shí)，在航空器沖突次數(shù)方面，中密度比低密度增加187次，高密度比中密度增加189次；在航空器等待時(shí)間方面，中密度比低密度增長1.27倍，高密度比中密度增長1.25倍。采用滾動(dòng)模糊窗口法時(shí)，在航空器沖突次數(shù)方面，中密度比低密度增加138次，高密度比中密度增加139次；在航空器等待時(shí)間方面，中密度比低密度增長1.18倍，高密度比中密度增長1.23倍。數(shù)據(jù)分析表明，采用滾動(dòng)模糊窗口法進(jìn)行路徑優(yōu)化，一定程度上減少了航空器滑行中的沖突次數(shù)和等待時(shí)間，從而提高了全場航空器滑行的效率。

表2 航空器滑行的沖突次數(shù)和等待時(shí)間

為更深入研究滾動(dòng)模糊時(shí)間窗法在繁忙場景中的應(yīng)用效果，用725架航空器為基數(shù)以依次增加0.5倍的航空器數(shù)量的方式，形成以762、798、834、870和907架航空器為基數(shù)的5種運(yùn)行場景方案。基于滾動(dòng)模糊時(shí)間窗算法進(jìn)行路徑優(yōu)化，且分析此5種方案在不同不確定度下，航空器的日高峰小時(shí)架次、全天平均延誤時(shí)間和高峰小時(shí)延誤時(shí)間數(shù)據(jù)結(jié)果。數(shù)據(jù)結(jié)果如表3所示。

表3 基于滾動(dòng)模糊時(shí)間窗算法的繁忙場景滑行數(shù)據(jù)

在不確定度相同的情況下，隨著航空器密度的增加，航空器的平均全天延誤和日高峰小時(shí)延誤逐漸增加。但增長趨勢緩慢，大部分平均全天延誤增長不超過1.3倍。大部分日高峰小時(shí)延誤增長不超過1.1倍。航空器的日高峰小時(shí)架次無明顯變化。

隨著不確定度的增加，同數(shù)量航空器架次場景下，航空器的平均全天延誤和日高峰小時(shí)延誤也隨著不確定度的增加而增加。數(shù)據(jù)結(jié)果表明，隨著場內(nèi)航空器數(shù)量的增加和不確定度的增大，場內(nèi)航空器滑行延誤會(huì)有一定程度的增加，但增加幅度較小。證明采用滾動(dòng)模糊時(shí)間窗法進(jìn)行路徑優(yōu)化時(shí)，對場內(nèi)航空器的延誤時(shí)間的減少和繁忙機(jī)場運(yùn)行效率的提高是有效的。

4 結(jié)論

機(jī)場場面航空器動(dòng)態(tài)滑行路徑優(yōu)化是個(gè)非常復(fù)雜的問題，除了滑行路徑間的沖突，還存在航空器進(jìn)場和離場時(shí)間的不確定性以及跑道時(shí)間的不確定性。基于滾動(dòng)模糊時(shí)間窗的動(dòng)態(tài)滑行路徑優(yōu)化算法，對路徑規(guī)劃中存在路徑?jīng)_突航空器的路線進(jìn)行動(dòng)態(tài)調(diào)整。選用某機(jī)場為例，對該算法進(jìn)行驗(yàn)證，并與BREEON’S法進(jìn)行對比，結(jié)果表明滾動(dòng)模糊時(shí)間窗可減少航空器的滑行沖突，縮短滑行時(shí)間，降低滑行運(yùn)行風(fēng)險(xiǎn)并提高機(jī)場的運(yùn)行效率。