基于分层序列法的多目标停机位分配

沈笑云，于荟文

（中国民航大学天津市智能信号与图像处理重点实验室，天津 300300）

中国民航运输业近年来发展迅速，机场数量、航班数量以及航空器规模等持续增加。如何在有限的资源条件下合理分配停机位，成为提高机场系统容量和服务效率的关键所在[1]。

停机位分配过程会受到诸多约束，分为硬约束和软约束[2]。硬约束是指在任何情况下都需要满足的约束条件，一旦违反可能会导致严重后果，包括时间约束、机型约束、唯一性约束。软约束是指在某些情况下可以违反的约束条件，包括国际/国内约束、航空公司约束、任务约束。违反了软约束则被视为软冲突。软冲突虽然不会造成严重后果，但会对机场正常运行造成负面影响。因此，为同时保证机场的正常运行和每架飞机都有机位可停，任何目标都应在软冲突次数最少的前提下进行优化。

国内外针对不同目标，运用多种方法对停机位分配问题进行了研究。尹嘉男等[3]以飞机滑行时间最短为目标进行了研究。杨越等[4]以近机位使用率最高和旅客步行距离最短为目标建立了分配优化模型。上述研究中，软约束被作为硬约束来进行建模。但在某些情况下，可能会出现飞机分配不到停机位的情况。Marinelli[5]以最小化旅客行走距离与远机位使用率为目标，使用蜂群算法进行求解。Ghazouani等[6]以近机位使用率最高为目标，采用遗传算法进行了求解。王永亮等[7]以旅客行走时间最短为优化目标，设计了交叉熵算法进行了求解。上述研究在建模时只添加了硬约束而忽视了软约束的存在，与机场实际运行状况存在一定差异。

针对以上研究中存在的不足，将软冲突次数作为较高优先级的目标进行考虑，采用分层序列法构建多目标停机位分配优化模型，同时设计针对性较强的混合遗传算法进行求解。

1 数学模型

在机位分配时，软冲突次数具有较高的优先级。根据分层序列法的基本思想，按照目标优先级的高低，将机位分配分为两个阶段，分别建立数学模型，分阶段逐步求取最优解。第一阶段在只添加硬约束条件下，以软冲突次数最少为目标构建优化模型。第二阶段利用第一阶段得到的分配结果对软约束条件进行松弛，在添加硬约束和经过松弛的软约束条件下，采用线性加权法，以近机位使用率最高和停机位预分配方案鲁棒性最好为目标进行建模。

为便于讨论和处理，引入3个假设：

1）信息完备性假设 在进行机位分配时，可以得到关于待分配飞机和停机位的所有相关信息；

2）容量满足假设 机场的实际容量可以满足航班量的需求，即可以为所有飞机都分配一个停机位；

3）有限时间段假设 对停机位分配的研究仅限于某一时段内，将连续过程简化为有限时间段进行处理。

1.1 参数定义

定义部分参数，如表1所示，其中M～MI为机位相关参数，N～NI为飞机相关参数。在表1基础上，其他定义如下。

1）xi，j、yi，j为 0-1 决策变量，i∈N，j∈M。当飞机 i分配到机位j时其取值为1，否则为0。

2）V（i）={j|oj≤ai≤di≤cj，∀j∈[1，2，…，m]}为开启时间早于飞机i预计进港时间且关闭时间晚于飞机i预计离港时间的机位集合。

3）U（i）={k|ai≤ak≤di，∀k∈[i+1，i+2，…，n]}为计划进港时间晚于飞机i计划进港时间且与飞机i有时间冲突的飞机集合。

1.2 第一阶段

软冲突次数为

表1 参数定义Tab.1 Parameter definition

航空公司冲突次数为

任务冲突次数为

以f1最小为目标，采用唯一性约束、时间约束、机型约束作为约束条件。因此，第一阶段优化模型为

其中：第1个约束条件为唯一性约束，即对于每架飞机，必须且仅能被分配到1个停机位，且占用时间在该停机位可用时间内；第2个约束条件为时间约束，即对于每个机位，同一时刻最多只能停放1架飞机；第3个约束条件为机型约束，即对于每个机位，只允许停放规定允许机型范围内的飞机。

求解后得到第一阶段分配方案，记为 yi，j，i∈N，j∈M，其满足：①硬约束全部得到满足，能够保证机场的正常安全运行；②软冲突次数最少，最大程度减少分配方案对机场运行的负面影响。

由于分配方案仅考虑软冲突次数最少，没有针对近机位使用率和停机位预分配方案鲁棒性进行优化，无法满足实际运行需求，需进行第二阶段优化。

1.3 第二阶段

以近机位使用率最高和停机位预分配方案鲁棒性最好为目标，增加3种软约束条件，并根据yi，j对软约束进行松弛。由于同一时间段内，近机位使用率与远机位使用率的和等于1，近机位使用率最高也就是远机位使用率最低，即

取机位使用空闲时间平方和作为鲁棒性代表，平方和越低表示飞机被更均匀地分配到各个机位上，则该分配方案吸收或抑制飞行计划在执行过程中进离港时刻波动的能力更强，即鲁棒性越好。设飞机k为飞机i在机位j上紧邻的前序飞机。则飞机i紧邻的前序机位空闲时间为

机位j的最后一段空闲时间为

因此，分配方案的鲁棒性最好对应

由于要同时考虑近机位使用率和分配方案的鲁棒性，为了在同一目标函数中同时体现这两个因素，设计权重参数 W∈[0，1]，选取历史最大值 max（f5）和max（f6），对f5和f6进行归一化后加权求和，构建多目标函数

则第二阶段优化模型为

其中：前3个约束条件与第一阶段相同；第4个约束条件为国际/国内约束，yi，j=1时，飞机i可以分配到机位j上，否则飞机i只允许分配到国际/国内属性集合MPj包含其国际/国内属性Npi的机位j上；第5个约束条件为航空公司约束，yi，j=1时，飞机i可以分配到机位j上，否则飞机i只允许分配到可停航空公司集合MHj包含其所属的航空公司Nhi的机位j上；第6个约束条件为任务约束，yi，j=1时，飞机i可以分配到机位j上，否则飞机i只允许分配到可停任务集合MRj包含其任务属性Nri的机位j上。在该模型下求解得到的分配结果可在满足机场安全运行、机场负面影响最小化条件下，实现对近机位使用率和预分配方案鲁棒性的统筹优化。

图1 分配约束条件关系Fig.1 Relation between assignment constraints

两阶段的优化过程和结果如图1所示，其中包含10架飞机和6个机位。第一阶段的优化在图1（a）空白区域内进行。经过第一阶段优化得到的分配方案被标记为“√”。由图1（b）可知，第一阶段得到的分配方案共产生了5次软冲突。第二阶段的优化在空白及交叉区域内进行，保证优化结果的软冲突次数不高于5次。

2 算法设计

遗传算法通过模拟自然界的物种进化过程，解决了许多传统方法难以解决的非线性、多目标问题，拥有良好的全局搜索性能[8]。而贪婪算法具有简单、有效、时间复杂度低的优点，常应用于其他搜索算法初始解的生成[9]。将遗传算法与贪婪算法结合，设计了混合遗传算法，针对模型的两个阶段分别求解。算法流程如图2所示。

图2 算法流程图Fig.2 Algorithm flowchart

2.1 第一阶段算法

第一阶段采用贪婪算法与遗传算法结合的方式。

第1步染色体编码 遗传算法中，每个染色体都表示问题的一个解。首先对染色体进行编码，设计染色体的排列组合形式，便于后续步骤的操作并获得有效解。采用 1 个 n 维整数字符串（b1，b2，…，bn）表示对n架飞机的1个分配方案，称为染色体编码。其中每个编码bi表示将第i架飞机分配到第bi个停机位。如图3所示为一段时间内某10架飞机先后停在5个机位上的一组染色体编码图，b1=2表示将1号飞机分配到2号机位。

图3 染色体编码Fig.3 Chromosome coding

第2步种群初始化 按照飞机的计划进港时间，顺序初始化所有飞机。读取飞机和机位的初始信息，根据相关约束（式（5））产生每架飞机对应的可分配机位集合。从第1架飞机开始，计算将其分配到每个可分配机位所产生的软冲突次数，再根据贪婪准则从产生的软冲突次数最少的几个机位中随机选择1个作为该飞机的停机位。更新其他可分配机位集合。如果为空，则重新进行分配；如不为空，则依次分配得到1个初始可行解。循环执行上述步骤a次，得到一组包含a个初始可行解的初始种群。

第3步计算目标函数值 根据第一阶段目标函数（式（1））计算染色体的目标函数值。

第4步适应值映射 将目标函数值映射为适应值。目标函数值越小，其对应的适应值越高。

第5步选择 按照染色体适应值高保留、低淘汰的原则选择算子。采用联赛选择法作为此阶段的选择算子[10]，尽量保证适应值最高的染色体被选中。

第6步重组 重组算子采用单点交叉。设定重组次数r。随机选择两个父代染色体p1和p2，产生小于染色体长度n的随机整数k，将p1和p2第k位后的基因（bk+1，bk+2，…，bn）进行交换，产生出 2 个新的子代染色体p1′和p2′。新产生的子代染色体可能不满足某约束条件，需要对其进行检测和修复，直到满足全部约束条件。重复进行r次即完成了r次重组。

第7步变异 变异算子采用多点变异。设定每代的变异次数v和每次的变异位数b。随机选择个体p，计算该分配方案下所有机位的空闲时间段。根据每个机位的空闲时间段和每架飞机的可分配机位集合，可得所有飞机的可变异机位集合。在集合中，随机将飞机i分配到可变异机位j，即令bi=j。再将集合中包含飞机i或机位j的项全部删除。重复进行b次，即完成了1次变异操作。重复本步骤v次，即完成了v次变异。

第8步精英保留 防止由于遗传操作而导致父代较优的染色体被破坏，在每代遗传操作结束之后，对子代种群染色体进行评价，选择种群中的最优个体进行记录。遗传运算结束后，得到一组较优的分配方案。选择最优分配方案作为最终方案。

第9步迭代 将每一代种群中较优的染色体重新插入父代种群，替换父代种群中较差的染色体，重复进行选择、重组、变异等操作，直至达到第一阶段遗传代数g的要求。

经过第一阶段运算得到软冲突次数最少的分配方案，记为yi，j。在保证机场安全运行的条件下，该分配方案最大程度减少了分配方案对机场的负面影响。

2.2 第二阶段算法

第二阶段仍采用遗传算法，步骤与第一阶段基本相似，第2步、第3步和第5步区别如下：

第2步种群初始化 根据第二阶段约束条件（式（11）），产生每架飞机对应的可分配机位集合，并与第一阶段分配结果yi，j中每架飞机所分配的机位取并集，作为第二阶段的可分配机位集合。后续针对每架飞机的所有操作都在其各自的可分配机位集合中进行，从而保证在软冲突次数不高于第一阶段分配结果的同时，可对近机位使用率和预分配方案鲁棒性进行优化。初始种群随机产生，以保证其多样性，提高算法的全局搜索能力。从第1架飞机开始，随机分配到其可分配机位集合中的某个机位。更新其他未分配飞机的可分配机位集合。如果为空，则重新进行分配；如不为空，则依次进行分配，得到1个初始可行解。

第3步计算目标函数值 根据第二阶段目标函数（式（10）），计算染色体的目标函数值。

第5步选择 采用比例选择法作为该阶段的选择算子[11]。适应度越高的染色体被选中的概率越大。

第二阶段运算实现了在满足机场安全运行、机场负面影响最小化条件下，对近机位使用率和预分配方案鲁棒性的统筹优化。

3 实验分析

针对国内某大型机场的3个指廊和3个停机坪共计49个机位进行模型仿真与算法实现。其中1～20号机位及27～36号机位为近机位，其余为远机位。如该机位的开启时间早于8：00，则以8：00为该机位的开启时间。机位关闭时间统一选择18：00。选取计划进港时间在8：00后、计划离港时间在18：00前的共计101架飞机的航班数据进行仿真验证。

在进行实验前，需要确定各项参数。首先确定种群规模，种群规模较小时，收敛速度快，但容易过早收敛；种群规模较大时，收敛到全局最优解的概率更高，但收敛速度慢。综合考虑，设定种群规模a=100。由于采用贪婪算法生成初始种群，第一阶段可通过较少的遗传代数得到优化结果，因此设定第一阶段遗传代数g1=20，第二阶段g2=150。重组次数与变异次数根据数据规模确定。设重组次数r=30，第一阶段变异次数v1=5，变异位数b1=3。第二阶段变异次数v2=20，变异位数b2=2。

利用Matlab求解该算例，以W=0.5为例，仿真分配结果甘特图[12]如图4所示。其中发生了1次软冲突，多数飞机集中在近机位区域，且没有出现机位空闲时间过短的情况。两阶段算法性能分别如图5～图6所示。算法分别在遗传的第15代和第150代左右达到收敛。

图4 停机位分配甘特图（W=0.5）Fig.4 Gate assignment Gantt-chart（W=0.5）

图5 第一阶段算法性能图（W=0.5）Fig.5 Algorithm performance of Stage Ⅰ（W=0.5）

图6 第二阶段算法性能图（W=0.5）Fig.6 Algorithm performance of Stage Ⅱ（W=0.5）

CPLEX是国际上领先的优化软件包，也是目前公认最好的商业优化软件，在学术界和工业界中普遍认为可以将CPLEX中的算法作为新提出算法与之比较的标杆[13]。应用CPLEX在Matlab环境下建模并通过精确算法求解该算例，与通过两阶段混合遗传算法求解的结果进行对比，计算结果各项评价指标如表2所示。

表2 计算结果比较Tab.2 Comparison of calculation results

通过观察分析各项指标可以发现：

1）两种方法都能在保证每架飞机都分配到机位的前提下，将软冲突降低到1次，最大程度地减少了软冲突对机场运行造成的影响。

2）W值不同，近机位使用率和鲁棒性呈现出不同的升降趋势，所建多目标优化模型有效。在此优化模型下，机场工作人员可通过设置权重因子W，满足不同航班量及航班正常性下的分配需求：在航班量较少或预计次日航班正常的情况下，分配方案对鲁棒性的需求有所降低，可设置较高的W值，使优化更侧重于提升近机位使用率；在航班量较多或预计次日航班正常性较差的情况下，分配方案对鲁棒性的需求有所提升，可设置较低的W值使优化更侧重于预分配方案的鲁棒性，保证次日分配方案的平稳执行。

3）在W值相同的情况下，虽然两阶段混合遗传算法仿真结果的主要指标均略低于CPLEX，但前者仅需69 s即可得到优化结果，后者则需要约1 300 s。证明所提算法具有良好的优化性能和较高的运算效率。

4 结语

针对机场停机位预分配问题，提出了以软冲突次数最少为前提，以近机位使用率和停机位预分配方案鲁棒性为目标的多目标分配优化模型，并设计了一种求解该模型的混合遗传算法。算例应用表明，所建模型和所提算法能够在较短的计算时间内得出更加符合机场实际运行的分配结果，具有良好的优化性能和较高的运算效率，为解决机场停机位分配问题提供了理论参考。