基于混合整數規劃的機場地面運動擾動恢復

張天慈， 丁萌，*， 左洪福

(1. 南京航空航天大學民航學院, 南京 211106； 2. 航空工業航空所飛行控制航空科技重點實驗室， 西安 710065)

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

擾動恢復與場面監視及滑行規劃系統之間有著密切聯系[1]。當地面運動過程出現干擾事件時，擾動恢復應根據監視系統提供的擾動信息和航空器運行狀態信息，以及滑行規劃系統提供的航空器初始計劃軌跡，對受影響航空器的計劃軌跡進行優化調整，使場面交通恢復安全有序狀態[13-14]。同時，擾動恢復還應盡量減少計劃路徑的變化以及目標位置到達時間與計劃時間的偏差，以降低擾動對跑道調度和停機位操作的影響[15]。

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

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

1 問題描述

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

在著陸或推出后，航空器將按照已分配的計劃軌跡開始滑行。計劃軌跡明確了航空器從起始位置到目標位置的滑行路徑以及各路點的期望到達時間。擾動恢復應確保調整后的航空器計劃軌跡符合滑行道的物理布局，航空器在各區域的通行時間與實際滑行速度相符，不同航空器的計劃軌跡之間不會出現沖突。同時，擾動恢復過程中還應解決以下問題：

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

4) 當有多種軌跡調整方案滿足上述約束條件時，擾動恢復應當在計算時間允許的范圍內選出總體運行效率最高且對其他場面操作影響最小的軌跡調整方案。

2 混合整數規劃模型

2.1 決策變量

2.2 目標函數

機場地面運動擾動恢復的主要目標為減少干擾事件對場面運行效率及其他相關場面操作的影響。為此，定義目標函數為

(1)

式(1)通過最小化航空器的滑行時間，確保軌跡調整后仍有較高的場面運行效率；通過最小化目標位置到達時間及滑行路徑變化量，降低干擾事件對跑道、停機位相關操作的影響。

輔助變量y用于線性化目標位置到達時間變化量，滿足以下條件：

(2)

(3)

2.3 約束條件

根據第1節的分析與第2.1節的決策變量定義，區域路由變量r應滿足以下約束：

(4)

(5)

(6)

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

(7)

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

與區域路由變量類似，路點路由變量n應滿足以下約束：

(8)

(9)

(10)

為關聯區域路由變量r與路點路由變量n，定義輔助變量η描述航空器在每個滑行步驟的目標路點。變量r、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為位于區域p、q公共邊界上的路點。

(14)

(15)

?a,b,p,q,k

(16)

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

(17)

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

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

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

(18)

(19)

(20)

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

(21)

此外，擾動恢復還應滿足以下邊界條件：

(22)

(23)

(24)

(25)

(26)

2.4 求解方法

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

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

步驟2檢查所得軌跡是否存在沖突。若存在沖突，則引入對應的變量和約束，轉到步驟3；否則，轉到步驟4。

步驟3對更新后的模型進行求解，得到一組新的計劃軌跡，轉到步驟2。

步驟4輸出當前結果，求解結束。

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

以上基于迭代沖突規避策略的求解方法僅在擾動恢復模型中引入必要的沖突規避變量和約束，大大降低了問題的復雜度。所有簡化問題的求解時間之和一般遠小于原問題的求解時間。

3 算例分析

針對路徑偏離和滑行道關閉2種情況，通過仿真實驗算例對本文擾動恢復方法的有效性進行了驗證。場面運行環境基于南京祿口機場布局構建，實驗平臺為配備i7處理器和8 GB內存的個人計算機。利用MATLAB完成輸入輸出數據處理，基于AMPL實現混合整數規劃建模，利用CPLEX 12.7.1對混合整數規劃模型進行求解。目標函數式(1)中的權重系數取w1=1，w2=50，w3=20。

算例1路徑偏離

在該算例中，初始階段有2架航空器a、b同時在場面滑行，計劃路徑如圖2(a)所示。某時刻，系統檢測到航空器a未能在區域41按計劃路徑轉向進入區域42，而將進入區域9，如圖2(b)所示。與此同時，航空器b正沿另一路徑向區域9運行。

為避免航空器a、b發生沖突，在檢測到航空器a偏離計劃路徑后，系統立即對航空器a、b的計劃軌跡進行調整。利用本文擾動恢復方法得到如圖2(c)和圖2(d)所示結果。其中，航空器a在進入區域9后轉向進入區域8，沿新路徑運動到達目標位置。為避免與航空器a發生對頭沖突，航空器b在區域8轉向并進入區域42，再經過區域41進入區域9，重新回到初始的計劃路徑。本算例的求解時間約為0.4 s。

算例2滑行道關閉

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

圖2 路徑偏離擾動恢復結果Fig.2 Disruption recovery result for route deviation

圖3 初始與調整后軌跡的區域占用時間窗Fig.3 Zone occupancy time windows for original and recovered trajectories

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

另外，擾動恢復過程未改變另外4架航空器的計劃路徑，僅對部分航空器的路點到達時間進行了適當調整，如圖4(d)～(g)所示。其中，航空器a1的計劃軌跡未發生變化，航空器a4和a6在部分區域的占用時間窗出現一定程度的變化，航空器a7的計劃軌跡變化也較小。

軌跡調整后，航空器的目標位置到達時間變化情況如表1所示。除航空器a2、a4、a7的目標位置到達時間略有增加外，其余航空器的目標位置到達時間均與初始值相同，從而有效降低了擾動對跑道、停機位等其他場面操作的影響。

圖4 擾動恢復前后各航空器的區域占用時間窗對比Fig.4 Comparison of zone occupancy time windows for individual aircraft before and after disruption recovery

由于本算例中航空器數量較多，直接利用求解器求解所需計算時間為139.8 s。應用迭代沖突規避策略后，計算時間下降至26.5 s。為進一步提高求解效率，可分組對航空器進行調整，并通過在混合整數規劃模型中增加相應的預留時間窗約束，避免不同組航空器的計劃軌跡發生沖突。不同的分組方式和分組大小均會對計算結果產生影響。實驗發現，按跑道占用優先次序對航空器進行分組能夠有效減少計算時間，同時對求解質量影響也較小。本算例中，航空器的跑道占用優先次序為a2>a4>a6>a1>a3>a5>a7。將航空器分為{a2,a4,a6,a1}和{a3,a5,a7}2組進行軌跡調整，能夠在不影響求解質量的情況下將計算時間減少至4.9 s。

表1 航空器目標位置到達時間變化Table 1 Change of aircraft destination arrival time s

4 結 論

本文針對機場地面運動擾動恢復問題提出一種基于混合整數規劃的軌跡調整方法。

1) 本文方法能夠有效處理復雜的約束條件和目標函數，實現對計劃軌跡的優化調整。

2) 本文方法保證了軌跡可行性和運行效率，并通過最小化目標位置到達時間和路徑變化量，降低了軌跡調整對其他場面操作的影響。

3) 實驗結果表明，本文方法能夠在航空器偏離計劃路徑和滑行道臨時關閉等干擾事件出現后，實現快速、有效的擾動恢復。