基于免疫遗传算法的停机位动态再分配优化

闫 萍，刘梦诗

(沈阳航空航天大学经济与管理学院，辽宁 沈阳 110136)

1 引言

近年来，我国民航运输业发展迅速，机场急剧增长的航班量增加了场面资源的运行负荷，导致场面交通拥堵现象日益凸显，不仅降低了旅客服务水平，而且增加了航空器的运行成本。停机位是机场地面作业的重要资源，是进港航班的运行终点和离港航班的运行起点。机场停机位分配问题(airport gate assignment problem，简称AGAP)是实现航班快速安全地停靠，保证航班之间的有效衔接，提高整个机场系统容量和服务效率的关键环节。因此，对停机位优化分配的研究具有重要理论意义和实用价值[1-3]。

停机位分配问题的优化目标主要是旅客步行距离最小、停机位的空闲时间最小、停机位利用率最大等。由于停机位分配问题具有NP-hard特性，因此很难在有限的时间内获得大规模问题的最优解。目前，国内外学者对停机位分配问题的研究主要包括数学规划和智能优化两类方法。数学规划方法首先构建停机位分配问题的数学规划模型，再通过精确算法[4]或者借助数学优化软件[5-7]求解模型，进而得到问题的优化解。应用于解决机场停机位分配问题的智能优化方法主要包括：遗传算法[8-10]、禁忌搜索算法[11-12]、蚁群算法[13]、粒子群算法[14]、领域搜索启发式算法[15-16]等。

综上，目前的研究主要以停机位静态预分配计划为研究对象，通过优化模型与算法，得到较为完整的停机位分配方案。较少的文献考虑到航班延误情况下的停机位动态再分配问题[2]，并且在实际的停机位分配过程中，需要平衡航空公司、机场和旅客等多方利益，探寻综合考虑多目标优化的求解方法有待研究。因此，本文首先给出停机位实时再分配的多目标优化数学模型。其次，提出一种改进的免疫遗传求解算法，将免疫系统中抗体多样性的保持机制引入遗传算法中，有效提升算法的全局搜索能力。仿真结果验证了所提出的模型和算法能够得到合理有效的停机位再分配方案。

2 停机位再分配数学模型

停机位分配问题需要综合考虑航班机型、停机位类型和航班进、离港时刻等因素，在给定的作业时间窗内，为执行每个航班的飞机分配适当的停机位，以保证机场客货的有效衔接。停机位再分配模型是在停机位静态预分配优化方案的基础上进行实时动态调度。

2.1 模型参数的定义

为了便于模型的描述，首先给出构造模型所需的符号、参数和变量的含义。

N—航班集合；

M—停机位集合；

dkl—停机位k到停机位l的距离；

hk—分配到停机位k的航班进离港场面滑行距离，即航班进港时从降落跑道到停机位k的滑行距离与航班离港时从停机位k到起飞跑道的滑行距离之和；

T—相继分配给同一停机位的连续两个航班之间的最小安全时间间隔；

T′—停机位的可用运行时间；

ui—航班i的航空器类型；

vk—停机位k允许停放的最大机型；

H—一个大正常数；

此问题的决策变量为：

2.2 目标函数

以旅客的角度优化停机位配置，指标为旅客转机所需要移动的距离最小。从航空公司和机场的角度优化停机位分配，一方面，航班在机场场面的滑行距离尽量短，才能节省燃料的消耗，同时增大机场场面的容量；另一方面，提高停机位的使用效率，加快机场机位的周转速度，以优化停机位资源的利用率。因此，停机位静态预分配模型的目标函数为

(1)

(2)

(3)

停机位再分配模型的优化目标为多目标函数(4)，即在停机位预分配目标函数f1的基础上，增加了航班停机位再分配的鲁棒性目标。当发生航班延误或取消时，会造成对原有航班停机位分配方案的扰动，因此应尽量减少受干扰的航班数目。w1和w2分别是目标函数两部分的权重系数。

(4)

2.3 约束条件

停机位动态再分配问题需要考虑的约束条件与静态预分配时相同，主要包括下面几个方面

(5)

(6)

(7)

yijk+yjik≤1， ∀i，j∈N，∀k∈M

(8)

(9)

ui-vk≤+H(1-xik)，∀i∈N，∀k∈M

(10)

式(5)表示每个航班只能分配一个停机位。式(6)表示每个航班在同一个停机位上，最多只有一个直接相邻的后继航班。式(7)表示每个航班在同一个停机位上，最多只有一个直接前驱航班。式(8)和式(9)表示联合确定yijk的值，当两个航班连续使用同一停机位时，相邻航班必须要满足一定的安全时间间隔T，以保证场面作业的安全性。式(10)表示航班机型与停机位类型的匹配约束，停机位只能停放允许的航班机型。

3 免疫遗传算法设计

遗传算法通过自然选择、遗传和变异等作用机制，实现各个个体适应性的提高，是一种高效的自适应进化搜索算法。但大量的实践和研究表明，标准遗传算法存在局部搜索能力差和“早熟”的缺陷。免疫算法是受生物免疫系统的启示而设计出来的一种新型的智能搜索算法，具有较强的鲁棒性。因此，本文将免疫系统中抗体多样性的保持机制引入遗传算法中，避免遗传算法的过早收敛，综合遗传算法和免疫算法的优点，以提升混合算法的搜索性能。

3.1 个体编码

求解停机位分配优化问题的免疫遗传算法采用一种基于自然数编码的策略。算法个体表示航班序列，个体编码的总长度等于所有航班的数目总和。个体中的每一个基因位代表一个航班，表示航班的停机位指派优先级顺序。在为各航班指派停机位时，按照航班序列的顺序，优先为排在前面的航班分配停机位。对于每一个航班，如果存在多个候选停机位，则优先选择使得航班的到达时间与停机位的最早可使用时间之差最小的停机位，以提高停机位的占用效率。

例如，对于有5个航班的停机位分配问题，其个体编码为长度是5的行向量(5，2，1，3，4)，代表5个航班的停机位分配顺序。首先，为航班5分配停机位；然后，对航班2进行停机位指派；以此类推，按照航班序列5→2→1→3→4的顺序，完成所有5个航班的停机位分配过程。基于航班序列的自然数编码方案，在后续遗传操作中可以始终保持个体产生可行解，进而提高了算法的执行效率。

3.2 初始种群的产生

免疫遗传算法的初始种群由两部分组成：首先，由启发式规则产生一些解质量比较好的个体加入到初始种群中，用于改进初始种群的解质量；然后，通过随机生成个体的方法产生初始种群中的其它个体，以改善算法初始种群中个体的多样性。启发式规则产生的初始种群包括：按照航班离港时间升序排列的航班序列、按照航班进港时间升序排列的航班序列，以及这两类个体的邻域个体。邻域个体通过交换个体的航班序列中任意两个基因位置的航班得到。例如，对于包含5个航班的航班序列(5，2，1，3，4)，将第1个和第3个基因位上的航班交换后，得到新的航班序列(1，2，5，3，4)即为原航班序列的一个邻域个体。

3.3 计算个体密度

在免疫遗传算法中引入个体密度的概念，将个体密度的计算结果作为评价个体优劣的一个重要标准。个体密度的计算过程用信息熵来描述个体之间的相似度，表示群体中相似可行解的多少。

3.3.1 个体之间的相似度

(11)

其中，

3.3.2 个体的密度

根据种群中个体之间的相似度，设计每个个体a的密度值Ca通过式(12)计算

(12)

3.4 计算适应度

为了保持群体的多样性，将个体密度Ca引入适应度值的计算过程，以抑制群体中密度高的个体，使目标函数值优良且密度较小的个体适应度值也越大。对于种群中每个个体a，定义个体的适应函数f′a如式(13)。其中，fa为个体a的目标函数值，参数k为取值-0.5的常数。

(13)

3.5 遗传操作

免疫遗传算法的选择和交叉操作采用“君主方案”，即在对群体根据适应度值高低进行排序的基础上，用最优个体与其它偶数位置的所有个体以交叉概率pc进行交叉操作，每次交叉产生两个新的子代个体。在交叉操作后，对新产生的群体以变异概率pm进行变异操作，并计算其适应度值。

3.5.1 交叉操作

为了较好地保留父代航班序列中的航班相邻关系和先后关系，采用顺序交叉操作，具体方法如下：

1)从两个父代个体P1、P2的编码中随机选择两个切点位置X和Y；

2)交换父代个体P1、P2的位置X和Y之间的编码部分，并分别复制到子代个体C1、C2的相应位置中；

3)按照父代个体的原航班排序，将未排入的航班依次填入子代个体的空基因位中。

图1描述了父代个体P1=(3，1，6，4，2，5，7)和P2=(6，2，1，5，3，4，7)进行顺序交叉操作后产生子代个体C1=(6，4，1，5，3，2，7)和C2=(1，5，6，4，2，3，7)的过程。

图1 顺序交叉操作

3.5.2 变异操作

通过随机改变个体编码的某些基因对个体进行较小扰动来生成新的个体，以增加种群的多样性，改善算法的局部搜索能力。变异操作采用插入变异：首先，在变异个体中随机选择两个基因位置X和Y；然后，将基因位置Y的航班信息插入到基因位置X之后，其它的航班先后顺序保存不变。图2描述了对个体P=(3，1，6，4，2，5，7)进行插入变异操作后产生变异个体P′=(3，1，5，6，4，2，7)的过程。

图2 插入变异操作

3.6 算法流程

改进免疫遗传算法求解停机位分配优化问题的具体执行步骤如下。

1)参数设置。包括种群规模NP、迭代次数G、个体密度的阈值λ、交叉概率pc、变异概率pm等；

2)种群的初始化。利用提出的初始种群的产生方法对种群个体初始化，使初始种群既包含质量较好的个体，又包括随机生成的个体。子代个体种群初始化为Φ；

3)判断算法的迭代次数是否大于G：如果大于G，转向步骤10；否则执行下面的步骤；

4)遍历父代与子代种群中每个个体，依据式(12)计算每个个体a的密度值Ca；

5)个体适应度评价。按照式(13)计算每个个体的适应度值：对于停机位预分配问题，目标函数为式(1)；对于停机位动态再分配问题，目标函数为式(4)；

6)子代个体种群与父代个体种群合并，并且根据适应度值进行排序，取前NP个个体作为新群体，进行下一次遗传操作；

7)以交叉概率pc对新种群进行交叉操作。两个父代个体交叉产生两个新的子代个体；

8)对交叉得到的种群中满足变异概率的个体按照变异策略进行变异，得到新一代子代种群；

9)算法的迭代次数增加一次，返回步骤3；

10)输出全局最好解信息，算法运行结束。

4 仿真结果与分析

4.1 实验设置

将上述模型应用于具有8个停机位的某小型机场停机位分配过程。对机场在9:00-13:00时间内的20个航班进行仿真，分别模拟停机位静态预分配和航班延误情况下的再分配方案。航班进离港时间以及航班的机型信息见表1，航班机型与停机位的匹配关系见表2。分配到停机位k的航班进离港场面滑行距离hk以千米为单位，取值为区间[1，5]内的随机整数。停机位的最小安全时间间隔T为5分钟。对于免疫遗传算法，算法种群规模NP=50，最大迭代次数G=1000，交叉概率pc=0.9，变异概率pm=0.01，个体密度的阈值λ=0.5。

表1 进离港航班信息

表2 航班机型与停机位的匹配关系

4.2 实验结果分析

免疫遗传算法得到停机位静态预分配方案如图3所示。在20个航班中随机产生20%的延误航班。设航班F03、F07、F10、F15先后延误25min、20min、15min、10min，通过停机位再分配优化模型，采用免疫遗传算法得到停机位再分配方案。图4给出航班的动态调整结果。延误航班导致对3个航班的停机位预分配方案进行了动态调整，具体调整方案为：航班F10由原来的停机位G3调整到G6，航班F13由原来的停机位G8调整到G7，航班F20由原来的停机位G3调整到G5。从实验结果可以看出，停机位再分配方案兼顾了旅客、航空公司和机场的利益，在减少旅客转机步行距离和航班场面滑行距离，提高停机位利用率的同时，最小化由延误航班带来的停机位预分配计划扰动。

图3 航班停机位预分配方案

图4 航班停机位再分配方案

5 结论

本文从平衡航空公司、机场和旅客等多方利益的角度，研究机场航班停机位的分配问题。

1)构建停机位静态预分配模型和考虑航班延误情况下的动态再分配模型，并设计改进免疫遗传算法对模型进行求解。

2)针对20个航班的停机位分配过程进行优化仿真分析，结果表明：当4个航班发生延误时，动态调整后的停机位分配方案中，仅有3个航班改变了停机位预分配计划。所提出的免疫遗传算法达到了较好的优化效果。

3)由于天气条件、机场、机组、航空公司等诸多方面因素都会对停机位分配过程造成影响，因此，考虑更多综合因素的停机位实时动态分配方法还有待做更进一步的研究。