A－SMGCS航空器動態最優滑行路徑規劃研究＊

王 翀 湯新民 安宏鋒

（南京航空航天大學民航學院 南京 210016）

0 引 言

基于航空運輸業的發展及運營要求，ICAO提出了建設先進場面引導與控制系統的構想，即A－SMGCS［1］.其中，為場面航空器指定合適路由是實現A－SMGCS的前提和關鍵.

機場場面的動態路由規劃要求保證進出港航班在滑行過程中按最短路徑連續滑行，并且不能發生對頭相遇.目前主要有兩類研究思想：（1）在傳統尋優算法思想基礎上引入時間要素，將其應用到動態最優路徑尋優中來［2－4］；（2）根據機場交通建立規劃模型［5］和網絡模型［6］，或建立包括機型和安全間隔等因素的混合整數線性規劃模型［7］.將Petri網運用于路徑規劃方面，一些學者將無向交通網轉成Petri網，再定義相關規則，求解最短路徑［8］，并引入“時間庫所”等［9］，但沒有考慮機場場面動態因素.

本文根據機場場面結構建立場面活動模型及運行控制規范，引入關鍵事件軌跡等概念，求解基于場面全局最優的航空器規劃路徑.經計算機仿真驗證，可以較好的滿足機場高負荷條件下對實時性的需求.

1 機場場面結構建模與靜態路徑規劃

機場場面交通系統是由航空器和道路、跑道、停機坪網絡組成的復雜系統，分別對靜態對象和運動對象建模是場面路徑規劃的基礎［10］.本文以成都雙流國際機場為例，建立符合機場場面物理特性和活動規則要求的場面活動模型.

定義1 場面活動模型定義為賦時庫所Petri網TPN＝｛P，T，Pre，Post，m，Γ｝.式中：庫所集P為航空器所處滑行段區域；變遷集T為航空器（托肯）所處的區域與下一區域的邊界集L；Pre與Post分別表示P與T的前向和后向關聯關系；m為場面各庫所內的航空器分布向量.Γ為航空器a在某滑行段的平均滑行時間，由滑行段長度d（p）和航空器a的平均滑行速度va（p）求解，即：Γ（a，p）＝d（p）／va（p）.機場場面活動模型需滿足以下規則.

規則1 若航空器可通過交界線l雙向通行，則有Pre（pi，t）＝1∧Post（pi，t）＝1，此時場面活動模型并非純網，為了避免這種情況的出現，需要將2個子區域的交界映射為2個變遷.

規則2 場面航空器所在滑行路段改變，需更新場面狀態標識向量m.假設第k架航空器位于允許活動子區域內，以第i元素為1的n維單位向量ei標識第k架航空器的狀態.假設場面內有na架航空器活動，則場面狀態標識向量

圖1 機場場面活動模型

圖2 航空器交叉和對頭兩種沖突

2 機場場面運行控制規范

2.1 場面活動優先規范

定義3 場面活動優先規范.場面活動模型狀態演變過程中，變遷集合之間優先激發順序關系可采用二元關系集Q定義：Q：T×T，若（t1，t2）∈Q，則表示當t1，t2∈Fe（m）時，t1優先于t2.定義航空器在交叉口相遇的二元關系集為QC.

3）相向滑行的航空器可能在某一航段發生對頭沖突.設對頭路徑πD＝（p1，…，pi，pj，pk，…，pn），航空器 A 由p0（A）向pn＋1（A）滑行，航空器B由p0（B）向pn＋1（B）滑行；則航空器 A、航空器B的可能沖突路段構成子Petri網系統＝ （PD，TD，PreD，PostD，mD，ΓD），見圖3.

圖3 對頭路徑的Petri網表示

定義二元關系集：QD：TD×TD，為TD中已激發變遷集合為未激發變遷集合，則

定義4 優先使能.設?ti，tj∈Se（m），若存在二元關系集Q 使得（ti，tj）∈（QC∪QD），則稱使能變遷集合ti為優先使能變遷集，記作Fe（m）.

2.2 場面活動禁止規范

定義5 狀態禁止規范.場面活動模型狀態演變過程中所禁止狀態可描述為標識的加權和不超過某一上限的不等式組.

根據場面管制規則對場面滑行的航空器建立如下的約束條件.

1）航空器在跑道上滑行時不允許其他航空器進入跑道，該規范可描述為

2）當跑道進近方向上有即將進入著陸的航空器，則其他航空器只能在跑道外等待，否則可進入跑道或穿越跑道，假設papproach為進近著陸庫所，則該規范可描述為

3）航空器在地面滑行時必須保持安全間距.為保證安全距離，每個庫所pi內只允許一架航空器，該規范可描述為

定義6 約束使能.給出場面狀態禁止規范后，可給出約束使能的概念，若?t∈Fe（m），變遷t激發后滿足狀態禁止規范，則稱變遷t滿足約束使能，在標識m下約束使能變遷集記作Ce（m）.

3 基于Petri網動態滑行路徑規劃

動態路徑規劃的可行解集從預先規劃的靜態路徑集合∏s中提取.∏s由求解K最短路徑的相關理論［11］得到，并可據管制員經驗選擇c條常用滑行路徑構成.

本文借鑒“先到先服務”的思想［12］，僅為進場航空器規劃路徑，并根據規劃路徑動態調整場面其他航空器的滑行時間.

3.1 動態路徑規劃目標函數的確定

定義7 滑行臨界時刻向量.在場面活動模型∑＝（P，T，Pre，Post，m，Γ）內，某航空器ai沿由n段活動區域組成路徑π（ai）滑行.航空器ai進入活動區域pk（pk∈π（ai））時刻為EFTk（ai），離開pk段預計時刻為 PLFTk（ai），PLFTk（ai）＝EFTk（ai）＋Γ（ai，k）.離 開 pk的 實際時刻為LFTk（ai），則三元組 CTSk（ai）＝（EFTk（ai），PLFTk（ai），LFTk（ai））構成航空器ai在區域pk的臨界時刻狀態（critical－time－state）.航空器ai在路徑π（ai）各段上的時間狀態標識構成時間狀態向量［CTS1（ai），CTS2（ai），…，CTSk（ai），…，CTSn（ai）］.

定義8 關鍵事件軌跡.關鍵事件軌跡定義為二元組（λ，m）構成的序列〈Λ，M〉＝〈（λ0，m0），（λ1，m1），…，（λi，mi），…〉，其中m 為機場場面狀態標識向量，λi為場面航空器的分布從機場場面狀態標識向量mi－1變化為mi的瞬時時刻.

3.2 動態滑行路徑規劃算法

3.2.1 動態路徑規劃算法初始條件 關鍵事件軌跡反映了場面狀態變化的時刻.若能求出場面運行的完整關鍵事件軌跡〈（λ0，m0），（λ1，m1），…，（λi，mi），…（λe，me）〉，即可求出場面各航空器新的時間狀態向量及目標函數.見圖4.

圖4 動態路徑規劃算法

設當前為航空器a規劃路徑π（a），已知a進入場面時刻為TOA（a），場面上已存在的N架航空器分布向量為m0，即（λ0，m0）＝（TOA（a），m0），則初始關鍵時刻序列〈Λ，M〉＝〈（λ0，m0）〉.

此刻，場面任意航空器ai（包括a）在其滑行（規劃）路徑π（ai）第pi段滑行，離開pi預計時刻為PLFTpi（ai），場面N＋1架航空器構成初始目標序列〈P，PLFT〉＝〈（p1（a1），PLFTp1（a1）），（p2（a2），PLFTp2（a2）），…，（pN＋1（aN＋1），PLFTpN＋1（aN＋1））.

3.2.2 動態路徑規劃算法 動態路徑規劃算法是由初始條件推算場面關鍵事件軌跡、各航空器當在π（a）下的時間狀態向量及目標函數Z（π）的過程.算法的結束條件為當前規劃航空器a到達目的庫所pend（a）.其流程圖如圖4所示.

圖4中，若航空器ai在PLFTpi（ai）滿足tpi（ai）∈Ce（mk），場面活動模型狀態改變，更新相關序列及目標函數，規則如下：

1）更新關鍵事件軌跡〈Λ，M〉：

2）更新目標序列〈P，PLFT〉 PLFTpi＋1（ai）＝λk＋1＋Γ（ai，pi＋1），航空器ai更新為（pi＋1（ai），PLFTpi＋1（ai））；?PLFTpj（aj）∈ PLFT 且PLFTpj（aj）＜PLFTpi（ai），令（aj）＝λk＋1，即（pj（aj），λk＋1）.

3）更新航空器ai滑行臨界時刻向量 航空器ai離開當前段時刻和進入下一段時刻相同，即LFTpi（ai）＝EETpi＋1（ai）＝λk＋1，航空器ai離開下一段預計 時刻PLFTpi＋1（ai）＝λk＋1＋Γ（ai，pi＋1）.

4）更新目標函數Z（π） 航空器ai在pi段等待時間WTpi（ai）＝LFTpi（ai）－PLFTpi（ai），故Z（π）′＝Z（π）＋WTpi（ai）ξi，ξi為航空器ai的等待權重.

遍歷當前規劃航空器a的靜態路徑預選庫，從中找出路徑πα，使得Z（πα）最小即可.

表1 進離港航空器靜態預選路徑

4 態滑行路徑規劃研究案例

為驗證航空器動態滑行路徑規劃方法的有效性，結合場面活動模型進行計算機仿真.

設預選路徑數s＝3，對個進離港求得預選路徑集合Πs，見表1.其中：App為進近庫所；Gx為GateX.

根據航空器進離港時間的先后順序，對航空器動態行為進行仿真.利用動態路徑規劃模型，為每架航空器計算最優路徑及滑行總時間.假設每架航空器仿真5次，每次仿真結束再次加入仿真隊列，仿真結果見表2.

由表2可見，2種方法規劃的路徑均存在一定等待時間，這是依據管制規則避免與其他航空器沖突而實施等待造成的.經過動態路徑規劃，滑行時間雖略為增加，但總時間降低了，這是由于動態路徑規劃充分考慮了場面的動態變化，避開了容易發生擁擠的路段，減少了航空器等待時間，對于航班量越大的機場，其優化效果越明顯.

表2 靜態路徑和動態路徑規劃結果比較

5 結束語

本文建立了基于Petri網的機場場面活動模型，并根據ICAO－9830文件定義了場面活動控制規范.以靜態規劃路徑的結果為可行解集，研究了以全局等待時間權值最少為約束目標的動態最優規劃路徑算法.由于本文主要以單跑道機場為研究對象，未來的研究重點偏重于該算法在多跑道的大型機場的應用，并將滑行路徑規劃與沖突解脫相結合，為航空器的滑行實施精確的規劃與引導.

［1］ICAO.Advanced surface movement guidance and control systems manual［R］.ICAO－9830，2004.

［2］丁一波，靳學梅，楊 愷.淺析A－SMGCS中的自動路由規劃技術［J］.空中交通管理，2009（11）：16－18.

［3］劉長有，叢曉東.基于遺傳算法的飛機滑行路徑優化［J］.交通信息與安全，2009，27（3）：6－8.

［4］HESSELINK H H，PAUL S.Planning aircraft movements on airports with constraint satisfaction［R］.National Aerospace Laboratory，1998.

［5］MARIN A G，CODINA E.Network design：taxi planning［J］.Annals Operation Research，2008，157（1）：135－151.

［6］BAIK H，SHERTALI H D，TRANI A A.Time－dependent network assignment strategy for taxiway routing at airports［J］.Transportation Research Record，2002：70－75.

［7］RATINAM S，MONTOYA J，JUNG Y.An optimization model for reducing aircraft taxi times at the Dallas FortWorth International Airport［C］／／26th International Congress of the Aeronautical Sciences，Anchorage，2008：1－14.

［8］張 威，謝曉妤，劉 曄.基于Petri網的機場場面路徑規劃探討［J］.現代電子工程，2007，4（1）：59－61.

［9］黃圣國，孫同江，呂 兵.運輸網絡的最短有向路Petri網仿真算法［J］.南京航空航天大學學報，2002，34（2）：121－125.

［10］湯新民，王玉婷，韓松臣.基于DEDS的 A－SMGCS航空器動態滑行路徑規劃［J］.系統工程與電子技術，2010，32（12）：2669－2675.

［11］李成江.新的K最短路算法［J］.山東大學學報：理學版，2006，41（4）：40－43.

［12］王 維.機場飛行區管理與場道施工［M］.北京：人民交通出版社，2007.