基于协同学习型差分进化算法的机场停机位分配研究

基于协同学习型差分进化算法的机场停机位分配研究

张思彬 王翌琦 赵梓祎

（沈阳航空航天大学，辽宁 沈阳 110136）

摘  要：停机位作为机场中的重要资源，是实现航班快速安全停靠，提高整个机场系统容量和服务效率的一个关键因素。但随着市场经济的快速发展，停机位分配问题呈现出高维、多目标、多约束等复杂特征，传统的差分进化算法框架和理论还不完善，对机场停机位资源不能最大化利用，因此针对差分进化算法存在的问题，引入协同学习型差分进化算法，开展基于协同学习型差分进化算法的机场停机位分配研究。

关键词：差分进化算法，学习协同，停机位分配

0引言

民航运输是交通运输网络中的重要组成部分。“十三五”期间，全行业完成运输总周转量1293亿吨公里、旅客运输量6.6亿人次、货邮运输量753 万吨，年均分别增长11%、10.7%和4.6%[1]。预计到2025年，民航全行业运输总周转量达到 1750亿吨公里。民航运输量的增长对民航产业链中各个基础环节都提出了更高的要求。停机位作为重要的地面服务资源对保障民航正常，安全和高效运行发挥着重要作用。

停机位资源紧张与需求增长的矛盾，已经成为阻碍民航业发展亟待破解的难题。目前解决停机位资源不足的方式主要有两种。一种是通过增改扩建机场的方式增加停机位数量。《关于促进通用航空业发展的指导意见》提出民航业发展的重要任务之一是加快通用机场建设[2]。但机场的建设需要投入大量的人力和物力，见效速度慢[3]。2011到2019年的全国民航运输机场的航班起降架次如图1所示，截至 2020 年底，我国境内运输机场总数 241个[4]，比上年底净增3个。由此可以看出我国民航基础设施的发展是相对缓慢的。另一种解决停机位不足的方式是对现有的停机位进行科学合理的分配，提高停机位的利用效率。这种方式见效快，成本低。因此得到了工业界和学界的广泛关注。

图1. 2011—2019年全国民航运输机场的航班起降架次

目前，停机位的分配方案主要以人工分配为主，算法分配为辅。随着航班数量的快速增长和机场运营环境的复杂化，依靠传统的优化算法进行分配是远远不够的。因此对停机位分配问题（Gate Assignment Problem, GAP）展开研究，建立符合实际的数学模型，并设计时间复杂度低、稳健型强的有效算法进行分配对促进民航业的发展具有十分重要的意义[5-7]。

综上所述，当前对机场停机位的分配问题进一步优化研究具有极其重要的意义，需要通过不断计优化更新，设计出更加智能，更加高性能的算法去解决停机位的分配问题，以便得到最优的分配方案，从而解决停机位资源不足的问题，保证机场安全，高效地运行。

1研究内容

1.1停机位分配按阶段划分为基于计划阶段的预分配和基于运行阶段的再分配。

在满足基本安全约束的前提下提出优化分配约束，研究建立多目标优化的停机位分配模型。在航班计划运行阶段，主要研究基于机场停机位运行效率、航空公司运营成本和乘客乘机体验的多方利益均衡性的停机位分配模型。选择乘客在机场的通行距离、飞机的滑行成本和远机位航班数量最小为目标函数开展研究，其中对影响航班停机位方案分配的航线和机型属性进行分析、设置优先级表并量化。在航班实际运行阶段，主要研究基于对原方案扰动最小的多目标优化停机位分配，在考虑停机位运行安全和服务质量的同时以航班扰动距离、乘客扰动距离和调整航班数量最小为优化目标。

1.2研究改进的基于差分进化算法的机场停机位分配模型。

基于传统的差分进化算法无法很好地适应机场停机位与航班之间分配的复杂问题，因此，引入协同思想求解优化问题，其示意图如图2所示。对协同差分进化算法进行研究和改进，算法流程图如图3所示。在此基础上，提出基于协同学习型差分进化算法的机场停机位分配模型进行优化，通过探索提高算法求解效率的方法，使其具有更好的全局搜索能力和更好的稳健型，从而建立符合实际的数学模型，并设计时间复杂度低、稳健型强的有效算法进行停机位分配，从而有效提高停机位分配的效率。

图2.协同进化示意图

图3. 协同学习型差分进化算法流程

2相关理论研究

2.1差分进化算法

差分进化算法(Differential Evolution Algorithm，DE)是一种高效的全局优化算法。它也是基于群体的启发式搜索算法，群中的每个个体对应一个解向量。差分进化算法的进化流程则与遗传算法非常类似，都包括变异、杂交和选择操作，但这些操作的具体定义与遗传算法有所不同。DE算法通过采用浮点矢量进行编码生成种群个体[8]。在DE算法寻优的过程中，首先，从父代个体间选择两个个体进行向量做差生成差分矢量；其次，选择另外一个个体与差分矢量求和生成实验个体；然后，对父代个体与相应的实验个体进行交叉操作，生成新的子代个体；最后在父代个体和子代个体之间进行选择操作，将符合要求的个体保存到下一代群体中去[9]。

2.2多目标优化

多目标优化的概念是在某个情景中在需要达到多个目标时，由于容易存在目标间的内在冲突，一个目标的优化是以其他目标劣化为代价，因此很难出现唯一最优解，取而代之的是在他们中间做出协调和折衷处理，使总体的目标尽可能的达到最优。

3关键技术点

（1）描述机场场面资源的构成，在分析当下民航行业现状的基础上重点关注停机位分配涉及的公平性问题，结合机场运行规章和不同运行阶段的需求对影响航班停机位分配的各项因素进行分析并设置相关约束条件，构建多目标优化的停机位预分配和再分配模型。

（2）针对计划阶段的停机位预分配问题，以航班运行多方利益公平性为目的构建停机位分配模型。在保障机场运行安全的前提下，同时以最小化乘客的通行距离、航班的滑行成本和远机位航班的数量为目标，并加入航班优先级的量化考虑同时对多个优化目标进行求解；针对实际运行阶段的停机位再分配问题，以场面扰动最小为原则构建停机位再分配模型。为避免航班临时调整给地面保障部门带来额外的工作负担过大，除了以航班扰动距离和调整航班数量最小为目标构建分配模型之外，引入乘客的考虑，尽量减少因航班调整导致的乘客上下机的步行距离变远。

（3）传统的差分进化算法不能较好的平衡种群收敛速度与种群多样性之间的关系，不利于产生新个体和优势个体。协同学习型差分进化算法的核心之一为精英种群映射策略，其策略高效的利用几个搜索种群的进化信息，及时的进行种群之间的信息交流，从而远离局部最值邻域，避免不必要的搜寻，加速收敛。

4结语

随着时代的发展，高效分配停机位，提高资源利用率迫在眉睫，协同学习型差分进化算法该算法结构简单，且进化能力较强，其模型的建立可以解决停机位的分配问题，以便得到最优的分配方案，从而解决停机位资源不足的问题，保证机场安全，高效地运行。

参考文献：

[1]张强.云计算环境下中小企业信息化建设发展研究[D].安徽大学,2014.

[2]《关于促进通用航空业发展的指导意见》[J].台声,2016(11):20.

[3]刘博勋.航空煤油输油管道腐蚀因素分析及应对措施[J].化工设计通讯,2020,46(01):194-206.

[4]朱荣生.我国民用机场投融资管理优化策略研究[J].民航管理，2019 (05):13-15.

[5]吴晓东,李瑞瑞,金楚欣等. 基于渐进元启发式搜索的快速机位分配算法[C]//中国自动化学会.2021中国自动化大会论文集,2021: 6.DOI:10.26914 /c.cnkihy.2021.053594.

[6]高阳.基于多目标优化的停机位调度方法研究[D].南京航空航天大学,2020.DOI:10.27239/d.cnki.gnhhu.2019.001615.

[7]王剑辉,刘继琳.基于差分进化算法的机位分配优化研究[J].计算机仿真,2023,40(03):52-57.

[8]凌海风，郑宇军，萧毅鸿著·装备保障智能优化决策方法与应用：国防工业出版社，2015.05

[9]余胜威编·MATLAB优化算法案例分析与应用 进阶篇：清华大学出版社，2015.06