王 翀 湯新民 安宏鋒

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

0 引 言

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

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

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

1 機場場面結構建模與靜態(tài)路徑規(guī)劃

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

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

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

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

圖1 機場場面活動模型

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

2 機場場面運行控制規(guī)范

2.1 場面活動優(yōu)先規(guī)范

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

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

圖3 對頭路徑的Petri網(wǎng)表示

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

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

2.2 場面活動禁止規(guī)范

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

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

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

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

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

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

3 基于Petri網(wǎng)動態(tài)滑行路徑規(guī)劃

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

本文借鑒“先到先服務”的思想［12］，僅為進場航空器規(guī)劃路徑，并根據(jù)規(guī)劃路徑動態(tài)調(diào)整場面其他航空器的滑行時間.

3.1 動態(tài)路徑規(guī)劃目標函數(shù)的確定

定義7 滑行臨界時刻向量.在場面活動模型∑＝（P，T，Pre，Post，m，Γ）內(nèi)，某航空器ai沿由n段活動區(qū)域組成路徑π（ai）滑行.航空器ai進入活動區(qū)域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在區(qū)域pk的臨界時刻狀態(tài)（critical－time－state）.航空器ai在路徑π（ai）各段上的時間狀態(tài)標識構成時間狀態(tài)向量［CTS1（ai），CTS2（ai），…，CTSk（ai），…，CTSn（ai）］.

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

3.2 動態(tài)滑行路徑規(guī)劃算法

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

圖4 動態(tài)路徑規(guī)劃算法

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

此刻，場面任意航空器ai（包括a）在其滑行（規(guī)劃）路徑π（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 動態(tài)路徑規(guī)劃算法 動態(tài)路徑規(guī)劃算法是由初始條件推算場面關鍵事件軌跡、各航空器當在π（a）下的時間狀態(tài)向量及目標函數(shù)Z（π）的過程.算法的結束條件為當前規(guī)劃航空器a到達目的庫所pend（a）.其流程圖如圖4所示.

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

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）更新目標函數(shù)Z（π） 航空器ai在pi段等待時間WTpi（ai）＝LFTpi（ai）－PLFTpi（ai），故Z（π）′＝Z（π）＋WTpi（ai）ξi，ξi為航空器ai的等待權重.

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

表1 進離港航空器靜態(tài)預選路徑

4 態(tài)滑行路徑規(guī)劃研究案例

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

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

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

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

表2 靜態(tài)路徑和動態(tài)路徑規(guī)劃結果比較

5 結束語

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

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

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

［3］劉長有，叢曉東.基于遺傳算法的飛機滑行路徑優(yōu)化［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網(wǎng)的機場場面路徑規(guī)劃探討［J］.現(xiàn)代電子工程，2007，4（1）：59－61.

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

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

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

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