基于遗传算法寻优的登机0分配策略

何静　张玉洁

摘要：本文考虑旅客流程时间和换乘紧张度并优化分配登机口，将20日内规定出发、到达时间的303次国内、国际航班分配给69个符合航班属性的登机口，提出符合各问题要求的登机口优化方案。

[关键词]遗传算法 匹配策略 登机口

1 数据收集

航站楼T和卫星厅S的布局设计如图1所示。航站楼T有28个登机口，卫星厅S有41个登机口。航站楼T和卫星厅S之间需要捷运时间，S厅没有办理出入境手续功能。

20日起降航班量为303次，机场总登机口数为69，如果直接进行整数规划方案，69303的解空间将会大大增加问题的复杂度和运算时间，降低运行效率，计算结果也会难以接受。因此，我們将遗传算法种群根据登机口的功能属性划分为（NII，NDI，NDD，NID，WII，WID，WDI，WDD）8个种群（其中N代表窄机型，W代表宽机型，I表示国际，D表示国内。

2 建立模型

2.1 目标函数构建

考虑航班——登机口分配，因此只需要尽可能最小化登机口的数量。因此可以将目标函数构建如下：

其中|M|为集合的大小。

2.2 遗传算法

这里采用自然数编码，使用自然数对每个登机口进行编码，以登机口作为基因，按航班到达的先后次序组成染色体。登机口按照T1，T2，..T28，S1，S2，..S41的顺序排序，然.后使用非零自然数编码，其中T1为1号，S1为29号，S41为69号。整数字符串呈现的染色体是表达航班到具体登机口的情况。字符串的长度为航班的班次，共303次航班，每一个数位对应一个航班，基因序列中的具体数字是指该航班所分配的登机口编号。例如，字符串“23565...521”中连续的两个“5”表示第五个登机口依次被分配给第三个和第五个航班。

2.3 基因操作

2.3.1 基因选择

选择择算子增大父代适应度值大的个体遗传至下一代的概率，以保证种群的基因优良，使种群个体能够不断接近最优解。

本次采用轮盘赌选择方式选择操作，将个体适应度值与整体适应度值比例作为被选择的概率。采用轮盘赌方法作为选择算子，使得具有更好适应度（目标函数）的染色体具有更多的选择机会，能够保证优良基因的存续能力，保证了程序的鲁棒性，增加了寻找到最优解的概率，但是也容易使种群在前期失去多样性。

2.3.2 交叉算子

交叉算子可以用来模拟生物进化过程中生物的基因重组，因此交叉算子也被叫做基因重组。每一次交叉操作在两条染色体上进行操作，并通过结合两种染色体的特征产生后代。在遗传算法中，人们希望通过交叉操作能够生成比父代更为优良的个体，因而有利于更快更好地进化出人们想要得到的最优解。

2.3.3 变异算子

本文采用随机生成方法实现运变异操作。由于本题约束条件较多，因此我们选中的变异位点将在其对应的解空间内随机生成于当前点不同的登机口。

我们对原始数据进行了描述统计和分析，我们观察原数据发现换乘旅客中有三位乘客情况不正确，分别为T2891、T2892、T2893，这三位乘客所买降落航班时间均晚于换乘航班的起飞时间。

2.3.4 求解结果

首先，我们对原始数据进行了描述统计和分析，我们观察原数据发现换乘旅客中有三位乘客情况不正确，分别为T2891、T2892、T2893，这三位乘客所买降落航班时间均晚于换乘航班的起飞时间，为了使后面的仿真结果更准确，我们对错误数据进行了分离。

然后，在我们的求解结果中，登机口按照T1，T2，.T28，S1，S2，..S41的顺序排序，然后使用非零自然数编码，其中T1为1号，S1为29号，S41为69号，在图表中取序号表示。

3 结论

在只考虑航班一登机口分配。尽可能多地分配航班到合适的登机口，最小化被使用登机口的数量的情况下，最小损失函数值为0.5142，最小化登机口数量为36，T登机口数为19，S登机口数为17，中转乘客的登机口平均时间占用率为81.25%，时间占用率最小的为编号为4和18的登机口，他们的时间占用率分别为25.57%和21.69%。

参考文献

[1]程林辉，王江晴.求解车辆路径问题的改进遗传算法[J].计算机工程与应用，2010，46（36）：219-221.

[2]田巧玉，龙建忠，遗传算法的编码理论研究[J].自动化与仪器仪表，2013，10（04）：4-7.