基于Petri網與遺傳算法的航空器滑行初始路徑規劃

基金項目： 國家科技支撐計劃項目（2011BAH24B06）；國家自然科學基金與民航局聯合基金資助項目（60879011，U1233105）

作者簡介： 朱新平（1983-），男，博士，研究方向為先進機場場面運行控制，電話：13419037831，E-mail：zhu408@163.com

通訊作者： 韓松臣（1963-），男，教授，博士，研究方向為空中交通安全、空域規劃管理，E-mail：hansongchen@nuaa.edu.cn

文章編號： 0258-2724（2013）03-0565-09DOI： 10.3969/j.issn.0258-2724.2013.03.027

摘要：

為支持先進機場場面活動引導與控制系統（A-SMGCS，advanced surface movement guidance and control system）實施航空器滑行的精確引導，將場面分為滑行道交叉口和直線段等典型運行單元，利用改進的擴展賦時庫所Petri網，建立了場面運行模塊化模型；采用該模型進行染色體編碼，并考慮場面運行管制規則，提出了染色體合法性檢測與修復算法，以及染色體交叉和變異算法.基于首都國際機場01號跑道實際運行數據，用本文模型和算法進行了多個航班滑行初始路徑規劃，研究結果表明：與節點-路段類模型相比，本文模型能更充分地描述場面管制規則約束，可避免生成違反管制規則的路徑；本文算法的每個航班初始路徑規劃耗時小于10 s，符合A-SMGCS的要求；由于考慮了航空器滑行速度調整特征，更符合場面運行的實際情況.

關鍵詞：

空中交通；A-SMGCS；滑行路由規劃； Petri網；遺傳算法

中圖分類號： V351.11文獻標志碼： A

航空器滑行自動路由規劃可以協調進離港航班安全有序地滑行，從而減少場面擁堵并提升場面容量.在國際民航組織（International Civil Aviation Organization， ICAO）提出的先進機場場面引導與控制系統（advanced surface movement guidance and control system， A-SMGCS）中，路由規劃功能是實現航空器場面滑行精確引導的前提[1].航空器場面滑行具有并發、資源共享特性，并受多種管制規則約束. A-SMGCS路由規劃不同于傳統道路網絡中的車輛路徑規劃，文獻[2]提出了A-SMGCS三階段路由規劃策略：

（1） 初始路徑規劃，為進離港航班確定最優滑行路徑和s-1個次優滑行路徑（s值由管制員動態交互確定）；

（2） 滑行前路由指派，依據航空器開始滑行前的場面態勢，為其確定合理路由；

（3） 路由實時更新，在航空器滑行過程中實時調整路由，以避免沖突發生.

本文僅考慮第（1）階段，即初始路徑規劃問題.

Petri網廣泛用于A-SMGCS場面運行過程的建模與沖突監控[3-4]，但較少用于航空器滑行路由規劃.文獻[5]將無向交通網絡轉換為Petri網表示的有向圖，并通過Petri網仿真器求解最短有向路徑.文獻[6]將機場滑行路徑描述為有向圖，并轉換為Petri網圖求解最佳滑行路徑.文獻[2]建立了基于Petri網的場面活動模型，并通過時間窗調度來進行路由規劃.上述研究建立的Petri網模型對場面管制規則約束考慮不全面，在算法設計上未充分利用Petri網的數學特征，且通常針對某一特定機場進行分析，實用性和通用性均顯不足.另一方面，將航空器場面滑行速度假設為恒定值[7-9]，忽略了航空器在場面不同區域滑行速度的調整變化，導致所得路由結果不能支持航空器滑行的精確引導.

在文獻[2]的基礎上，本文從以下方面展開研究：

（1） 給出一種擴展賦時庫所Petri網（extended timed place Petri net， ETPPN），以準確描述場面運行管制規則約束，并提出一種模塊化、面向路由規劃的場面運行ETPPN模型建模方法；

（2） 采用遺傳算法規劃航空器初始滑行路徑，其染色體編碼采用場面ETPPN模型的變遷激發序列，且交叉和變異均僅針對模型中的變遷進行，避免了以滑行道系統拓撲結構中的交叉口或直線段為基因組成染色體，在此基礎上展開的遺傳操作保證了方法的通用性；

（3） 與文獻[7-9]中關于航空器場面滑行速度恒定的假設不同，細化了航空器加減速特性對路段占用時間的影響，使路由規劃結果的精確度更高，實用性更強.

1

航空器場面運行過程建模

1.1

面向資源的場面運行過程建模

可見，采用ETPPN模型對場面運行進行建模，可描述航空器對場面各單元的動態占用與釋放，以及航空器在各單元滑行應遵循的管制規則.場面其它典型單元運行過程的Petri網建模也可采用本節的方法.不同機場的場面交通系統具有不同構型，但基本組成單元類似且有準確的數量和明確的運行規則.因此，利用各單元對應的ETPPN模型，并采用Petri網同步合成技術[10]可實現場面運行過程建模.

1.2

航空器滑行特征分析

航空器場面滑行速度具有以下特征：

（1） 當航空器先后通過的兩路段均為直線或彎道時，無須加減速；

（2） 當航空器從彎道滑入直線段時，須啟動加速過程；

（3） 當航空器從直線段滑入彎道時，減速過程通常在進入彎道前完成.

2

基于GA的初始路徑規劃算法

2.1

面向初始路徑規劃的GA設計

遺傳算法（genetic algorithm， GA）在工程優化領域已得到廣泛應用[11]，并越來越多地應用于航空器路由優化[12-15].本文提出基于場面ETPPN模型和GA的初始路徑規劃方法，基本思路為：

（1）

采用第1節方法，建立場面活動區中各典型運行單元對應的ETPPN模型，同時將場面管制規則約束集成到Petri網元素中，最終得到場面ETPPN模型；

（2）

以場面ETPPN模型為基礎，采用合適的編碼方式對模型中所含相關元素進行染色體編碼，并設計相關遺傳操作，求解初始滑行路徑集合（包括1個最優和s-1個次優滑行路徑）.

上述思路的優勢在于，對任何一個機場的航空器初始路徑規劃，所要解決的問題只需采用第1節的模塊化建模方法，將場面交通系統映射為對應的ETPPN模型并輸入管制規則約束即可，因而保證了所給算法的實用性和通用性.

2.2

染色體編碼

染色體應滿足以下約束：

（1） 物理約束.指與航空器自身占用物理空間大小或與滑行性能相關的約束，如翼展對通過某些區域的限制等.

（2） 管制規則約束.指管制規則確定的航空器在某些路段的滑行約束，如滑行速度約束、進出某機坪必經的交叉口等.

算法2中，步驟1保證了染色體不會出現重復基因，即所規劃滑行路徑不會出現環路；步驟2保證了航空器在單元內部的滑行過程滿足航空器性能要求，例如航空器在同一交叉口滑行時不能多次轉彎；步驟3～5保證了航班按照所規劃路徑滑行時能滿足相關約束.

2.3

選擇算子與遺傳算子

2.3.1選擇算子

2.3.2

交叉算子

2.3.3

變異算子

由于采用變遷激發序列進行染色體編碼，若采取隨機改變某一基因位變遷進行變異，則極有可能產生不滿足可激發約束的解.以往采取兩種方法解決該問題：第1種方法是隨機改變染色體，當生成了不滿足約束的解時再進行改正；第2種方法是在進行變異時保證不產生不可行解[16].

3

仿真試驗

3.1

仿真試驗設計

以首都國際機場為研究對象，采集T3航站樓東側飛行區某日實際運行數據，為所有進離港航班規劃初始滑行路徑集.該部分飛行區的場面交通系統結構如圖6所示，采用北向運行模式（使用01號跑道），且假設所有離港航班均使用全跑道起飛，即從跑道等待區Q0處（圖中方框所示區域）進入跑道起飛，進港航班從快速脫離道Q5、Q6、Q7脫離的比例為0.1∶0.6∶0.3.作為對比，采用文獻[12]的方法為圖6所示飛行區建立對應的節點-路段類有向圖模型，并采用基于遺傳算法的路徑規劃方法為航班規劃滑行路徑.

文獻[12]采取的優化目標是所有航班滑行的總里程最短，將其修改為與本文算法相同的優化目標，即滑行時間較短的s條滑行路徑（設s=3）.對比的目的是：

（1） 檢驗用本文所建場面模型進行路徑規劃是否比節點-路段類模型能更好地遵循管制規則；

（2） 檢驗本文初始路徑規劃算法的效率和有效性.

計算環境CPU為Interl（R） Pentium Dual 2.2 GHz，內存為4 GB.

具體實施過程為：在基于Anylogic的場面運行仿真平臺上建立對應的場面ETPPN模型，然后解析得到該模型對應的關聯矩陣并導入MATLAB2008a中，采用Sheffield大學的遺傳算法工具箱GATBX求解滑行路徑.在求解過程中，MATLAB可直接調用Anylogic存儲的相關庫所屬性數據庫，并采用遺傳算法工具箱GATBX進行求解.文獻[12]中算法的實現直接用MATLAB的遺傳算法工具箱GATBX完成.

3.2

仿真試驗結果及分析

為了給每個航班的進離港滑行規劃s

個滑行時間較短的初始滑行路徑，需要設置合理的遺傳算法參數.但目前在遺傳算法參數設定方面缺乏通用理論，一般根據問題難易程度和染色體編碼形式，由經驗和反復試湊來設定參數值.

用上述參數為離港航班SK996（所在機位511）規劃初始滑行路徑集（包含3條路徑）.由于遺傳算法具有一定的隨機性，可進行多次試驗，每次試驗得到的最短滑行時間均為246 s，因此認為對應的滑行路徑為最短滑行路徑.

圖8為在1次隨機試驗中不同遺傳代數所得路徑集的最短滑行時間和平均滑行時間變化曲線.由圖8可以看出，每次優化均能獲得最短滑行路徑，且隨著進化代數的增加，平均滑行時間越來越接近最短滑行時間，表明算法收斂性良好.

最終為該航班確定的初始滑行路徑集如表3所示.對每條路徑進行分析可知，在優化場面資源使用的同時，滿足了各類場面運行管制規則約束.

采用文獻[12]的遺傳算法為該航班規劃初始滑行路徑集，將求出的前3條較短滑行路徑參照圖6轉化為對應的節點形式，如表4所示.

由表4可見，路徑1和路徑2分別在滑行道K5和K4上未遵循該路段的運行方向約束，這與該算法設計僅考慮避免航空器之間的滑行沖突約束但未充分考慮其它約束有關.可見，在節點-路段類模型中，模型本身對管制規則約束的描述能力有限，僅在算法實現過程中考慮各類約束，可能影響路徑規劃結果的有效性.

此外，文獻[12]中設定的航空器具有單一固定滑行速度5 m/s，路徑3的滑行時間為467 s（表4），用本文方法路徑3的滑行時間為260 s（表3），二者相差較大.可見，考慮航空器滑行速度的調整特性，可更精確地計算航空器的滑行時間.

4

結束語

提出了一種面向A-SMGCS的航空器場面滑行初始路徑規劃方法，該方法具有以下特點：

（1） 定義一種擴展賦時庫所Petri網（ETPPN），可對航空器場面滑行過程進行建模，該模型充分體現了管制規則約束；

（2） 考慮航空器場面滑行速度調整特性，使規劃結果更接近實際運行需要；

（3） 采用場面運行ETPPN模型中的變遷激發序列進行GA染色體編碼，結合場面滑行特征給出交叉與變異設計，改變以往研究中對問題空間（場面拓撲結構）的直接處理，算法的通用性更好.

在求解初始滑行路徑時僅以滑行時間最短作為優化目標，今后需要考慮更多的優化目標，例如航空器加減速次數、轉彎次數等，并與其它路徑規劃方法進行比較.

參考文獻：

[1]International Civil Aviation Organization （ICAO）. Doc.9830-AN/452， Advanced surface movement guidance and control systems （A-SMGCS） manual[S]. 2004.

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

TANG Xinmin， WANG Yuting， HAN Songchen. Aircraft dynamic taxiway routes planning for A-SMGCS based on DEDS[J]. Systems Engineering and Electronics， 2010， 32（12）： 2669-2675.

[3]朱新平，湯新民，韓松臣. 基于EHPN的A-SMGCS機場滑行道運行控制建模[J]. 交通運輸工程學報，2010，10（4）： 103-108.

ZHU Xinping， TANG Xinmin， HAN Songchen. EHPN-based modeling of airport taxiway operation control in A-SMGCS[J]. Journal of Traffic and Transportation Engineering， 2010， 10（4）： 103-108.

[4]朱新平，湯新民，韓松臣. 基于DES監控理論的滑行道對頭沖突控制策略[J]. 西南交通大學學報，2011，46（4）： 664-670.

ZHU Xinping， TANG Xinmin， HAN Songchen. Avoidance strategy for head-on conflict on taxiway based on supervisory control theory of DES[J]. Journal of Southwest Jiaotong University， 2011， 46（4）： 664-670.

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

HUANG Shengguo， SUN Tongjiang， LU Bing. Petri net simulation arithmetic of the shortest directional path in transportation net[J]. Journal of Nanjing University of Aeronautics and Astronautics， 2002， 34（2）： 121-125.

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

ZHANG Wei， XIE Xiaoyu， LIU Ye. Petri-net based airport surface routes planning[J]. Modern Electronic Engineering， 2007， 4（1）： 59-61.

[7]GARCIA J， BERLANGAA A. Optimization of airport ground operations integrating genetic and dynamic flow management algorithms[J]. AI Communications， 2005， 18（2）： 143-164.

[8]KEITH G， RICHARDS A， SHARMA S. Optimization of taxiway routing and runway scheduling[C]∥Proc. of AIAA Guidance， Navigation， and Control Conference and Exhibit. Honolulu： [s. n.]， 2008： 1-11.

[9]MARN G. Airport management： taxi planning[J]. Annals of Operations Research， 2006， 143（1）： 191-202.

[10]王化冰. 一種基于同步合成Petri網的FMS建模方法[J]. 系統工程理論與實踐，2001，21（2）： 35-42.

WANG Huabing. A Petri net synchronous synthesis method for modeling flexible manufacturing systems[J]. System Engineering： Theory and Practice， 2001， 21（2）： 35-42.

[11]GEN M， CHENG R W. Genetic algorithms and engineering optimization[M]. New York： John Wiley and Sons， 2000： 297-340.

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

LIU Changyou， CONG Xiaodong. Taxing optimization for aircraft based on genetic algorithm[J]. Transportation Information and Safety， 2009， 27（3）： 6-8.

[13]劉兆明，葛宏偉，錢鋒. 基于遺傳算法的機場調度優化算法[J]. 華東理工大學學報：自然科學版，2008，34（3）： 392-398.

LIU Zhaoming， GE Hongwei， QIAN Feng. Airport scheduling optimization algorithm based on genetic algorithm[J]. Journal of East China University of Science and Technology： Nature Science Edition， 2008， 34（3）： 392-398.

[14]GOTTELAND J， DURAND N， ALLIOT J M， et al. Aircraft ground traffic optimization[C]∥Proc. of the Genetic and Evolutionary Computation Conference. San Francisco： IEEE Press， 2001： 1-9.

[15]GOTTELAND J， DURAND N. Genetic algorithms applied to airport ground traffic optimization[C]∥Proc. of the 2003 Congress on Evolutionary Computation. Canberra： IEEE Press， 2003： 544-551.

[16]郝東，蔣昌俊. 基于Petri網與GA算法的 FMS調度優化[J]. 計算機學報，2005，28（2）： 201-208.

HAO Dong， JIANG Changjun. Petri net based modeling and GA based scheduling[J]. Chinese Journal of Computers， 2005， 28（2）： 201-208.