协同时隙二次指派的改进自适应单亲遗传算法

陈可嘉，杨晓倩

(福州大学经济与管理学院，福建 福州 350108)

1 引言

众所周知，飞机相比于其他交通工具，具有方便快捷等诸多优点，能够为乘客节约宝贵的时间，因此越来越多的人选择飞机作为出行工具，使得空中交通密度急剧增长。这与基本保持不变的民航可用空域资源存在很大的矛盾，由此导致我国的航班延误问题日趋严重，不仅产生了巨大的经济损失，也造成了不良的社会影响。此外，空域资源容易受到恶劣天气等突发状况的影响，导致大面积的航班延误，这已成为我国主要的空中交通问题[1-2]。1987年，Odoni[3]第一次全面阐述了空中交通流量管理的基本概念、主要问题和研究领域，提出了通过重新安排航班计划以达到最小化航班延误成本的思想。如何对计划航班及时隙资源进行二次指派是一个非常复杂的问题，建立准确描述该问题的数学模型和快速有效的优化算法一直是民航领域的研究重点。

传统的空中交通流量管理采用中心决策机制，航空公司与空中流量管理部门之间沟通较少，信息互补不充分，缺乏对全局空中交通态势的了解[4]。协同时隙分配的目的是改善空中流量管理部门与航空公司之间几乎零交流的状态，促进它们之间的信息及时交换，同时引入航空公司参与具体航班时隙分配，以便当时隙资源减少导致原航班计划不可行时，及时对时隙资源进行二次指派，从而使原受扰航班计划在短时间内恢复，并使乘客的延误时间达到最短[5-7]。

1998年，李茂军等提出单亲遗传算法(Partheno-Genetic Algorithm，PGA)，该算法取消了传统遗传算法中的交叉操作，仅通过无性繁殖产生后代，具有操作简单且运行效率高的特点[8]，并于第二年进一步研究了PGA的全局收敛性[9]。近年来，在求解实际组合优化问题上，越来越多的学者采用单亲遗传算法，比如Yang等[10]采用单亲遗传算法求解考虑快速充电和定期充电的电动汽车最优路径模型。冯炳超等[11]为求解自行车共享系统静态再平衡问题对单亲遗传算法进行改进应用，能在较短的时间内获得更短的运载车路径方案。朱新平等[12]针对飞机过站保障车辆调度问题，运用递阶式染色体编码结构的单亲遗传算法求解，实验结果验证了算法的有效性。Wang等[13]将杂草算法与单亲遗传算法融合，获得一种带有繁殖机制的单亲遗传算法，用于解决寻址多旅行商问题。因此鉴于单亲遗传算法在求解实际组合优化问题方面的求解性能较好，本文借鉴单亲遗传算法的思想并加以改进使其适合时隙二次指派问题，并运用算例验证其有效性。

传统的单亲遗传算法都是按一定的概率进行遗传操作，为了进一步提高算法的收敛速度、搜索精度以及稳定性，Srinivas等[14]提出了自适应遗传算法，更有效的得出问题的全局最优解。传统的自适应单亲遗传算法(Adaptive Partheno-Genetic Algorithm，APGA)有一个缺陷：当染色体适应度值小于平均适应度值时，基因插入概率为一个定值，所以当适应度值小于平均适应度值的染色体所占比例逐渐增多时，基因插入概率也会趋于一个定值，达不到自适应调节的作用，全局搜索能力随之下降。因此本文提出了一种改进的自适应单亲遗传算法(Improved Adaptive Partheno-Genetic Algorithm，IAPGA)用于求解协同时隙二次指派问题，运用序号编码表示时隙指派方案，改进传统自适应机制增强算法的搜索能力。通过MATLAB对系列算例进行仿真，证实了本算法能在较短的时间内获得延误时间更少的时隙指派方案。

2 二次指派模型

2.1 模型假设

根据实际情况作出协同时隙二次指派模型的假设。

假设1：航空公司对分配得到的时隙具有自主使用权，且能够决定航班是否取消。

假设2：当出现突发状况如恶劣天气，时隙资源的数量会显著下降，导致航班与时隙数量不一致，需要对原航班计划进行二次指派。

2.2 问题描述

协同时隙分配过程可以分为两个阶段：第一阶段，流量管理部门根据各航空公司的时隙要求分配时隙，形成初始的航班计划安排表，此时航班数量与时隙数量是一一对应的关系；但是在实际运营中，可能会出现各种突发状况导致时隙资源的数量少于航班的数量，使得原航班计划不可行，这就进入时隙分配的第二阶段，航空公司需要重新安排航班计划。

本文研究在突发状况导致时隙资源不足的情况下，基于航空公司航班波的运行模式，将航班取消纳入航空公司时隙二次分配，以减少航班延误，恢复航班计划。

2.3 符号说明

集合定义。J为重新分配后可用时隙的集合，j∈J；I为计划到达航班的集合，i∈I；K为航班波的集合，k∈K；kh表示的是基于航班波k上的航班波全集，如原计划航班波1包括航班11和航班12，则航班波全集表示为{∅，{航班11}，{航班12}，{航班11，航班12}}，所以航班波全集是由原计划的航班波所包含的航班子集而构成的航班波的集合；k′为航班波子集，航班波全集中的每一个子集称之为航班波子集，k′∈kh；K′为基于航班波集合K上的航班波全集的集合。

参数定义。M为重新分配后可用时隙的数量；N为计划到达航班的数量；sj为重新分配后可用时隙j开始的时间；ri为航班i的初始抵达时间；dk为航班波k的初始抵达时间；ti表示中转到该航班的人数；fi为航班i的乘客人数。

变量定义。xij为0-1决策变量，当航班i使用时隙j时为1，否则为0；yk′为0-1决策变量，表示当航班波k的航班波全集kh中航班波子集k′出现在指派方案中时为1，未出现为0；zi为0-1决策变量，当航班i取消时，zi=1，否则为0；ek＇为航班波子集k′的实际抵达时间；wk′为航班波子集k′中包含的中转乘客人数。

2.4 数学模型

本文建立的协同时隙二次指派模型是以总的乘客延误时间最小为目标，以时隙分配的有效性为约束，制定时隙指派的优化方案。

2.4.1 目标函数

(1)

模型的目标函数(式(1))为乘客总的延误时间最短，其中包含三个部分：第一部分为航班取消导致的乘客延误。国际通行规定航班取消的延误时间H为480min，但不是取消航班的所有乘客都无法完成行程，一部分乘客可以通过签转到其他航空公司完成行程，此时延误时间缩短，国际通行规定由此产生的延误时间T为120min。从而，可以计算出取消航班i所造成的乘客延误时间ci(式(2))，其中，r表示航班的签转率。

ci=H×(fi+ti)×(1-r)+T×(fi+ti)×r

(2)

第二部分表示到达乘客的延误时间；第三部分表示转机乘客的延误时间(航班波的延误时间)。

2.4.2 约束条件

模型的约束条件如下

(3)

(4)

(5)

(6)

xij(sj-ri)≥0i∈I，j∈J

(7)

(8)

(9)

xij=0，1；yk′=0，1；zi=0，1 ∀i，i∈I，∀j，j∈J

(10)

式(3)表示每个航班最多使用一个时隙；式(4)表示每个时隙只能安排一个航班；式(5)表示所有时隙都得到使用；式(6)表示每个航班只能执行或取消；式(7)表示航班使用的时隙必须晚于航班初始抵达时间；式(8)表示航班波子集k′的实际抵达时间ek′等于航班波子集k′中最后一个航班的实际抵达时间；式(9)表示航班波k产生的所有航班波子集k′有且只有一个会出现在指派方案中；式(10)表示决策变量的定义域约束。

3 改进的自适应单亲遗传算法

本文所建立模型的求解属于NP-Hard问题，采用传统的数学方式很难求解，而且本文所建模型的目标函数和约束条件比较复杂，是一个大规模的组合优化问题，所以求解难度也随之加大。传统遗传算法(Traditional Genetic Algorithm，TGA)在求解组合优化问题上已有较多的研究与应用，然而并不是所有的组合优化问题都适合采用传统的遗传算法进行求解，可能存在计算过程复杂繁琐和“早熟收敛”等问题。

序号编码和非序号编码是遗传算法的两种编码方式，在求解组合优化问题时，序号编码相对而言更为简明有效。采用序号编码的染色体中的每一个基因表示的是求解问题中一个事物的序号，所以采用序号编码，其染色体就不能如同采用非序号编码的染色体一般进行随机的交叉操作，否则随机交叉后的个体很有可能就不再表示原问题的一个解。要解决上述问题，就必须使用操作起来很不方便的PMX、OX和CX等交叉算子[15]。

此外，传统遗传算法要求初始种群具有多样性。因为传统遗传算法产生后代的方式主要是通过交叉和变异操作，若两个相同的染色体进行交叉操作，则不能产生新的染色体，此时仅靠变异操作很难产生新的染色体，从而陷入局部最优解，即发生“早熟收敛”现象。

因此，针对上述缺点，采用一种能避免出现不符合问题的解和避免发生“早熟收敛”现象的特殊遗传算法，该遗传算法通过单个个体繁殖后代，所以称之为单亲遗传算法(PGA)。PGA算法用无性繁殖的方式取代了传统遗传算法中的交叉操作，仅在一条染色体上进行遗传操作，即使种群中的个体均相同，迭代也能进行，不存在“早熟收敛”问题。文献[16]表明PGA与TGA具有类似的进化机制，PGA仍属于遗传算法范畴，但PGA简化了遗传算法，提升了算法效率。

传统单亲遗传算法都是按一定的概率进行遗传操作，为了进一步提高算法的收敛速度、搜索精度以及稳定性，本文提出了一种改进的自适应单亲遗传算法。

3.1 基因及染色体编码设计

序号编码方式相对于二进制编码方式更加简明有效，直观性和可操作性也比较强。所以本文根据所建模型特性和序号编码方式的优点，采用基于递阶式的染色体编码方式，如图1所示，这种编码方式直观明了且准确性高。首阶代表控制基因串f，一个基因位代表一个航班号；次阶代表参数基因串j，各基因位代表首阶基因中相应航班指派的时隙号。染色体应分为几个连续的片段，其中每个片段相对的是一个航班波的时隙指派方案。jk表示航班波k包含的时隙号；fk表示相对应的所包含的航班编号。

图1 递阶式染色体编码结构

3.2 构建适应度函数

本文的研究目的是为了使总延误时间最短，以目标函数的倒数作为相应的适应度函数，如下所示

3.3 算法的选择操作

本文采用二元锦标赛选择策略，从种群中随机有放回的抽取2个个体，根据每个个体的适应度值选择最优的个体进入下一代种群，重复操作多次(重复次数为种群的大小)，直到新的种群规模达到原来的种群规模。

3.4 算法的遗传操作

单亲遗传算法引入5种算子对染色体进行遗传操作[17]。

1)算子Reinsertion

给定染色体x={x1，x2，…，xn}，随机生成2≤i≤n-1，2≤j≤n(i≠j)，将xi插入到xj的前一个位置，同时将其从原位置删除，从而得到新的染色体。

2)算子Or-opt2

给定染色体x={x1，x2，…，xn}，随机生成2≤i≤n-2，2≤j≤n(i≠j)，将xi和xi+1插入到xj的前一个位置，同时将其从原位置删除，从而得到新的染色体。

3)算子Or-opt3

给定染色体x={x1，x2，…，xn}，随机生成2≤i≤n-3，2≤j≤n(i≠j)，将xi，xi+1和xi+2插入到xj的前一个位置，同时将其从原位置删除，从而得到新的染色体。

4)算子2-opt

给定染色体x={x1，x2，…，xi，xi+1，…，xj-1，xj，…，xn}，随机生成2≤i

5)算子Swap

给定染色体x={x1，x2，…，xn}，随机生成2≤i

遗传操作的概率大小直接影响最后的最优解，因此，在本文中，主要是对单亲遗传算法中的算子进行改进，使算子实现自适应调节。根据本文的研究问题，结合自适应遗传算法的基本思想可知，当某一染色体的适应度值大于平均适应度值时，说明该染色体的性能较好，根据适应度值取较小的变异概率，相反，当某一染色体的适应度值小于种群中平均适应度值时，表明该染色体的性能较差，应该采用较大的变异概率。传统的变异概率按以下公式计算[17]

(11)

式中，f表示将要进行变异操作的染色体的适应度值，fmax表示种群中最大的适应度值，fa表示平均适应度值，Qm1=0.9，Qm2=0.5。

从式(11)中可以看出，染色体适应度值小于平均适应度值时，变异概率为一个定值，所以当出现适应度值小于平均适应度值的染色体所占比例逐渐增多的情况时，变异概率也会趋于一个定值，达不到自适应调节的作用，全局搜索能力随之下降。因此，可以从中做相应的改进措施，解决上述问题。

改进措施：当染色体适应度值小于种群的平均适应度值时，该染色体的性能较差，表明要以更大的概率对其进行变异操作。为了达到自适应调节的作用，即能够使变异概率能随适应度值的变化而变化，并维持合适的变异概率，本文对传统的自适应概率计算公式进行调整。插入以e为底的指数函数，由指数函数的性质可知，当其指数大于0时，指数函数的数值大于1，利用指数函数的这个性质，得到改进后的变异概率的计算公式如下[17]

式中，f表示将要进行变异操作的染色体的适应度值，fmax表示种群中最大的适应度值，fa表示平均适应度值，Qm1=0.9，Qm2=0.85。

3.5 算法的终止条件

当单亲遗传算法的迭代次数达到最大迭代次数时，算法终止。

3.6 算法流程图

本文改进的自适应单亲遗传算法流程图如图2所示。

图2 改进的自适应单亲遗传算法流程图

4 仿真算例研究

为了验证本文二次指派模型以及改进的自适应单亲遗传算法的有效性，利用典型算例和系列算例进行验证分析。在算法求解中，本文采用单亲遗传算法(PGA)、自适应单亲遗传算法(APGA)与文中改进的自适应单亲遗传算法(IAPGA)进行了比较研究。所有算例运用MATLAB2014b实现，在Intel core i7-7500U 2.70GHz处理器、8.00GB内存、Window 10系统下进行求解。其中各算法的参数设置如表1所示。

表1 算法的参数设置

4.1 实验数据

典型算例“17I-11J-5K”的出处选自文献[18]，其中，“***I-**J-*K”表示算例中包含有“***”个航班，“**”个时隙，“*”个航班波。在文献[18]的算例中，航班与时隙是一一对应的关系，考虑的是通过自主取消航班放弃时隙的情况，与本文所研究问题有些不同。通过减少时隙的数量使得时隙数量少于航班数量，以满足本文所研究问题。在9：00-11：40某航空公司计划在某机场降落17个航班，航班初始抵达时间、人数及相应的航班波信息见表2。需要说明的是，dk为航班波k的初始抵达时间，即为航班波k中最后一个航班的初始抵达时间，如航班波1的初始抵达时间为航班F14的初始抵达时间10：15。各航班波中转乘客的信息见表3。由于受到恶劣天气影响，导致时隙资源数量下降，空中交通流量管理部门重新为航空公司分配时隙，重新分配的时隙数量为11个，其详细信息见表4。同时，签转率r设置为40%。

系列算例“12I-8J-4K”的数据选自文献[19]，由于文献[19]提供的算例中，航班和时隙是一一对应的关系，所以为了符合本文研究问题，减少时隙数量使得时隙数量少于航班数量；算例“26I-17J-6K”选自文献[20]。由于篇幅的原因，只列出“17I-11J-5K”的数据。

表2 航班与航班波信息

表3 航班波中转信息

表4 时隙信息

4.2 仿真结果分析

分别使用三种算法求解“17I-11J-5K”算例的时隙二次指派方案，延误时间结果比较如表5所示，表中数据均取各个算法求解10次中的最优值。其中：PGA是传统的单亲遗传算法；APGA是自适应单亲遗传算法；IAPGA为改进的自适应单亲遗传算法。

表5 “17I-11J-5K”时隙指派方案

由表5可知，如果按照PGA的时隙指派方案，本算例的总延误时间为402000min，运行时间为6.96s；如果按照APGA的时隙指派方案，本算例的总延误时间为398143min，运行时间为7.01s；如果按照IAPGA的时隙指派方案，总延误时间为395650min，运行时间为7.13s。由此可以看出，在相同的计算环境和计算参数下，运用算法求解能在较短的时间内完成重新安排航班计划，且改进的自适应单亲遗传算法的最优解比另外两种算法更优，很好的满足了航空公司对重新分配时隙指派方案实施决策的要求。

三种算法对“17I-11J-5K”算例的迭代优化图如图3所示。从图3可以看出，APGA由于加入了自适应机制能够有效避免算法在迭代后期陷入局部最优，因此比PGA得到更好的最优解；IAPGA由于改进了自适应机制，使得基因操作概率更加灵活的随适应度值的变化而变化，在一定程度上能更加广泛的搜索最优解，因此搜得的最优解比其他两种算法更优。在IAPGA中，大约在第50代以后就得到了稳定的最优解，而采用PGA和APGA，在100代以后才达到稳定的最优解。综上可以看出IAPGA的收敛速度更快而且运行结果更优，能更快速高效的为航空公司重新分配时隙指派方案。

为进一步验证本文二次指派模型以及改进的自适应单亲遗传算法的有效性，对更多算例进行求解的结果如表6所示，表中数据均取各个算法求解10次中的最优值。由实验结果可知，IAPGA在不同规模的算例上都能得到更好的求解结果。

图3 “17I-11J-5K”迭代优化图

表6 系列算例PGA、APGA和IAPGA结果比较

三种算法对“12I-8J-4K”算例和“26I-17J-6K”算例的迭代优化图如图4和图5所示。同样也可以看出IAPGA的收敛速度更快而且运行结果更优，能更快的为航空公司重新分配时隙指派方案。

图4 “12I-8J-4K”迭代优化图

目前对重新分配时隙指派方案主要依据时隙的动态信息与原飞行计划，依靠经验进行人工排序。这种方法在任务繁重时运行效率较低，且会导致大量的航班延误。而采用本文的二次指派模型和优化算法只用较短的时间就可以完成重新安排航班计划，并且优化效果好于人工排序，很好的满足了航空公司对重新分配时隙指派方案的要求。

图5 “26I-17J-6K”迭代优化图

5 结论

针对协同时隙二次指派问题，本文提出一种改进的自适应单亲遗传算法，仅在同一条染色体上进行遗传操作能够有效避免出现不符合问题的解，该方法优化过程较为简练，采用序号编码表示时隙指派方案，通过改进传统自适应机制增强算法的搜索能力，加快收敛速度。系列算例结果表明，本文提出的IAPGA算法具有较好的优化效果，能够在较短的时间内获得比单亲遗传算法和自适应单亲遗传算法更短的延误时间及相应的时隙指派方案。