基于AGA的多目标停机位优化分配

王晨曦，黄 辰

(沈阳航空航天大学 民用航空学院，沈阳 110136)

随着国民经济的快速发展和人民生活水平的提高，航空运输业在我国的交通运输业中占据的比重也越来越大，民航逐渐成为人们出行的首选。但是机场的基础设施建设与不断增多的民航运输需求量几乎不成正比，因此造成机场服务设施短缺，尤其是机场的停机位资源已经不堪重负。停机位作为机场的重要资源，是实现航班快速安全停靠、保证航班之间有效连接、提高整个机场服务效率和整个机场系统容量的一个重要因素。

针对机场停机位分配的问题，国内外的学者已经进行了深入的研究，并且取得了一些研究成果。Deng等[1]设计了一种基于生态协同进化策略和增强粒子群优化的改进量子进化算法，将不同时间段的航班分配到了合适的停机位上。王丹琴[2]将改进的量子进化算法应用到了停机位分配中，目标函数为旅客步行距离最短、停机位使用最充分和空闲时间最均衡。李苹苹等[3]将聚类与GA算法结合，建立以冲突调整率、航班靠桥率和机位预分配的鲁棒性的多目标优化模型，并且对目标函数采用线性加权法来设置各个目标的权重。李博[4]在模型中采用了一种基于遗传算法和蚁群优化算法相结合的两阶段算法。孙萌[5]提出了自适应协同进化蚁群优化算法，建立以机场和航空公司效益最大化以及旅客最满意的停机位分配优化模型。刘继琳等[6]以停机位占有数量最小建立数学模型，并用遗传算法进行求解。孙淑光等[7]结合遗传与禁忌搜索算法两者的优点，建立以最小空闲时间的平方和最大机位使用效率的数学模型。李亚玲等[8]提出一种动态、灵活分配停机位的禁忌搜索算法，以停机位利用率最大化以及旅客行走距离最小化为目标。陈前等[9]在合理分配停机位空闲时间的基础上，建立了避免冲突的停机位分配模型，用遗传算法进行模型的求解。王春晓[10]基于PTVACO构建以旅客步行最短、航班占有率最大以及停机位空闲时间最均衡的多目标优化模型，并且采用加权法进行了无量化处理。Cheng[11]提出满足动态和静态指派的方法。Ding等[12]考虑过度约束停机位的条件。Nikulin等[13]将参考计划的绝对偏差引入到模型中。Wang等[14]将航班分类后以最小化所有延误航班再指派导致的干扰设置为目标研究停机位分配问题。Dormdorf等[15]基于启发式算法进行求解停机位分配问题，大大提高了效率。Liu等[16]应用序贯博弈以及混合集合规划的方法对模型求解停机位分配问题，节省了时间。闫萍等[17]以最小化航班停机位分配的扰动性为优化目标，建立停机位动态再分配混合整数规划模型。

综上，国内外学者运用多种方法对停机位分配问题进行研究，优化的目标主要是旅客行走距离最短、机场资源利用最大化、延误等待时间最小化等。上述研究的约束条件中，某些软约束会被当作硬约束来进行建模，从而会存在飞机分配不到停机位的情况发生。同时，采用进化算法在求解停机位优化问题时仍存在收敛速度慢、陷入局部最优等问题。因此，本文首先将最小化油耗和最大化靠桥率作为优化目标，建立停机位分配的多目标优化数学模型，综合两个目标对停机位优化分配产生的影响。其次，引入一种适合全局搜索的自适应遗传算法，使用分段阶梯函数来优化交叉、变异算子，并且对适应度函数进行动态线性标定，确保在迭代初期，种群中每一个个体都有寻优的机会，从而提高算法的能力。最后，通过仿真结果验证所提出的模型和算法能够得到合理有效的停机位分配方案。

1 多目标停机位分配模型

1.1 问题假设

停机位分配涉及到的影响因素较多，为方便计算机仿真，作出如下假设：

(1) 假设信息完整：所有要研究的航班机位信息齐全，然后按照这些信息来安排航班，分配停机位；

(2) 假设时间段有限：由于停机位分配是一个实时动态的情况，相邻的两航班之间的状态会相互影响，如果不设定时间段很难求出最优的解决方案。因此，假设只分配一个时间段内的飞机，就可以求出最优解；

(3) 假设机场停机位容量够用：在研究的航班数和时间范围内，机场机位足够所有飞机停靠，即不会出现机场超负荷的状况。

1.2 目标函数

首先给出构造模型所需要的符号、参数和变量的含义，如表1所示。

表1 问题参数与决策变量

飞机在起飞和着陆滑行过程中，会产生大量的滑行油耗，航空公司为了提高其效益希望减少这部分的消耗，飞机滑行平均油耗的目标函数为

(1)

此外，从资源利用方面来考虑，最大化靠桥率也就是最小化机位资源浪费。基于航班靠桥率构建的目标函数为

(2)

综上两个单目标函数，用线性加权法对每一个子目标函数Fi(x)(i=1,2)赋值不同的权重wi(x)(i=1,2)，wi(x)的数值大小代表函数Fi(x)的重要程度。油耗量和靠桥率具有不同的量纲，因此不能简单地设置权重因子来得到最终的多目标函数，需要对效用函数归一化处理后才能进行计算。处理后的函数为

(3)

φi=max{|Fi(x)|}

(4)

其中:φi是规范化修正值，它起到将不同量纲的目标进行归一化处理的作用，使得不同的量纲的函数可以放到一个函数式子进行求解。

将式(1)、(2)同式(3)联立，便可以得到最终的多目标停机位分配研究的总函数

(5)

目标函数中的第一项为飞机滑行的平均油耗，第二项为飞机的最大化靠桥率。

1.3 约束条件

(1)在某一个时间范围内，一个停机位只能被一个航班占用。

(6)

(2)当航班i停靠在停机位k上时，yik=1，否则yik=0。

yik∈{0,1}∀i∈N,k∈M

(7)

(3)判断两个航班是否连续使用同一个停机位。其中sijk是一个0-1决策变量，当第j个航班在第i个航班离开停机位k之后进入停机位k，则sijk=1，否则为0。

sijk∈{0,1} ∀i,j∈N,k∈M

(8)

(9)

(10)

(4)每一个航班进入停机位之前，最多有且只有一个相邻的前序航班，航班离开停机位之后，最多有且只有一个后继航班。

(11)

(12)

(5)两个进港的航班不能同一时间都分配给同一个停机位。

sijk+sjik≤1 ∀i,j∈N,∀k∈M,i≠j

(13)

(6)飞机的进港时刻一定小于它的离港时刻。

(14)

2 自适应遗传算法

2.1 机位分配编码

在解决停机位分配的实际问题上，因为航班的数量过多，如果使用二进制编码，编码过程较为复杂，所以采用整数编码形式。假设有8个航班，4个停机位，每个进港的航班都已经按照预计的进港时间先后顺序进行排列，排列的序号即为航班的编码，停机位也根据停机位编号的大小顺序进行排序，如图1所示。

图1 航班所停靠的停机位整数编码形式

2.2 动态线性标定适应度函数

适应度函数的作用就是区分出个体的好坏，是选择过程中的参考依据。本研究的目标为求解函数最小值，可以将多目标分配停机位分配的总函数Q取倒数转换为遗传算法中的适应度函数

(15)

计算出个体之间的适应度函数值大小有可能相近，导致算法的选择功能被弱化。对上述公式进行动态线性标定，确保在开始迭代时，种群中每一个个体都有寻优机会。随着迭代次数的增加，优秀的个体就会被保存下来，且计算不占用时间。适应度函数公式如下

(16)

(17)

2.3 选择算子

从已产生的历史群体中以特定的概率选择出优良个体组建一个新的种群继续繁衍下去，个体是否被选择取决于其适应度值大小，适应度值越高，其被选择去组建新种群的概率也越高。常见的选择算子的方法有轮盘赌选择法、锦标赛法、排序选择法等。本文选择轮盘赌选择法，其在选择个体时不根据个体的选择概率，而是将所累积的概率进行选择，且最终的选择误差很小。

2.4 自适应交叉变异算子

随着算法迭代次数的不断增加，交叉和变异概率在这个过程中不断调整，以产生更优的个体。交叉操作实现基因的重组，变异操作实现基因的创新。交叉算子和变异算子之间相互配合，使得算法在多个局部空间达到收敛，最终可以提高全局收敛的速度和效果。如果当代的染色体的适应度值较为集中，此时则需要更激烈的交叉和变异，提高交叉概率Pc和变异概率Pm，反之降低。自适应调整的公式如下

(18)

(19)

其中:Fmax为进化过程中个体适应度函数最大值；Favg为进化过程中个体适应度平均值；F′为两个个体中较大个体的适应度函数值；F为待变异运算的个体适应度函数值；Pc1>Pc2>Pc3,Pm1>Pm2>Pm3且为区间(0,1)内的某个值，在优化过程中自适应调整。图2、图3为参数自适应的调整过程。

图2 自适应的Pc概率

图3 自适应的Pm概率

自适应的遗传算法流程图如图4所示。

图4 算法流程图

3 仿真模拟计算

3.1 实验环境及参数选择

在仿真实验中，自适应遗传算法的相关参数设置如表2所示。

现将自适应遗传算法应用于国内某机场的停机位分配，选取该机场某一天的航班和航班数据。待分配的航班数据如表3所示，该机场共有10个停机位，有40个航班需要停靠。机型的大小分别用L表示大机型，M表示中机型，S表示小机型。采用Matlab进行基于AGA的停机位分配实现，运行环境为一台PC机，CPU为i5 7300，内存8G，操作系统为Windows 10。

表2 自适应遗传算法的参数设置

表3 待分配的航班数据

3.2 实验结果分析

运用自适应遗传算法对多目标停机位分配模型进行了停机位分配实验，实验一共进行了30次，对其中30次中最好的一组分配结果进行分析，得到的分配结果如表4所示，进一步生成的甘特图如图5所示。为了更直观地展示停机位的占用情况，图6给出了各停机位分配的航班数量。图7为AGA得到的最大靠桥率的目标函数值曲线。图8给出了AGA得到的最低油耗的目标函数值曲线。图9为两种算法在30次中运行中的平均目标函数值收敛曲线。

表4 停机位分配结果

图5 基于AGA的停机位分配甘特图

图6 各停机位分配的航班数量

图7 最大靠桥率的目标函数值曲线

图8 最低油耗的目标函数值曲线

图9 两种算法收敛曲线

从以上的曲线中可以看出，在迭代次数达到163时，靠桥率达到85%，乘客出行方便。而在迭代次数为4时，飞机油耗达到最小，节约了航空公司成本。综合靠桥率以及飞机油耗这两个指标，在迭代次数达到111之后，最优解趋于平稳，也基本趋近收敛。与传统的遗传算法相比，最优解优化了3.47%。由此可见，AGA较好解决了停机位分配问题。

4 结论

本文针对民航运输机场中的停机位分配问题进行了研究，结合停机位分配中实际的约束限制条件建立基于AGA的多目标停机位分配模型，优化靠桥率及油耗，最后用Matlab进行仿真模拟实验，仿真实验结果表明了该方法的有效性。停机位分配问题是一个复杂的多目标多约束问题，综合考虑一些其他目标或更多的约束条件，用智能优化算法进一步优化，并且在航班发生延误时，或者由于机场、航空公司以及恶劣的天气因素对停机位分配造成影响时，能够动态地调整并确定更好的停机位分配方案是未来的研究方向。