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

謝春生，盧菲菲，楊群亭

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

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

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

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

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

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

(1)

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

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

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

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

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

跑道的運行模式：包括隔離運行和獨立運行。

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

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

1.2 滾動模糊時間窗算法

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

表1 變量匯總

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

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

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

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

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

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

1.3 離場航空器滑行路線

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

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

圖1 離場路徑搜索流程

2 機場運行模型設(shè)計

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

滾動模糊時間窗算法的流程如圖2所示。

圖2 滾動模糊時間窗算法的流程圖

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

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

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

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

3.1 滑行時間

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

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

圖3 低密度95%不同機位滑行時間圖

圖4 中密度100%不同機位滑行時間圖

圖5 高密度125%不同機位滑行時間圖

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

圖6 3種密度交通流下不同機位平均滑行時間圖

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

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

3.2 滑行沖突

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

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

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

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

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

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

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

4 結(jié)論

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