基于Petri网与遗传算法的航空器滑行初始路径规划

基金项目： 国家科技支撑计划项目（2011BAH24B06）；国家自然科学基金与民航局联合基金资助项目（60879011，U1233105）

作者简介： 朱新平（1983-），男，博士，研究方向为先进机场场面运行控制，电话：13419037831，E-mail：

通讯作者： 韩松臣（1963-），男，教授，博士，研究方向为空中交通安全、空域规划管理，E-mail：

文章编号： 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.