基于混合整數(shù)規(guī)劃的機(jī)場(chǎng)地面運(yùn)動(dòng)擾動(dòng)恢復(fù)

張?zhí)齑龋?丁萌，*， 左洪福

(1. 南京航空航天大學(xué)民航學(xué)院, 南京 211106； 2. 航空工業(yè)航空所飛行控制航空科技重點(diǎn)實(shí)驗(yàn)室， 西安 710065)

機(jī)場(chǎng)地面運(yùn)動(dòng)是影響場(chǎng)面運(yùn)行安全和效率的重要環(huán)節(jié)。隨著場(chǎng)面移動(dòng)目標(biāo)引導(dǎo)與控制技術(shù)的不斷發(fā)展，機(jī)場(chǎng)地面運(yùn)動(dòng)開(kāi)始由傳統(tǒng)的人工操作模式向以四維軌跡為基礎(chǔ)的新型操作模式轉(zhuǎn)變[1-5]。四維軌跡明確了移動(dòng)目標(biāo)的地面運(yùn)行路徑和路點(diǎn)到達(dá)時(shí)間，提高了地面運(yùn)動(dòng)過(guò)程的可預(yù)測(cè)性，有利于實(shí)現(xiàn)場(chǎng)面操作的協(xié)同優(yōu)化。近年來(lái)，針對(duì)航空器滑行規(guī)劃問(wèn)題的研究取得較大進(jìn)展[6]。其中，基于混合整數(shù)規(guī)劃的滑行軌跡分配方法從優(yōu)化角度對(duì)滑行規(guī)劃問(wèn)題進(jìn)行建模，能夠處理復(fù)雜的約束條件和目標(biāo)函數(shù)，顯著提高運(yùn)行效率[7-11]。盡管如此，在實(shí)際場(chǎng)面運(yùn)行過(guò)程中仍然可能出現(xiàn)操作失誤、設(shè)備故障、非合作目標(biāo)侵入等多種干擾事件，使得移動(dòng)目標(biāo)無(wú)法按照計(jì)劃軌跡運(yùn)行。為確保干擾事件出現(xiàn)后地面運(yùn)動(dòng)能夠及時(shí)恢復(fù)安全有序狀態(tài)，還需要進(jìn)一步構(gòu)建有效的擾動(dòng)恢復(fù)機(jī)制，針對(duì)干擾情況對(duì)受影響的計(jì)劃軌跡進(jìn)行動(dòng)態(tài)調(diào)整[12]。

擾動(dòng)恢復(fù)與場(chǎng)面監(jiān)視及滑行規(guī)劃系統(tǒng)之間有著密切聯(lián)系[1]。當(dāng)?shù)孛孢\(yùn)動(dòng)過(guò)程出現(xiàn)干擾事件時(shí)，擾動(dòng)恢復(fù)應(yīng)根據(jù)監(jiān)視系統(tǒng)提供的擾動(dòng)信息和航空器運(yùn)行狀態(tài)信息，以及滑行規(guī)劃系統(tǒng)提供的航空器初始計(jì)劃軌跡，對(duì)受影響航空器的計(jì)劃軌跡進(jìn)行優(yōu)化調(diào)整，使場(chǎng)面交通恢復(fù)安全有序狀態(tài)[13-14]。同時(shí)，擾動(dòng)恢復(fù)還應(yīng)盡量減少計(jì)劃路徑的變化以及目標(biāo)位置到達(dá)時(shí)間與計(jì)劃時(shí)間的偏差，以降低擾動(dòng)對(duì)跑道調(diào)度和停機(jī)位操作的影響[15]。

根據(jù)不同成因，機(jī)場(chǎng)地面運(yùn)動(dòng)的干擾事件可分為2類：一類起因于航空器自身的計(jì)劃執(zhí)行偏差，例如實(shí)際的路點(diǎn)到達(dá)時(shí)間與計(jì)劃不符、運(yùn)動(dòng)軌跡偏離計(jì)劃路徑等；另一類起因于外部事件，例如滑行道關(guān)閉、非合作目標(biāo)侵入、設(shè)備故障等，通常導(dǎo)致部分滑行道區(qū)域在一段時(shí)間內(nèi)不可用。文獻(xiàn)[16]針對(duì)不同干擾事件對(duì)地面運(yùn)動(dòng)的影響程度進(jìn)行了仿真研究。實(shí)驗(yàn)結(jié)果表明，滑行道臨時(shí)關(guān)閉和機(jī)場(chǎng)配置變化對(duì)地面運(yùn)動(dòng)的影響最為顯著。但該研究沒(méi)有探討航空器偏離計(jì)劃軌跡的情況；仿真實(shí)驗(yàn)中也未完全規(guī)避滑行沖突[17]。文獻(xiàn)[18-20]對(duì)航空器出現(xiàn)延誤(即未按時(shí)到達(dá)指定位置)時(shí)的計(jì)劃軌跡調(diào)整問(wèn)題進(jìn)行了研究。文獻(xiàn)[18,20]提出利用計(jì)劃步驟優(yōu)先次序圖調(diào)整未出現(xiàn)延誤的航空器在受影響區(qū)域的訪問(wèn)優(yōu)先級(jí)。這種局部?jī)?yōu)先級(jí)調(diào)整策略能夠確保無(wú)沖突場(chǎng)面運(yùn)行，但會(huì)對(duì)場(chǎng)面運(yùn)行效率造成不利影響[18]。文獻(xiàn)[19]提出一種基于計(jì)劃步驟優(yōu)先次序圖的延誤傳播算法，在某架航空器出現(xiàn)延誤后調(diào)整其他航空器在受影響區(qū)域的到達(dá)時(shí)間。該方法能夠確保無(wú)沖突場(chǎng)面運(yùn)行，但軌跡調(diào)整過(guò)程中缺少對(duì)運(yùn)行效率的優(yōu)化；調(diào)整后的運(yùn)行軌跡會(huì)出現(xiàn)較大的總體延誤。

綜上所述，現(xiàn)有擾動(dòng)恢復(fù)研究?jī)H針對(duì)航空器延誤問(wèn)題提出了局部調(diào)整方案，未考慮軌跡調(diào)整過(guò)程對(duì)整體運(yùn)行效率的影響。為進(jìn)一步實(shí)現(xiàn)對(duì)滑行道關(guān)閉、路徑偏離等其他干擾事件的有效處理，本文根據(jù)現(xiàn)有滑行軌跡優(yōu)化分配模型提出一種基于混合整數(shù)規(guī)劃的擾動(dòng)恢復(fù)方法。針對(duì)外部擾動(dòng)造成的滑行道關(guān)閉問(wèn)題，構(gòu)建區(qū)域可用性約束，使航空器避開(kāi)擾動(dòng)影響范圍。針對(duì)航空器偏離計(jì)劃路徑問(wèn)題，根據(jù)航空器實(shí)際位置對(duì)計(jì)劃軌跡進(jìn)行調(diào)整，構(gòu)建沖突規(guī)避約束，確保場(chǎng)面運(yùn)行安全。與現(xiàn)有局部調(diào)整策略不同，本文方法從優(yōu)化角度對(duì)擾動(dòng)恢復(fù)問(wèn)題進(jìn)行建模和求解，充分利用混合整數(shù)規(guī)劃方法的復(fù)雜約束建模和指標(biāo)優(yōu)化能力，統(tǒng)一處理受擾動(dòng)影響的航空器，實(shí)現(xiàn)最優(yōu)計(jì)劃軌跡調(diào)整；并通過(guò)在目標(biāo)函數(shù)中引入對(duì)軌跡變化的懲罰，降低擾動(dòng)對(duì)其他場(chǎng)面操作的影響。

1 問(wèn)題描述

為確保運(yùn)行安全，分區(qū)域控制滑行道的使用，每個(gè)區(qū)域在任意時(shí)刻只允許一架航空器占用[9]。如圖1所示，每個(gè)交叉口將作為一個(gè)單獨(dú)區(qū)域；較長(zhǎng)的路段將被進(jìn)一步分割為若干單元區(qū)域，以提高滑行道使用效率。航空器的滑行路徑通常貫穿多個(gè)區(qū)域。航空器到達(dá)各區(qū)域邊界與運(yùn)行路徑交點(diǎn)的時(shí)間稱為路點(diǎn)到達(dá)時(shí)間。

在著陸或推出后，航空器將按照已分配的計(jì)劃軌跡開(kāi)始滑行。計(jì)劃軌跡明確了航空器從起始位置到目標(biāo)位置的滑行路徑以及各路點(diǎn)的期望到達(dá)時(shí)間。擾動(dòng)恢復(fù)應(yīng)確保調(diào)整后的航空器計(jì)劃軌跡符合滑行道的物理布局，航空器在各區(qū)域的通行時(shí)間與實(shí)際滑行速度相符，不同航空器的計(jì)劃軌跡之間不會(huì)出現(xiàn)沖突。同時(shí)，擾動(dòng)恢復(fù)過(guò)程中還應(yīng)解決以下問(wèn)題：

圖1 滑行道受控區(qū)域、路點(diǎn)與滑行路徑示意圖Fig.1 Schematic of taxiway controlled zones, waypoints and taxiing route

4) 當(dāng)有多種軌跡調(diào)整方案滿足上述約束條件時(shí)，擾動(dòng)恢復(fù)應(yīng)當(dāng)在計(jì)算時(shí)間允許的范圍內(nèi)選出總體運(yùn)行效率最高且對(duì)其他場(chǎng)面操作影響最小的軌跡調(diào)整方案。

2 混合整數(shù)規(guī)劃模型

2.1 決策變量

2.2 目標(biāo)函數(shù)

機(jī)場(chǎng)地面運(yùn)動(dòng)擾動(dòng)恢復(fù)的主要目標(biāo)為減少干擾事件對(duì)場(chǎng)面運(yùn)行效率及其他相關(guān)場(chǎng)面操作的影響。為此，定義目標(biāo)函數(shù)為

(1)

式(1)通過(guò)最小化航空器的滑行時(shí)間，確保軌跡調(diào)整后仍有較高的場(chǎng)面運(yùn)行效率；通過(guò)最小化目標(biāo)位置到達(dá)時(shí)間及滑行路徑變化量，降低干擾事件對(duì)跑道、停機(jī)位相關(guān)操作的影響。

輔助變量y用于線性化目標(biāo)位置到達(dá)時(shí)間變化量，滿足以下條件：

(2)

(3)

2.3 約束條件

根據(jù)第1節(jié)的分析與第2.1節(jié)的決策變量定義，區(qū)域路由變量r應(yīng)滿足以下約束：

(4)

(5)

(6)

ra,p,q,k+ra,q,p,k+1≤1 ?a,k,p,q

(7)

式(4)表示每架航空器在每個(gè)滑行步驟中有且僅有一個(gè)區(qū)域路由變量取非零值，即航空器不能同時(shí)出現(xiàn)在2個(gè)不同位置。式(5)表示區(qū)域路由變量取值與區(qū)域連通性相符，以確保航空器不會(huì)按實(shí)際中并不存在的路徑運(yùn)行。式(6)表示區(qū)域路由變量取值具有連續(xù)性，以避免出現(xiàn)航空器位置跳變的情況。式(7)表示航空器不能在到達(dá)區(qū)域終點(diǎn)后直接折返。

與區(qū)域路由變量類似，路點(diǎn)路由變量n應(yīng)滿足以下約束：

(8)

(9)

(10)

為關(guān)聯(lián)區(qū)域路由變量r與路點(diǎn)路由變量n，定義輔助變量η描述航空器在每個(gè)滑行步驟的目標(biāo)路點(diǎn)。變量r、n與η滿足以下關(guān)系：

ra,p,q,k=1?ηa,k=Vp,q?a,p,q,k

(11)

na,i,j,k=1?ηa,k=j?a,i,j,k

(12)

na,i,j,k=1?ηa,k-1=i?a,i,j,k

(13)

式中：Vp,q為位于區(qū)域p、q公共邊界上的路點(diǎn)。

(14)

(15)

?a,b,p,q,k

(16)

M(1-xa,b,q) ?a,b,p,q,k

(17)

為規(guī)避滑行沖突，定義0-1輔助變量f：fa,b,p,k,l=1表示航空器a、b分別在滑行步驟k、l占用區(qū)域p，且航空器a先于航空器b占用區(qū)域p。容易驗(yàn)證，為實(shí)現(xiàn)沖突規(guī)避，變量f與變量t、r之間應(yīng)滿足以下關(guān)系：

fa,b,p,k,l=1?tb,l-1≥ta,k+δ?a,b,p,k,l

1) 四季竹和少穗竹2種竹筍的含水量均超過(guò)90%，表明2種竹筍的口感均較好；四季竹筍的灰分和粗脂肪含量均高于少穗竹，但蛋白質(zhì)含量低于少穗竹。

(18)

(19)

(20)

fb,a,p,l,k)≤1 ?a,b,p,k,l

(21)

此外，擾動(dòng)恢復(fù)還應(yīng)滿足以下邊界條件：

(22)

(23)

(24)

(25)

(26)

2.4 求解方法

式(1)～式(26)描述的混合整數(shù)規(guī)劃模型可直接利用CPLEX等通用求解器求解。但由于模型變量較多、約束較為復(fù)雜，通用求解器有時(shí)無(wú)法在有限的計(jì)算時(shí)間內(nèi)得到可行解[12]。為此，可利用迭代沖突規(guī)避策略[8,21]減少變量和約束數(shù)量、提高求解效率。本文采用以下迭代沖突規(guī)避求解策略：

步驟1不考慮航空器之間的沖突，式(1)～式(26)描述的模型可按航空器分解，分別確定每架航空器的最優(yōu)滑行軌跡。

步驟2檢查所得軌跡是否存在沖突。若存在沖突，則引入對(duì)應(yīng)的變量和約束，轉(zhuǎn)到步驟3；否則，轉(zhuǎn)到步驟4。

步驟3對(duì)更新后的模型進(jìn)行求解，得到一組新的計(jì)劃軌跡，轉(zhuǎn)到步驟2。

步驟4輸出當(dāng)前結(jié)果，求解結(jié)束。

在步驟2中，若航空器a、b分別在各自的滑行步驟k、l占用區(qū)域p，且二者在區(qū)域p的占用時(shí)間窗存在沖突，則在模型中引入變量fa,b,p,k,l與fb,a,p,l,k，同時(shí)引入與變量fa,b,p,k,l、fb,a,p,l,k相關(guān)的約束。

以上基于迭代沖突規(guī)避策略的求解方法僅在擾動(dòng)恢復(fù)模型中引入必要的沖突規(guī)避變量和約束，大大降低了問(wèn)題的復(fù)雜度。所有簡(jiǎn)化問(wèn)題的求解時(shí)間之和一般遠(yuǎn)小于原問(wèn)題的求解時(shí)間。

3 算例分析

針對(duì)路徑偏離和滑行道關(guān)閉2種情況，通過(guò)仿真實(shí)驗(yàn)算例對(duì)本文擾動(dòng)恢復(fù)方法的有效性進(jìn)行了驗(yàn)證。場(chǎng)面運(yùn)行環(huán)境基于南京祿口機(jī)場(chǎng)布局構(gòu)建，實(shí)驗(yàn)平臺(tái)為配備i7處理器和8 GB內(nèi)存的個(gè)人計(jì)算機(jī)。利用MATLAB完成輸入輸出數(shù)據(jù)處理，基于AMPL實(shí)現(xiàn)混合整數(shù)規(guī)劃建模，利用CPLEX 12.7.1對(duì)混合整數(shù)規(guī)劃模型進(jìn)行求解。目標(biāo)函數(shù)式(1)中的權(quán)重系數(shù)取w1=1，w2=50，w3=20。

算例1路徑偏離

在該算例中，初始階段有2架航空器a、b同時(shí)在場(chǎng)面滑行，計(jì)劃路徑如圖2(a)所示。某時(shí)刻，系統(tǒng)檢測(cè)到航空器a未能在區(qū)域41按計(jì)劃路徑轉(zhuǎn)向進(jìn)入?yún)^(qū)域42，而將進(jìn)入?yún)^(qū)域9，如圖2(b)所示。與此同時(shí)，航空器b正沿另一路徑向區(qū)域9運(yùn)行。

為避免航空器a、b發(fā)生沖突，在檢測(cè)到航空器a偏離計(jì)劃路徑后，系統(tǒng)立即對(duì)航空器a、b的計(jì)劃軌跡進(jìn)行調(diào)整。利用本文擾動(dòng)恢復(fù)方法得到如圖2(c)和圖2(d)所示結(jié)果。其中，航空器a在進(jìn)入?yún)^(qū)域9后轉(zhuǎn)向進(jìn)入?yún)^(qū)域8，沿新路徑運(yùn)動(dòng)到達(dá)目標(biāo)位置。為避免與航空器a發(fā)生對(duì)頭沖突，航空器b在區(qū)域8轉(zhuǎn)向并進(jìn)入?yún)^(qū)域42，再經(jīng)過(guò)區(qū)域41進(jìn)入?yún)^(qū)域9，重新回到初始的計(jì)劃路徑。本算例的求解時(shí)間約為0.4 s。

算例2滑行道關(guān)閉

在該算例中，某時(shí)刻滑行道區(qū)域11需臨時(shí)關(guān)閉5 min。此時(shí)，有7架航空器a1～a7正在滑行或即將開(kāi)始按計(jì)劃軌跡滑行。圖3(a)展示了航空器a1～a7初始計(jì)劃軌跡在各區(qū)域的占用時(shí)間窗，以及區(qū)域11將要關(guān)閉的時(shí)間段。若按初始計(jì)劃軌跡滑行，航空器a3、a5、a2將會(huì)在區(qū)域11關(guān)閉期間依次經(jīng)過(guò)該區(qū)域。因此，必須對(duì)航空器a3、a5、a2的計(jì)劃軌跡進(jìn)行調(diào)整。由于航空器a3、a5、a2與另外4架航空器的計(jì)劃軌跡之間存在相互影響，擾動(dòng)恢復(fù)時(shí)將對(duì)所有7架航空器的計(jì)劃軌跡進(jìn)行調(diào)整。軌跡調(diào)整后，航空器a1～a7在各區(qū)域的占用時(shí)間窗如圖3(b)所示，均避開(kāi)了擾動(dòng)影響范圍。

圖2 路徑偏離擾動(dòng)恢復(fù)結(jié)果Fig.2 Disruption recovery result for route deviation

圖3 初始與調(diào)整后軌跡的區(qū)域占用時(shí)間窗Fig.3 Zone occupancy time windows for original and recovered trajectories

圖4(a)～(c)進(jìn)一步對(duì)比了軌跡調(diào)整前后航空器a3、a5、a2的區(qū)域占用時(shí)間窗。由此可以看到航空器a3、a5、a2的計(jì)劃軌跡變化情況(滑行道區(qū)域布局見(jiàn)圖2)：在新的計(jì)劃軌跡中，航空器從區(qū)域12進(jìn)入?yún)^(qū)域10，繞過(guò)了區(qū)域11，然后經(jīng)過(guò)區(qū)域8進(jìn)入?yún)^(qū)域9，回到初始計(jì)劃路徑；航空器在區(qū)域12等待一段時(shí)間后進(jìn)入?yún)^(qū)域10，然后經(jīng)過(guò)區(qū)域8、9進(jìn)入?yún)^(qū)域6，回到初始計(jì)劃路徑；航空器為了繞過(guò)區(qū)域11，從區(qū)域41進(jìn)入?yún)^(qū)域9，然后經(jīng)過(guò)區(qū)域8、10、13、14進(jìn)入?yún)^(qū)域16，回到初始計(jì)劃路徑。

另外，擾動(dòng)恢復(fù)過(guò)程未改變另外4架航空器的計(jì)劃路徑，僅對(duì)部分航空器的路點(diǎn)到達(dá)時(shí)間進(jìn)行了適當(dāng)調(diào)整，如圖4(d)～(g)所示。其中，航空器a1的計(jì)劃軌跡未發(fā)生變化，航空器a4和a6在部分區(qū)域的占用時(shí)間窗出現(xiàn)一定程度的變化，航空器a7的計(jì)劃軌跡變化也較小。

軌跡調(diào)整后，航空器的目標(biāo)位置到達(dá)時(shí)間變化情況如表1所示。除航空器a2、a4、a7的目標(biāo)位置到達(dá)時(shí)間略有增加外，其余航空器的目標(biāo)位置到達(dá)時(shí)間均與初始值相同，從而有效降低了擾動(dòng)對(duì)跑道、停機(jī)位等其他場(chǎng)面操作的影響。

圖4 擾動(dòng)恢復(fù)前后各航空器的區(qū)域占用時(shí)間窗對(duì)比Fig.4 Comparison of zone occupancy time windows for individual aircraft before and after disruption recovery

由于本算例中航空器數(shù)量較多，直接利用求解器求解所需計(jì)算時(shí)間為139.8 s。應(yīng)用迭代沖突規(guī)避策略后，計(jì)算時(shí)間下降至26.5 s。為進(jìn)一步提高求解效率，可分組對(duì)航空器進(jìn)行調(diào)整，并通過(guò)在混合整數(shù)規(guī)劃模型中增加相應(yīng)的預(yù)留時(shí)間窗約束，避免不同組航空器的計(jì)劃軌跡發(fā)生沖突。不同的分組方式和分組大小均會(huì)對(duì)計(jì)算結(jié)果產(chǎn)生影響。實(shí)驗(yàn)發(fā)現(xiàn)，按跑道占用優(yōu)先次序?qū)娇掌鬟M(jìn)行分組能夠有效減少計(jì)算時(shí)間，同時(shí)對(duì)求解質(zhì)量影響也較小。本算例中，航空器的跑道占用優(yōu)先次序?yàn)閍2>a4>a6>a1>a3>a5>a7。將航空器分為{a2,a4,a6,a1}和{a3,a5,a7}2組進(jìn)行軌跡調(diào)整，能夠在不影響求解質(zhì)量的情況下將計(jì)算時(shí)間減少至4.9 s。

表1 航空器目標(biāo)位置到達(dá)時(shí)間變化Table 1 Change of aircraft destination arrival time s

4 結(jié) 論

本文針對(duì)機(jī)場(chǎng)地面運(yùn)動(dòng)擾動(dòng)恢復(fù)問(wèn)題提出一種基于混合整數(shù)規(guī)劃的軌跡調(diào)整方法。

1) 本文方法能夠有效處理復(fù)雜的約束條件和目標(biāo)函數(shù)，實(shí)現(xiàn)對(duì)計(jì)劃軌跡的優(yōu)化調(diào)整。

2) 本文方法保證了軌跡可行性和運(yùn)行效率，并通過(guò)最小化目標(biāo)位置到達(dá)時(shí)間和路徑變化量，降低了軌跡調(diào)整對(duì)其他場(chǎng)面操作的影響。

3) 實(shí)驗(yàn)結(jié)果表明，本文方法能夠在航空器偏離計(jì)劃路徑和滑行道臨時(shí)關(guān)閉等干擾事件出現(xiàn)后，實(shí)現(xiàn)快速、有效的擾動(dòng)恢復(fù)。