基于區域控制的航空器滑行軌跡優化模型

張天慈, 丁　萌, 左洪福, 王幫峰, 曾麗娜, 孫澤軍

(1.南京航空航天大學民航學院, 江蘇 南京 211106;

2. 中國商用飛機有限責任公司客戶服務中心, 上海 200241)

?

基于區域控制的航空器滑行軌跡優化模型

張天慈1, 丁萌1, 左洪福1, 王幫峰2, 曾麗娜1, 孫澤軍1

(1.南京航空航天大學民航學院, 江蘇 南京 211106;

2. 中國商用飛機有限責任公司客戶服務中心, 上海 200241)

摘要：針對現有模型解決航空器滑行軌跡優化時沖突約束能力不足問題,提出了一種新的混合整數線性規劃(mixed integer linear programming,MILP)模型。利用區域劃分和區域公共節點網絡構建層次化滑行道結構模型,提高了滑行道建模精度,并在此基礎上應用區域控制規則實現對滑行道的無沖突占用。同時,基于滾動時域策略對復雜的滑行軌跡優化問題分階段求解,提高了滑行規劃模塊的靈活性和求解速度。實驗結果表明，利用該模型能夠有效回避滑行沖突，降低平均滑行時間和距離，提高場面運行效率。

關鍵詞：航空運輸; 沖突回避; 區域控制; 滑行軌跡優化; 滾動時域; 混合整數線性規劃

0引言

隨著空中交通量的不斷增加,機場在空中交通系統中的瓶頸效應日益凸顯,航空器地面滑行過程已成為制約場面運行效率的主要因素之一,為此,滑行優化問題近年來得到了廣泛關注[1-2]。

在滑行過程中,航空器之間需保持足夠的間隔以避免沖突。現有基于混合整數線性規劃(mixed integer linear programming, MILP)的滑行軌跡優化模型對安全間隔的約束方式取決于問題設定。例如,文獻[3-5]研究了固定路徑下的滑行調度問題,利用二值排序變量實現對滑行道的有序占用、保證安全間隔。文獻[6]研究了自由路由下的滑行路徑和調度同時優化(本文簡稱滑行軌跡優化),基于時空網絡模型利用離散時間變量描述滑行過程,通過頂點容量約束避免航空器沖突。但為保證路段上的安全間隔,航空器需按相同的速度運動。文獻[7]進一步利用排序變量實現了連續時間建模,允許航空器滑行速度在一定范圍內變動,但為避免超越沖突,該模型要求所有路段必須足夠短。此外,以上方法均采用節點-路段模型對滑行道進行描述,忽略了交叉口區域的空間結構,帶來了建模偏差。

相對固定路徑下的滑行調度、滑行路徑和調度的同時優化能夠更加充分地利用機場場面資源,但同時也增加了問題的求解難度。為此,文獻[8-9]均研究了基于順序規劃的滑行路徑規劃框架。與上述MILP集中優化模型相比,順序規劃策略能夠大大降低運算復雜度,但會造成最優性的損失。

針對上述問題,提出一種更加精確的滑行道結構模型,避免傳統節點-路段模型的建模偏差,并利用區域控制思想提高沖突約束能力。在此基礎上,利用文獻[7]的連續時間建模思想,提出一種基于滾動時域框架的滑行軌跡優化模型。最后，通過仿真實驗驗證了模型的沖突回避能力、規劃結果的效率優勢和滾動時域策略帶來的計算效率提升。

1區域控制與滾動時域

在自主引導車系統中,區域控制常被用于規避自主引導車(automated guided vehicle, AGV)之間的沖突[10-12]。它將AGV的活動場面劃分為相互不重疊的若干區域,每個區域在任意時刻只能被一輛AGV占用,以避免資源搶占沖突或者碰撞事故。本文基于該思想提出一種新的滑行軌跡優化模型,以彌補傳統模型沖突控制能力的不足。

1.1滑行道結構模型

首先,根據實際布局將滑行道劃分為若干不重疊區域,得到滑行道區域劃分模型;然后,根據滑行道區域連接關系構建區域公共節點網絡模型;最后,將二者按空間位置疊加得到層次化的滑行道結構模型,如圖1所示。該模型避免了節點-路段模型的建模偏差,確保了規劃軌跡與滑行道中線的一致性,使規劃結果更加精確。

圖1　滑行道結構模型示例

1.2區域控制

設滑行道結構模型中所有區域的集合為E,則區域控制規則可通過下式描述:

?r∈E:load(r,t)≤1

(1)

式中，load(r,t)表示在t時刻占用區域r的航空器數量。

當所有航空器的計劃軌跡均滿足式(1)時,滑行道各區域在任意時刻最多只被一架航空器占用。

1.3滾動時域

為降低復雜度,路徑規劃中常采用分段求解框架[3,13],利用滾動時域策略將問題規模限制在有限的時間范圍內,僅對后續運行過程進行粗略估計;為避免區間效應,規劃結果通常在一個長度小于規劃區間的執行區間內有效,并在執行區間的結束時刻重新規劃。

本文基于該框架構建滑行軌跡優化模型,如圖2所示。在新規劃周期的起始,確定所有活動航空器的狀態信息,作為優化模型的輸入;然后,調用求解器求解優化問題實例,得到階段性最優滑行路徑和調度;航空器按照規劃結果運行,直到新的規劃結果出現。這種動態求解策略不僅能夠有效降低計算量,也使得路徑規劃模塊能夠更加靈活地應對運行過程中出現的干擾[7]。

圖2　滾動時域滑行軌跡優化框架

2滑行軌跡優化模型

在機場場面上,離港航空器從停機位推出后,沿滑行道運行到達目標跑道入口;進港航空器脫離著陸跑道后,沿滑行道運行到達指定停機位。滑行軌跡優化問題研究如何為進離港航空器規劃最優的運行路徑和到達路徑上關鍵位置的時間。

2.1輸入數據

輸入數據可分為靜態參數和動態參數兩類,其中靜態參數主要用于描述機場布局結構等信息,一般在整個規劃過程中固定不變。動態參數指隨規劃區間滾動而發生變化的輸入數據。

2.1.1靜態參數

設滑行道結構模型包含Ne個區域和Nv個公共節點,記區域集合為E、公共節點集合為V。靜態參數包括:

(1)CNe×Ne:描述區域連通性。任意x,y∈E,若二者直接相連則Cx,y=1,否則Cx,y=0。

(2)DNv×Nv:描述節點連通性。任意m,n∈V,若二者直接相連則Dm,n=1,否則Dm,n=0。

(3)JNe×Ne:描述相鄰區域公共節點。

(4)LNv×Nv:描述連接兩個公共節點的滑行道中線長度。

此外,靜態參數還包括航空器最早可以開始滑行的時刻和位置、航空器最大滑行速度vmax和每次規劃的滑行步驟數Np。

2.1.2動態參數

動態參數依賴于航空器的當前運行狀態。若用Ai表示規劃周期i內Ni個活動航空器集合,則對任意a∈Ai,與其相關的動態參數包括在當前規劃周期的起始區域r0i、起始節點n0i、起始時刻t0i以及目標區域rei和目標節點nei。

規劃周期i內的活動航空器一般包括兩類:第一類航空器在當前規劃區間的起始時刻ti已經開始滑行,并且尚未完成滑行過程;第二類航空器在ti時刻尚未開始滑行,但將在當前規劃區間內開始滑行。第一類航空器的起始位置取ti時刻所在區域和ti之后將要到達的第一個節點,起始時刻取上一次規劃結果中到達該位置的時刻。第二類航空器的起始位置和時刻可直接從靜態參數中讀取。

2.2決策變量

(1)X∈{0,1}Ni×Ne×Ne×Np

若航空器a在第k個滑行步驟從區域x向區域y運行,則Xa,x,y,k=1,否則Xa,x,y,k=0。

(2)Y∈{0,1}Ni×Nv×Nv×Np

若航空器a在第k個滑行步驟從節點m運行到節點n,則Ya,m,n,k=1,否則Ya,m,n,k=0。

(3)N∈{1,…,Nn}|Ai|×Np

Na,k表示航空器a在第k個滑行步驟結束時到達的節點。

(4)T∈R|Ai|×Np

Ta,k表示航空器a完成第k個滑行步驟的時刻。

在滑行路徑和調度同時優化問題中,航空器可以在運行規則允許的范圍內自由選擇滑行路徑。定義航空器之間可能出現的沖突集合為F={{a,b,x}:a,b∈Ai,a≠b,x∈E}。為構建沖突回避約束,還需定義如下輔助決策變量:

(1)S{a,b,z},j,k

對?j,k∈{1,…,Np},{a,b,z}∈F,二值變量S{a,b,z},j,k=1,當且僅當航空器a、b分別在各自的第j、k個滑行步驟占用區域z。

(2)G{a,b,z},j,k

二值變量G{a,b,z},j,k=1,當且僅當航空器a、b分別在各自的第j、k個滑行步驟占用區域z,且航空器a先于航空器b占用z。

由上述定義可知,變量S和X之間有如下關系:

(2)

根據下式可以將式(2)轉換為線性不等關系[5]:

(3)

2.3約束

2.3.1起始約束

為保證航空器的計劃路徑和時間與輸入數據指定的起始位置和起始時刻相符,引入如下約束:

(4)

2.3.2連通性約束

滑行路徑需要與區域的連通性一致,對應的約束如下:

(5)

(6)

2.3.3可行性約束

為保證路徑的可行性,變量X、Y還需滿足

(7)

(8)

(9)

(10)

(11)

其中,式(7)、式(8)保證了航空器始終有可用的滑行路徑;式(9)、式(10)保證了航空器滑行過程的連續性;式(11)保證了滑行路徑中不會出現直接折返的現象。

2.3.4滑行速度約束

當滑行過程中允許停車等待時,航空器只需滿足最大滑行速度約束:

(12)

2.3.5區域控制規則約束

式(1)描述的區域控制規則可通過如下約束實現:

(13)

(14)

式(13)、式(14)中,M為任意足夠大的正數,用于松弛約束;δ是一個很小的正常量,用于避免同時資源交換[14]引發的對頭沖突。

2.3.6終止約束

規劃過程擴展到航空器的目標位置時,需要滿足如下約束:

(15)

(16)

2.3.7其他約束

以下約束描述了變量間需要滿足的關系:

(17)

(18)

(19)

2.4目標函數

以常用的滑行時間和滑行距離作為優化指標,對航空器a∈Ai,定義滑行軌跡代價函數如下:

(20)

式中,第一項和第二項分別代表滑行時間和距離;α和β分別為滑行時間和滑行距離的權重,滿足α,β∈[0,1],α+β=1;H表示任意兩節點間靜態最短路徑的長度。因此,第三項代表了對后續運行過程的粗略估計。

根據式(20)可定義滑行軌跡優化的目標函數如下:

(21)

3實驗驗證

本節首先通過仿真實驗驗證上述模型的沖突回避能力;然后與一種先到先服務的順序規劃(sequential planning,SP)策略[6-7]進行對比,驗證MILP模型所得結果的效率優勢;最后對滾動時域策略帶來的計算效率提升進行了分析。

3.1實驗設置

滑行道結構模型基于南京祿口國際機場構建,覆蓋了其主要滑行道區域、跑道及停機位,共包含56個區域和72個公共節點。航空器初始狀態采用隨機方式生成,共30架次。相鄰航空器的滑行起始時刻間隔在0~100 s之間均勻分布。最大滑行速度取10 m/s;規劃區間和執行區間長度均取25 s;規劃步驟數取Np=4;目標函數中,滑行時間和距離的權重取α=β=0.5。

實驗中MILP模型使用AMPL建模語言[15]構建,利用商業求解器CPLEX 12.5.1求解。實驗基于2.5 GHz英特爾酷睿i7處理器、8 GB內存計算機,在Window 8.1操作系統下完成。

3.2實驗結果與分析

3.2.1規劃結果的有效性

航空器對各區域的占用時間窗如圖3所示。縱坐標表示滑行道結構模型中的區域編號,橫坐標表示系統時間。圖中矩形表示某架航空器對相應區域的占用時間窗。由圖3可知,位于同一行的時間窗均不存在重疊區間。因此,航空器對每個區域的占用過程均符合區域控制規則。

圖3　區域占用時間窗

3.2.2規劃結果的效率

圖4和圖5給出了各航空器的滑行時間和滑行距離分布情況,橫縱坐標分別對應MILP和SP所得結果。位于對角線上的數據點表示SP和MILP結果相同;對角線上(下)方數據點表示SP數值大于(小于)MILP數值。

圖4　滑行時間分布

圖5　滑行距離分布

由圖4可知,MILP所得結果中約5/6的航空器的滑行時間與SP相比有所減少,其中兩架的滑行時間減少了50%以上。由圖5可知,MILP所得結果中僅有兩架航空器滑行距離與SP相比略有增加,超過1/4的航空器滑行距離明顯減少,其余航空器滑行距離與SP結果基本一致。相對滑行時間而言,MILP對滑行距離的改善程度略有下降,主要原因如下:

(1) 所選機場滑行道結構較為簡單,航空器在指定停機位和跑道入口或脫離口之間的路徑缺少多樣性,路徑長度相對固定;

(2) 滑行距離和時間兩個度量標準本身具有較強的相關性,SP雖然僅以最小化滑行時間為準則確定最優滑行軌跡,但所得結果一般不會出現滑行距離過大的情況。

表1進一步給出了滑行時間和滑行距離等參數的統計平均值。平均繞行距離表示航空器為回避沖突額外運行的距離,等于實際運行距離減去靜態最短路徑長度;平均等待時間為滑行過程中航空器為回避沖突而減速或停止等待造成的時間延誤,等于實際滑行時間減去不考慮沖突時的最短滑行時間。作為參考基準,表1(第1行)給出了不考慮滑行沖突時利用Dijksra算法[16]得到的靜態最短滑行路徑對應的滑行距離和滑行時間平均值。

由表1可知,MILP所得結果的平均滑行時間和距離與靜態最優值之差與SP相比分別減少了37%和82%。此時,SP和MILP結果的平均繞行距離和等待時間均大于零,表明在當前實驗設置下機場場面出現了一定程度的交通擁堵。進一步的實驗結果表明,場面交通密度對滑行軌跡優化結果有著重要影響。表2給出了不同交通密度下SP和MILP的規劃結果。其中每一行對應一個交通密度;從上向下交通密度逐漸下降。例如,“0~75”表示相鄰航空器的滑行起始時間間隔在0~75 s之間隨機分布。另外,與表1第4列的等待時間不同,表2中“總等待時間”表示開始滑行前的等待時間與滑行過程中的等待時間之和。

表1　平均滑行距離和滑行時間對比

由表2可知,當交通密度較低時(第3、4行),SP滑行時間和總等待時間均略小于MILP所得結果。這表明此時滾動時域框架帶來的最優性損失大于SP帶來的最優性損失。而隨著交通密度的增加,MILP的優勢開始凸顯(第1、2行)。因此,當場面較為擁堵時,MILP能夠更有效地降低滑行時間、提高場面運行效率。

表2　不同交通密度下的滑行距離和滑行時間

3.2.3計算時間

為驗證滾動時域策略帶來的計算效率提升,本節將其與不使用滾動時域策略的完全規劃方法進行對比,實驗結果如圖6所示。其中，“單次規劃”表示使用滾動時域策略時每個規劃周期需要的計算時間;“滾動時域”表示完成指定數量航空器軌跡優化所需的總計算時間;“非滾動時域”表示在不使用滾動時域策略時同時為指定數量航空器規劃完整的滑行軌跡所需的計算時間。為排除偶然性因素的影響,圖6中各項數據均取為10次實驗結果的平均值，每次實驗均從輸入數據中隨機選取指定數量航空器進行滑行軌跡優化。

圖6　計算時間對比

由圖6可知,在當前實驗設置下,非滾動時域的計算時間將隨問題規模快速增長,當航空器數量大于5時平均計算時間已超過1 000 s,難以滿足場面運動引導與控制系統的實時需求。而使用滾動時域策略時每個規劃周期所需的平均求解時間小于1 s,能夠實現滑行軌跡的實時優化。盡管當航空器數量增加時,為全部航空器確定最優滑行軌跡所需的滾動時域操作開始增多,造成總計算時間的增大,但其增長速度仍遠小于非滾動時域結果。因此,使用滾動時域策略構建MILP模型能夠有效降低運算量,具有更好的適用性和可擴展性。

4結論

針對現有航空器滑行軌跡優化模型沖突回避能力不足的問題提出一種新的滑行道結構建模方法,并據此構建基于區域控制的MILP模型。利用滾動時域策略對大規模優化問題分階段求解,降低了運算量,也提高了滑行規劃模塊的靈活性。在交通較為擁堵時,與順序規劃策略相比能夠在有效避免滑行沖突的同時降低平均滑行時間和滑行距離,進一步提高場面運行效率。

參考文獻：

[1] Atkin J A, Burke E K, Ravizza S. The airport ground movement problem: past and current research and future directions[C]∥Proc.ofthe4thInternationalConferenceonResearchinAirTransportation, 2010: 131-138.

[2] Roling P C, Visser H G. Optimal airport surface traffic planning using mixed-integer linear programming[J].InternationalJournalofAerospaceEngineering, 2008, 2008(1): 1-11.

[3] Smeltink J W, Soomer M J. An optimisation model for airport taxi scheduling[C]∥Proc.oftheINFORMSAnnualMeeting, 2004.

[4] Rathinam S, Montoya J, Jung Y. An optimization model for reducing aircraft taxi times at the dallas fort worth international airport[C]∥Proc.ofthe26thInternationalCongressoftheAeronauticalSciences, 2008: 14-19.

[5] Dong Y, An R. Optimization of aircraft taxiing time[J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2011, 11(5): 141-146. (董瑩, 安然. 機場航空器地面滑行時間優化研究[J]. 交通運輸系統工程與信息, 2011, 11(5): 141-146.)

[6] Marín A. Airport management: taxi planning[J].AnnalsofOperationsResearch, 2006, 143(1): 191-202.

[7] Clare G L, Richards A G. Optimization of taxiway routing and runway scheduling[J].IEEETrans.onIntelligentTransportationSystems, 2011, 12(4): 1000-1013.

[8] Ravizza S, Atkin J A, Burke E K. A more realistic approach for airport ground movement optimisation with stand holding[J].JournalofScheduling, 2014, 17(5): 507-520.

[9] Tang Y, Hu M H, Huang R S, et al. Aircraft taxi routes planning based on free time windows and multi-agent for ASMGCS[J].ActaAeronauticaetAstronauticaSinica, 2015, 36(5): 1627-1638. (唐勇,胡明華,黃榮順,等.基于空閑時間窗和多Agent 的A-SMGCS航空器滑行路由規劃[J].航空學報, 2015, 36(5): 1627-1638.)

[10] Fanti M P. Event-based controller to avoid deadlock and collisions in zone-control AGVS[J].InternationalJournalofProductionResearch, 2002, 40(6): 1453-1478.

[11] Ho Y C, Liao T W. Zone design and control for vehicle collision prevention and load balancing in a zone control AGV system[J].Computers&IndustrialEngineering, 2009, 56(1): 417-432.

[12] Smolic-Rocak N, Bogdan S, Kovacic Z, et al. Time windows based dynamic routing in multi-AGV systems[J].IEEETrans.onAutomationScienceandEngineering,2010,7(1):151-155.

[13] Zhang C G. Mobile robot path planning based on rolling windows[J].SystemsEngineeringandElectronics, 2002, 24(6): 63-69. (張純剛. 基于滾動窗口的移動機器人路徑規劃[J]. 系統工程與電子技術, 2002, 24(6): 63-69.)

[14] ter Mors A. The world according to MARP: multi-agent route planning[D]. Delft University of Technology, 2010: 36-40.

[15] Fourer R, Gay D M, Kernighan B W.AMPL:amodelinglanguageformathematicalprogramming[M]. Duxbury Press, 2002.

[16] Dijkstra E W. A note on two problems in connexion with graphs[J].NumerischeMathematik, 1959, 1(1): 269-271.

張天慈(1989-),男,博士研究生,主要研究方向為機場場面路徑規劃與引導、基于計算機視覺的目標檢測、識別與跟蹤。

E-mail:tiancizh@nuaa.edu.cn

丁萌(1981-),男,副教授,博士,主要研究方向為智能交通中的視頻監控與圖像分析、無人機導航、制導與控制、民用飛機航電系統適航技術。

E-mail:nuaa_dm@hotmail.com

左洪福(1959-),男,教授,博士,主要研究方向為檢測與傳感器技術、航空發動機預測與健康管理、系統安全性分析與適航評估驗證技術、飛機系統測試性分析、故障診斷與維修誘導、飛機備件預測、庫存控制與供應鏈管理。

E-mail:rms@nuaa.edu.cn

王幫峰(1970-),男,教授,博士,主要研究方向為飛行器故障診斷技術、航空器適航技術、智能結構以及信號處理技術。

E-mail:wangbangfeng@comac.cc

曾麗娜(1988-),女,碩士研究生,主要研究方向為機場場面監視、目標檢測與識別。

E-mail:zeng_li_na@163.com

孫澤軍(1990-),男,碩士研究生,主要研究方向為機場場面監視、目標檢測與識別。

E-mail:zejunsun@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20150918.1806.016.html

Zone control based aircraft ground movement trajectory optimization model

ZHANG Tian-ci1, DING Meng1, ZUO Hong-fu1, WANG Bang-feng2, ZENG Li-na1, SUN Ze-jun1

(1.CollegeofCivilAviation,NanjingUniversityofAeronauticsandAstronautics,Nanjing211106,China;

2.CustomerServiceCenter,COMAC,Shanghai200241,China)

Abstract:Existing models for aircraft ground movement (or taxiing) trajectory optimization tend to have weak conflict avoidance capability. For this reason, a novel mixed integer linear programming (MILP) model is proposed. It utilizes a partition model and inter-region node network to enhance the modeling fidelity of taxiways, and adopts the zone control strategy to ensure conflict-free occupancy of taxiway parts. Based on the rolling horizon scheme, the proposed model solves trajectory optimization stage by stage, which reduces the computational cost in general and makes the taxi planning module more flexible. Experimental results demonstrate the effectiveness of the proposed model in terms of conflict avoidance. And a comparative test with a sequential planning approach shows that it can also improve airport ground movement efficiency with less taxi time and shorter taxi distance.

Keywords:air transportation; conflict avoidance; zone control; taxiing trajectory optimization; rolling horizon; mixed integer linear programming (MILP)

作者簡介：

中圖分類號：V 351.11

文獻標志碼：A

DOI:10.3969/j.issn.1001-506X.2016.01.22

基金項目：國家自然科學基金(61203170)；民航局科技項目(MHRD201124)；博士后科學基金特別資助項目(2013T60539)；江蘇省普通高校研究生科研創新計劃項目(KYLX0291)資助課題

收稿日期：2015-04-27；修回日期：2015-07-23；網絡優先出版日期：2015-09-18。