基于Petri網(wǎng)與遺傳算法的航空器滑行初始路徑規(guī)劃

基金項(xiàng)目： 國家科技支撐計(jì)劃項(xiàng)目（2011BAH24B06）；國家自然科學(xué)基金與民航局聯(lián)合基金資助項(xiàng)目（60879011，U1233105）

作者簡介： 朱新平（1983-），男，博士，研究方向?yàn)橄冗M(jìn)機(jī)場場面運(yùn)行控制，電話：13419037831，E-mail：zhu408@163.com

通訊作者： 韓松臣（1963-），男，教授，博士，研究方向?yàn)榭罩薪煌ò踩⒖沼蛞?guī)劃管理，E-mail：hansongchen@nuaa.edu.cn

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

摘要：

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

關(guān)鍵詞：

空中交通；A-SMGCS；滑行路由規(guī)劃； Petri網(wǎng)；遺傳算法

中圖分類號(hào)： V351.11文獻(xiàn)標(biāo)志碼： A

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

（1） 初始路徑規(guī)劃，為進(jìn)離港航班確定最優(yōu)滑行路徑和s-1個(gè)次優(yōu)滑行路徑（s值由管制員動(dòng)態(tài)交互確定）；

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

（3） 路由實(shí)時(shí)更新，在航空器滑行過程中實(shí)時(shí)調(diào)整路由，以避免沖突發(fā)生.

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

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

在文獻(xiàn)[2]的基礎(chǔ)上，本文從以下方面展開研究：

（1） 給出一種擴(kuò)展賦時(shí)庫所Petri網(wǎng)（extended timed place Petri net， ETPPN），以準(zhǔn)確描述場面運(yùn)行管制規(guī)則約束，并提出一種模塊化、面向路由規(guī)劃的場面運(yùn)行ETPPN模型建模方法；

（2） 采用遺傳算法規(guī)劃航空器初始滑行路徑，其染色體編碼采用場面ETPPN模型的變遷激發(fā)序列，且交叉和變異均僅針對(duì)模型中的變遷進(jìn)行，避免了以滑行道系統(tǒng)拓?fù)浣Y(jié)構(gòu)中的交叉口或直線段為基因組成染色體，在此基礎(chǔ)上展開的遺傳操作保證了方法的通用性；

（3） 與文獻(xiàn)[7-9]中關(guān)于航空器場面滑行速度恒定的假設(shè)不同，細(xì)化了航空器加減速特性對(duì)路段占用時(shí)間的影響，使路由規(guī)劃結(jié)果的精確度更高，實(shí)用性更強(qiáng).

1

航空器場面運(yùn)行過程建模

1.1

面向資源的場面運(yùn)行過程建模

可見，采用ETPPN模型對(duì)場面運(yùn)行進(jìn)行建模，可描述航空器對(duì)場面各單元的動(dòng)態(tài)占用與釋放，以及航空器在各單元滑行應(yīng)遵循的管制規(guī)則.場面其它典型單元運(yùn)行過程的Petri網(wǎng)建模也可采用本節(jié)的方法.不同機(jī)場的場面交通系統(tǒng)具有不同構(gòu)型，但基本組成單元類似且有準(zhǔn)確的數(shù)量和明確的運(yùn)行規(guī)則.因此，利用各單元對(duì)應(yīng)的ETPPN模型，并采用Petri網(wǎng)同步合成技術(shù)[10]可實(shí)現(xiàn)場面運(yùn)行過程建模.

1.2

航空器滑行特征分析

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

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

（2） 當(dāng)航空器從彎道滑入直線段時(shí)，須啟動(dòng)加速過程；

（3） 當(dāng)航空器從直線段滑入彎道時(shí)，減速過程通常在進(jìn)入彎道前完成.

2

基于GA的初始路徑規(guī)劃算法

2.1

面向初始路徑規(guī)劃的GA設(shè)計(jì)

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

（1）

采用第1節(jié)方法，建立場面活動(dòng)區(qū)中各典型運(yùn)行單元對(duì)應(yīng)的ETPPN模型，同時(shí)將場面管制規(guī)則約束集成到Petri網(wǎng)元素中，最終得到場面ETPPN模型；

（2）

以場面ETPPN模型為基礎(chǔ)，采用合適的編碼方式對(duì)模型中所含相關(guān)元素進(jìn)行染色體編碼，并設(shè)計(jì)相關(guān)遺傳操作，求解初始滑行路徑集合（包括1個(gè)最優(yōu)和s-1個(gè)次優(yōu)滑行路徑）.

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

2.2

染色體編碼

染色體應(yīng)滿足以下約束：

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

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

算法2中，步驟1保證了染色體不會(huì)出現(xiàn)重復(fù)基因，即所規(guī)劃滑行路徑不會(huì)出現(xiàn)環(huán)路；步驟2保證了航空器在單元內(nèi)部的滑行過程滿足航空器性能要求，例如航空器在同一交叉口滑行時(shí)不能多次轉(zhuǎn)彎；步驟3～5保證了航班按照所規(guī)劃路徑滑行時(shí)能滿足相關(guān)約束.

2.3

選擇算子與遺傳算子

2.3.1選擇算子

2.3.2

交叉算子

2.3.3

變異算子

由于采用變遷激發(fā)序列進(jìn)行染色體編碼，若采取隨機(jī)改變某一基因位變遷進(jìn)行變異，則極有可能產(chǎn)生不滿足可激發(fā)約束的解.以往采取兩種方法解決該問題：第1種方法是隨機(jī)改變?nèi)旧w，當(dāng)生成了不滿足約束的解時(shí)再進(jìn)行改正；第2種方法是在進(jìn)行變異時(shí)保證不產(chǎn)生不可行解[16].

3

仿真試驗(yàn)

3.1

仿真試驗(yàn)設(shè)計(jì)

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

文獻(xiàn)[12]采取的優(yōu)化目標(biāo)是所有航班滑行的總里程最短，將其修改為與本文算法相同的優(yōu)化目標(biāo)，即滑行時(shí)間較短的s條滑行路徑（設(shè)s=3）.對(duì)比的目的是：

（1） 檢驗(yàn)用本文所建場面模型進(jìn)行路徑規(guī)劃是否比節(jié)點(diǎn)-路段類模型能更好地遵循管制規(guī)則；

（2） 檢驗(yàn)本文初始路徑規(guī)劃算法的效率和有效性.

計(jì)算環(huán)境CPU為Interl（R） Pentium Dual 2.2 GHz，內(nèi)存為4 GB.

具體實(shí)施過程為：在基于Anylogic的場面運(yùn)行仿真平臺(tái)上建立對(duì)應(yīng)的場面ETPPN模型，然后解析得到該模型對(duì)應(yīng)的關(guān)聯(lián)矩陣并導(dǎo)入MATLAB2008a中，采用Sheffield大學(xué)的遺傳算法工具箱GATBX求解滑行路徑.在求解過程中，MATLAB可直接調(diào)用Anylogic存儲(chǔ)的相關(guān)庫所屬性數(shù)據(jù)庫，并采用遺傳算法工具箱GATBX進(jìn)行求解.文獻(xiàn)[12]中算法的實(shí)現(xiàn)直接用MATLAB的遺傳算法工具箱GATBX完成.

3.2

仿真試驗(yàn)結(jié)果及分析

為了給每個(gè)航班的進(jìn)離港滑行規(guī)劃s

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

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

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

最終為該航班確定的初始滑行路徑集如表3所示.對(duì)每條路徑進(jìn)行分析可知，在優(yōu)化場面資源使用的同時(shí)，滿足了各類場面運(yùn)行管制規(guī)則約束.

采用文獻(xiàn)[12]的遺傳算法為該航班規(guī)劃初始滑行路徑集，將求出的前3條較短滑行路徑參照圖6轉(zhuǎn)化為對(duì)應(yīng)的節(jié)點(diǎn)形式，如表4所示.

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

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

4

結(jié)束語

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

（1） 定義一種擴(kuò)展賦時(shí)庫所Petri網(wǎng)（ETPPN），可對(duì)航空器場面滑行過程進(jìn)行建模，該模型充分體現(xiàn)了管制規(guī)則約束；

（2） 考慮航空器場面滑行速度調(diào)整特性，使規(guī)劃結(jié)果更接近實(shí)際運(yùn)行需要；

（3） 采用場面運(yùn)行ETPPN模型中的變遷激發(fā)序列進(jìn)行GA染色體編碼，結(jié)合場面滑行特征給出交叉與變異設(shè)計(jì)，改變以往研究中對(duì)問題空間（場面拓?fù)浣Y(jié)構(gòu)）的直接處理，算法的通用性更好.

在求解初始滑行路徑時(shí)僅以滑行時(shí)間最短作為優(yōu)化目標(biāo)，今后需要考慮更多的優(yōu)化目標(biāo)，例如航空器加減速次數(shù)、轉(zhuǎn)彎次數(shù)等，并與其它路徑規(guī)劃方法進(jìn)行比較.

參考文獻(xiàn)：

[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航空器動(dòng)態(tài)滑行路徑規(guī)劃研究[J]. 系統(tǒng)工程與電子技術(shù)，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ī)場滑行道運(yùn)行控制建模[J]. 交通運(yùn)輸工程學(xué)報(bào)，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監(jiān)控理論的滑行道對(duì)頭沖突控制策略[J]. 西南交通大學(xué)學(xué)報(bào)，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]黃圣國，孫同江，呂兵. 運(yùn)輸網(wǎng)絡(luò)的最短有向路Petri網(wǎng)仿真算法[J]. 南京航空航天大學(xué)學(xué)報(bào)，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網(wǎng)的機(jī)場場面路徑規(guī)劃探討[J]. 現(xiàn)代電子工程，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網(wǎng)的FMS建模方法[J]. 系統(tǒng)工程理論與實(shí)踐，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ī)滑行路徑優(yōu)化[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ī)場調(diào)度優(yōu)化算法[J]. 華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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網(wǎng)與GA算法的 FMS調(diào)度優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào)，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.