A－SMGCS航空器動(dòng)態(tài)最優(yōu)滑行路徑規(guī)劃研究＊

王 翀 湯新民 安宏鋒

（南京航空航天大學(xué)民航學(xué)院 南京 210016）

0 引 言

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

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

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

1 機(jī)場(chǎng)場(chǎng)面結(jié)構(gòu)建模與靜態(tài)路徑規(guī)劃

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

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

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

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

圖1 機(jī)場(chǎng)場(chǎng)面活動(dòng)模型

圖2 航空器交叉和對(duì)頭兩種沖突

2 機(jī)場(chǎng)場(chǎng)面運(yùn)行控制規(guī)范

2.1 場(chǎng)面活動(dòng)優(yōu)先規(guī)范

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

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

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

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

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

2.2 場(chǎng)面活動(dòng)禁止規(guī)范

定義5 狀態(tài)禁止規(guī)范.場(chǎng)面活動(dòng)模型狀態(tài)演變過程中所禁止?fàn)顟B(tài)可描述為標(biāo)識(shí)的加權(quán)和不超過某一上限的不等式組.

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

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

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

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

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

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

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

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

3.1 動(dòng)態(tài)路徑規(guī)劃目標(biāo)函數(shù)的確定

定義7 滑行臨界時(shí)刻向量.在場(chǎng)面活動(dòng)模型∑＝（P，T，Pre，Post，m，Γ）內(nèi)，某航空器ai沿由n段活動(dòng)區(qū)域組成路徑π（ai）滑行.航空器ai進(jìn)入活動(dòng)區(qū)域pk（pk∈π（ai））時(shí)刻為EFTk（ai），離開pk段預(yù)計(jì)時(shí)刻為 PLFTk（ai），PLFTk（ai）＝EFTk（ai）＋Γ（ai，k）.離 開 pk的 實(shí)際時(shí)刻為LFTk（ai），則三元組 CTSk（ai）＝（EFTk（ai），PLFTk（ai），LFTk（ai））構(gòu)成航空器ai在區(qū)域pk的臨界時(shí)刻狀態(tài)（critical－time－state）.航空器ai在路徑π（ai）各段上的時(shí)間狀態(tài)標(biāo)識(shí)構(gòu)成時(shí)間狀態(tài)向量［CTS1（ai），CTS2（ai），…，CTSk（ai），…，CTSn（ai）］.

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

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

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

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

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

此刻，場(chǎng)面任意航空器ai（包括a）在其滑行（規(guī)劃）路徑π（ai）第pi段滑行，離開pi預(yù)計(jì)時(shí)刻為PLFTpi（ai），場(chǎng)面N＋1架航空器構(gòu)成初始目標(biāo)序列〈P，PLFT〉＝〈（p1（a1），PLFTp1（a1）），（p2（a2），PLFTp2（a2）），…，（pN＋1（aN＋1），PLFTpN＋1（aN＋1））.

3.2.2 動(dòng)態(tài)路徑規(guī)劃算法 動(dòng)態(tài)路徑規(guī)劃算法是由初始條件推算場(chǎng)面關(guān)鍵事件軌跡、各航空器當(dāng)在π（a）下的時(shí)間狀態(tài)向量及目標(biāo)函數(shù)Z（π）的過程.算法的結(jié)束條件為當(dāng)前規(guī)劃航空器a到達(dá)目的庫所pend（a）.其流程圖如圖4所示.

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

1）更新關(guān)鍵事件軌跡〈Λ，M〉：

2）更新目標(biāo)序列〈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滑行臨界時(shí)刻向量 航空器ai離開當(dāng)前段時(shí)刻和進(jìn)入下一段時(shí)刻相同，即LFTpi（ai）＝EETpi＋1（ai）＝λk＋1，航空器ai離開下一段預(yù)計(jì) 時(shí)刻PLFTpi＋1（ai）＝λk＋1＋Γ（ai，pi＋1）.

4）更新目標(biāo)函數(shù)Z（π） 航空器ai在pi段等待時(shí)間WTpi（ai）＝LFTpi（ai）－PLFTpi（ai），故Z（π）′＝Z（π）＋WTpi（ai）ξi，ξi為航空器ai的等待權(quán)重.

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

表1 進(jìn)離港航空器靜態(tài)預(yù)選路徑

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

為驗(yàn)證航空器動(dòng)態(tài)滑行路徑規(guī)劃方法的有效性，結(jié)合場(chǎng)面活動(dòng)模型進(jìn)行計(jì)算機(jī)仿真.

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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

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