基于粒子群算法的航空器滑行路径优化研究

冯广洪

摘 要：航空器滑行路径的优化可以提高繁忙机场场面的运行效率，减小航空器的滑行成本。考虑实际情况，做出了相应的假设，以机场航空器地面滑行总时间为优化目标，考虑航空器的优先级和冲突节点避让等问题，建立了航空器地面滑行路径优化的0-1整数规划模型，并采用了粒子群算法进行求解。通过实例求解仿真，实验结果表明算法可以实现航空器滑行路径优化问题，得到的路线具有可行性，也验证了模型的可用性，可为复杂的路径规划问题提供有效的求解方法。

关键词：航空运输;地面滑行路径;路径优化;粒子群优化算法

滑行道的合理规划与使用，影响着机场场面运行的安全和效率。随着民航业的大力发展，各大型机场的航班数量也不断上升，场面运行日益复杂，通过为航空器的滑行路径进行优化管理，提高机场场面运行的效率成为热门研究方向。

对于航空器的地面滑行路径的优化，国内外学者从模型建立、求解方法等不同方面都已有了大量的研究。2003年，Visser[1]等建立了整数规划模型来研究滑行路径优化的问题，但由于研究的假设理想化，后续不断有更符合现实运行的研究。2005年，Garacia[2]等分别用遗传算法和最小费用最大流法对滑行路径优化问题进行求解，并做了相应的对比;2012年，李楠[3]等、谷润平等[4]针对滑行冲突问题，考虑冲突避让等规则，分别使用了A*算法、Dijkstra 算法和代价函数的 D*算法进行优化;

针对现有模型对航空器滑行系统刻画不足的特点，提出0-1整数规划模型，考虑航空器在滑行时所必须满足的航班时刻、机场地面的实时动态、冲突解脱、特殊滑行道的限制等的现实问题的约束，更精确地描绘了航空器的滑行过程。针对传统算法计算模型过大，精确度不高的问题，提出应用粒子群算法对模型进行求解，以达到减少航空器地面滑行时间，提高航班运行效率的目标。

1 符号说明及模型建立

定义K=1，2，…，n为所有航空器的集合;滑行道布局为以节点和边构成的有向图G=（P，R），其中P为滑行道交叉点集（共n个），R为连接交叉点的一段滑行道。i、j均为滑行道的连接节点，i∈P，j∈P，i≠j;

式（1）为目标函数，表示所有航空器的地面滑行时间最短，其中地面滑行时间为航空器的实际滑行时间加上停机等待时间;式（2）表示优先级更低的航空器在节点遇到冲突前需要进行一次等待，即使其可能在时间窗内先到达节点;式（3）为冲突探测因子，若两航空器到达节点的时间差大于要求保持的安全时间间隔，则不需要等待;式（4）为优先级因子，优先级高的不需要等待;式（5）为航空器到达节点的时刻;式（6）表明航空器的开始滑行时间不可以早于实际着陆时间;式（7）表示了航空器不可早于计划起飞时间的前15分钟;式（8）表示不允许在同一节滑行道产生对头冲突;式（9）表示在同一节滑行道不允许超越前机;式（10）、（11）分别为滑行的起点、终点约束，表示k航空器的起点s、终点e为必选点。

2 基于粒子算法的模型求解算法

本文采用粒子群算法进行求解，粒子群算法（PSO，Particle Swarm Optimization）是一种智能优化算法，源于研究鸟类捕食问题。和遗传算法的染色体信息共享的传播机制不一样，粒子群算法是粒子间的单向的信息传递，收敛速度快，结果理想且可以解决一些遗传算法中容易产生的问题。粒子群算法在函数优化方面易于实现，已得到了广泛的使用。

因此本文在目标函数和约束条件的基础上，PSO算法以粒子的形式，在可行解空间先生成初始解。每个粒子都可能是一个最优解，以适应度函数来评判粒子值的优劣。通过判定个体极值和整体极值来不断迭代计算，更新粒子所处的位置，逐步搜索到全局较优的区域，获得问题的最优解[5～6]。

算法中，所有航空器的可行滑行轨迹的解集，都是一个粒子。设有n个粒子，其中k粒子所处的位置为Xk=（xk1，xk2，…，xkn），其速度为Vk=（vk1，vk2.…，vkn）。粒子k搜寻到了其最佳的位置pbestk=（pbestk1，pbestk2，…，pbestkn），整体种群最佳的位置gbest=（gbest1，gbest2，…，gbestn）。经过迭代，k粒子更新其速度为Vmk=ωVm-1k+c1rand（）（pbestk-Xm-1k）+c2Rand（）（gbestk-Xkm-1）位置为：Xmk=Xm-1kn+Vm-1k。其中，m表示粒子从第m-1次运动到下一次的过程;ω是用来调节搜索范围的惯性权重;c1和c2是源于我们对这两部分分量的把握而加的系数;rand（）和Rand（）是出于对共享和认知提供的随机系数，均在[0，1]区间内分布。

算法的具体步骤如下：

（1）种群粒子初始化：粒子群体规模为n，在模型的可行解集空间的基础上，初始化粒子群体，每个粒子携带的其随机位置和速度的信息。

（2）计算适应度值：根据目标函数，计算每个粒子的适应度函数值。

（3）计算个体极值pbest：将每个粒子当前所处的位置对应的适应度值同粒子历史最佳位置对应的适应度值相比，若大于，则将当前位置更新为最佳位置pbest。

（4）计算全局极值gbest：同理，将粒子当前所处的位置对应的适应度值同群体的历史最佳位置对应的适应度值相比，若大于，则将当前位置更新为最佳位置gbest。

（5）更新粒子位置和速度：按照前述公式更新粒子所处的位置与速度。

（6）重复迭代直至结束：回到（2），重复步骤迭代计算，直到达到最佳的迭代数量或者最优适应度值增量小于一定的阈值后，结束迭代，输出所得结果。

3 算例分析

选取国内某国际机场，机场有三条平行跑道。航站楼东边为两条近距平行跑道。西北一条跑道与东边两条的运行关系为独立平行运行，相互间不影响。选取机场的东机坪作为研究对象，进行优化计算。机场的东机坪一条跑道的编号为02L/20R，用于起飞;另一条跑道为02R/20L，用于着陆。航空器的平均滑行速度为15m/s，滑行安全間隔为200m。

使用MATLAB 2017b，在Win10环境中运行算法程序。设置初始粒子数为500，c1=1.5，c2=1.8，设置的最大迭代数量为2000，惯性权重从0.8～0.4逐步线性递减。加入了参数终止阈值1e-25和终止次数500，即，当连续的500次迭代的结果都小于此阈值时，终止算法。

图2为目标函数值随迭代进行下的变化情况。图中可以看出，在经过187次迭代后，结果趋于收敛，收敛至约为52.19min。之后的500次迭代，結果的变化依然很小，则提前终止了迭代，输出结果。

根据计算结果显示，机场的3～9和13～19号结点为主要的冲突点，冲突类型主要为进场-离场航空器交叉冲突，进场的航空器提前等待避让离场航空器的滑行。计算得全局最优的方差为0.00113，属于较理想的结果。说明利用粒子群算法可以解决在复杂的环境中的路径规划搜寻最优解的问题，结果可靠。

4 结语

本文以机场所有航空器在地面滑行时间最短为优化目标，考虑航空器的冲突避让问题和航空器优先级等限制条件，建立了航空器滑行路径优化模型。采用粒子群算法进行求解，实验结果表明，粒子群算法在实现路径规划问题求解中存在有效的效果，计算精度高，实验结果贴近实际。为了便于建模，文章对于着陆的航空器滑行至机位需要穿越起飞跑道而可能增加的等待时间，文章没有考虑;算法在初始粒子群的给定中也是按照随机的分配，实验容易陷入局部最优而导致结果偏差大，后续还可在此问题上继续深入研究。

参考文献：

[1]VISSER H，ROLING P.Optimal airport surface traffic planning using mixed integer linear programming.Proc.of AIAAs 3rd Annual Aviation Technology，Integration，and Operations（ATIO）Technology conference.Denver，CO，2003：17-19.

[2]GARCIA，J，BER;ANGA A，MOLINA JM，et al.Planning techniques for airport ground operations[C].Proc.of the 2002 Digital Avionics Systems Conference.IEEE Press，2002：1：1D5-1-1D5-12.

[3]李楠，赵擎，徐肖豪.基A～*算法的机场滑行路径优化研究[J].计算机仿真，2012，29（07）：88-92.

[4]谷润平，崔朋，唐建勋，等.基于D*算法的场面滑行动态规划研究[J].科学技术与工程，2015，15（1）：315-319.

[5]高明瑶，石红国.基于改进PSO算法的轨道交通接运公交线路优化问题[J].交通运输工程与信息学报，2019，17（04）：49-54.

[6]滕靖，林琳，陈童.纯电动公交时刻表和车辆排班计划整体优化[J].同济大学学报（自然科学版），2019，47（12）：1748-1755.