基于双层规划模型的停机位冲突优化研究

李龙海，姚金程

（中国民航大学机场学院，天津 300300）

随着国内民用航空业的迅猛发展，航班密度也在逐年增加，航班流量不断增加给机场的运行管理带来了极大挑战。停机位是机场运行的重要资源，是飞机在地面的主要保障区域。停机位分配是机场资源配置的重要部分，合理的停机位分配可以有效提高停机位利用率和机场的运行效率，降低航班延误率和停机位运行风险。如何安全高效地分配停机位资源成为了现阶段停机位分配问题的重要研究方向。

近些年，国内外针对停机位分配问题的研究较多：马思思等[1]将航空器地面滑行距离最小作为优化目标建立停机坪分配模型，并通过实验仿真验证了模型的有效性；杨新湦等[2]结合进离场航班的运行特点，建立了停机位和机场滑行路径的临时改派双层规划模型，以此来解决停机位和滑行路径的临时改派对于整个机场运行造成的扰动问题；冯霞等[3]以缓冲时间成本最小为目标确立了停机位分配鲁棒性的评价函数，建立停机位分配鲁棒性模型以实现缓冲时间成本最小、停机位-航班匹配度最高和远机位使用率最低等优化目标，并使用禁忌搜索算法进行求解；Kim 等[4]以预期停机位冲突时间总和最小为目标，建立了一种停机位空闲时间与预期停机位冲突的指数关系模型并进行停机位鲁棒性指派。

现阶段的国内外研究成果中，针对停机位分配的研究主要是从提高机场运行效率[5-8]和降低延误成本角度考虑[9-10]，对由空域和放行原因对航班推出冲突可能导致的安全风险考虑较少，部分研究以机场运行效率最大化为前提条件，进一步加入了安全约束，得到的方案提高了安全性[11]，但这种方法更适用于流量不大、停机位资源较充足的中小型机场。相比于中小型机场，繁忙的大型机场可能很难找到完全满足最小安全间隔时间的最优解，因此，设置一个航班冲突时间最少的目标函数是必要的。

本文以远机位使用率和停机位分配鲁棒性作为上层模型的优化目标，以相同停机位、相邻航班推出冲突时间作为下层模型的优化目标，建立双层规划模型[12-13]。在提高机场运行效率的同时降低相同停机位、相邻航班的运行风险，兼顾了停机位分配的效率和运行安全，最后使用Matlab 对双层规划模型进行验证。

1 停机位分配模型

1.1 停机位分配冲突概述

由于航班冲突的情况较为复杂，选择机场繁忙情况较为普遍且可研究性较高的相同停机位、相邻航班冲突问题进行深入分析[14]。假设繁忙大型机场某一天的高峰时段航班流量超过了机场自身的容量限制，在进行停机位预分配阶段无法找到让所有航班都满足最小安全间隔时间的分配方案。例如将航班A 和B都分配到停机位h 停靠，航班A 预计到达时间为a1，预计起飞时间为d1，航班B 预计到达时间为a2，预计起飞时间为d2。很明显，当航班A 的起飞时间加上最小安全间隔时间大于航班B 的预计到达时间时，两个航班的实际间隔时间小于最小安全间隔时间，会出现停机位冲突。冲突时间[15]设定为航班B 实际进入和预计进入停机位h 的时间差。图1 所示为相同停机位、相邻航班冲突可能出现的时间分布图。

图1 相同停机位、相邻航班冲突分布图Fig.1 Diagram of conflict distribution of the adjacent flights at the same gate

1.2 假设条件

为了便于问题的研究和解决，做出以下假设：①选取繁忙机场某一天的高峰时段来进行研究。高峰时段的航班流量在机场容量可接受的范围内，即每个航班都可以被分配到停机位，但相同停机位、相邻航班的间隔时间可能会小于最小安全间隔时间；②在停机位分配时，所有需要的相关信息均已知；③停机位的分配遵循先到先服务的原则。

1.3 相关参数

假定：航班集合为N，停机位集合为M；航班数量为n，停机位数量为m；ai、di表示航班i 的预计到达时间和预计起飞时间；ok、ck是停机位k 的计划开始使用时间和计划停止使用时间；Ri表示航班i 的机型；Gk表示停机位k 允许停靠的机型集合；Q 表示远机位的集合。

V（i）表示在航班i 位于机场期间始终处于开启状态的停机位集合，V（i）={k|ok≤ai≤di≤ck，∀k∈{1，2，…，m}；U（i）表示预计到达时间晚于航班i 的预计到达时间且与航班i 有时间冲突的航班集合，U（i）= { j|ai≤aj≤di，∀j∈{i+1，i+2，…，n}；F（i）表示航班i 可停靠的停机位集合，F（i）={k|Ri∈Gk，∀k∈V（i）}；E（i）表示航班i 不能停靠的停机位集合，E（i）={k|∀k∉F（i）}。

si，j，k表示停机位k 的空闲时间，其中∀i∈{1，2，…，n-1，j∈{i+1，i+2，…，n}，即

航班i 和j 连续分配到停机位k 上时，∀i ∈{1，2，…，n-1}，j∈{i+1，i+2，…，n}，假定δ 表示最小安全间隔时间，航班i 从停机位k 推出时与航班j 发生冲突的时间长度可表示为

xi，k为决策变量，当航班i 被分配到停机位k 时，xi，k=1，否则设为0。yi，j，k也为决策变量，表示相同停机位k 上航班i 和j 的变量联系，当出现航班i 和j 接连被分配到停机位k 上，同时航班i 的到达时刻早于航班j 的情况时，yi，j，k=1，否则设为0。

2 双层规划模型

2.1 上层模型

上层模型是以机场运行效率最大为目标的停机位分配模型，其目标函数的最优解影响下层模型的求解。远机位使用率是指航班被分配到远机位的数量占比，机位空闲时间[16]是指前一个航班预计起飞时间与后一个航班预计到达时间的时间差。在机场运行中，降低远机位使用率[17]有利于减少旅客的步行距离，既提高了旅客的服务质量又在一定程度上增加了机场的运行效率；保证机位分配时间的均衡可以提高停机位分配系统的鲁棒性，考虑到相同停机位、相邻航班发生冲突对停机位分配系统鲁棒性的影响，将机位空闲时间平方和最小作为保证停机位分配鲁棒性的决策目标。经过分析可知，降低远机位使用率在一定程度上会造成距离稍远的机位空闲时间过长[18]，并进一步影响到系统的鲁棒性，两个指标相互之间存在一定的矛盾，需对两个决策目标设置相应权重[19]。具体模型如下

式中：ω 是远机位使用率的权重，ω∈[0，1]；p1和p2分别表示远机位使用率和机位空闲时间平方和，p1=，采用min-max 标准化法对不同量纲的两个决策目标进行归一化处理。约束条件中：式（2）表示唯一性约束，即同一航班只能分配在同一停机位上；式（3）表示机型匹配约束，即不同机型的航班只能停靠在满足机型许可范围的停机位上；式（4）表示独占性约束，即每个机位同一时间最多只能停放一个航班。

2.2 下层模型

以相同停机位、相邻航班推出冲突总时间最小为目标函数建立停机位分配下层模型，上层模型变量的变化会影响到下层模型的最优解。当后续航班j 的预计到达时间减前个航班i 的预计起飞时间小于规定的最小安全间隔时间时，则此相邻的两个航班发生了停机位冲突，设定所有发生冲突的后续航班实际进入和预计进入停机位的时间差为航班冲突总时间。具体模型如下

式中yi，j，k来自上层模型的求解结果，体现了上下层的数据传输。发生冲突时，冲突时间Ti，j，k增加会间接导致该停机位的空闲时间si，j，k增加，上、下层模型之间存在一定的变量联系。约束条件中：式（6）和式（7）表示每个航班只能分配一个停机位且该航班的机型必须在停机位允许范围内；式（8）表示独占性约束，即每个停机位同一时间最多只能停放一个航班；式（9）和式（10）代表决策变量之间的逻辑关系。

3 算法实现

遗传算法具有流程简单、易计算等特点，非常适合用来解决组合优化中的NP（non-deterministic polynomial）问题[20]。本文使用遗传算法对停机位双层规划模型进行计算求解，详细计算流程如下。

1）初始种群生成

采用整数编码方式，将从机场采集的航班时刻等数据根据时间前后进行排序，然后对其编码，产生种群的个体染色体，如图2 所示。其中，航班序号代表染色体中的基因序号，每个航班被安排的停机位编号代表基因的数值，染色体的个数为S。如第1 个基因序号为1，对应的基因数值为k1，则表示序号为1 的航班被安排在停机位k1停靠。由于只对停机位分配问题进行研究，所以上下层模型产生的个体染色体结构一致。

图2 染色体结构示意图Fig.2 Diagram of chromosome structure

2）适应度函数设置

按照上、下层模型的目标函数设置适应度函数，并根据适应度值对每个个体进行评估。

3）个体选择概率计算

使用轮盘赌选择法，根据适应度值大小来计算选择概率，即适应度越大，选择概率就越大，直接通过概率对个体进行选择。个体的选择概率计算如下

式中：pg表示个体g 的选择概率；Wg表示个体g 的适应度值。

4）染色体交叉

采用单点交叉的方式，即在两个不同染色体的随机相同位置处设置一个交叉点并两两相交，子代染色体的左右两侧分别来自于父代染色体，选中的父代个体以交叉概率pc进行交叉并产生子代。

5）染色体变异

在染色体交叉完成后即可获得下一代染色体，对于其中不满足要求的个体需要通过变异操作来进行调整。在交叉过后形成的新个体，有一定的概率会发生基因变异，这个概率称为变异概率pm，为了保证好的解不会有过多变形，设pm≤0.05。

4 实例分析

现将上述模型和算法应用于某实际运行机场的停机位分配，该机场共有103 个停机位，统计到的机场高峰小时容量为39 架次。假设在早晚高峰时段开始时均有63 个停机位处于占用状态，只能利用剩余的40 个停机位进行分配，其中，1～10 号停机位及21～40 号停机位为近机位，其余均为远机位。选取机场某天早晚高峰时段8：00—10：00 和19：00—21：00 的进离港航班数据作为样本，航班数量分别为82 架和85架，相比于机场的高峰小时容量，可以发现这两个时段内的航班流量均在一定程度上超出了机场自身的容量限制。

由于求解过程大致相同且篇幅有限，只列出早高峰时段的进离港航班时刻信息如表1 所示。每个停机位的早晚高峰开放时间分别为8：00 和19：00，停机位关闭时间分别为早晚高峰时段最后一个航班离开停机位的时间。设定早晚高峰时段的开始时间为00：00，Ai表示航班i 预计到达时间00：00 的分钟数，Di表示航班i 预计起飞时间距离00：00 的分钟数；I 表示航班编号；M 表示机型，1 表示小型航班，2 表示大型航班；1～28 号停机位为D 类及以上停机位，可以停靠所有类型的航班；29～40 号停机位为C 类及以下停机位，仅能停靠小型航班。设最小安全间隔时间为8 min，远机位使用率的权重ω=0.5。

表1 早高峰时段进离港航班时刻信息Tab.1 Flight info for arrivals and departures at morning rush hour

利用Matlab 软件中的遗传算法工具箱进行计算，设置种群数量为50，最大进化代数为100，选择方式为轮盘赌选择法，交叉方式为单点交叉，交叉概率pc=0.9，变异概率pm=0.04。

根据原计划和基于双层规划模型所得到的早高峰时段停机位分配甘特图如图3（a）和图3（b）所示。

图3 停机位分配甘特图Fig.3 Gantt chart of gate assignment information

按照同样的步骤对晚高峰时段的航班数据进行仿真计算，得到的早晚高峰时段远机位使用情况和航班冲突时间如表2 所示。

从表2 中可看出，利用双层规划模型优化后的远机位使用情况和航班冲突时间均有所减少。早高峰时段远机位的使用降低了31.25%，原计划下的冲突航班包括航班34 和60、航班22 和36、航班50 和68 等共11 对，优化后的冲突航班有6 对，冲突时间减少16 min。晚高峰时段远机位的使用降低了23.53%，原计划下的冲突航班包括航班39 和67、航班43 和78、航班47和80 等共11 对，优化后的冲突航班有7 对，冲突时间减少了24 min。在提高机场运行效率的同时有效降低了停机位运行风险，保障了停机位运行安全，适用于实际运行中高峰时段较为繁忙的大型机场。图4 所示为算法收敛曲线，可以看出，随着迭代次数的增加，目标函数值也在不断被优化，算法在30 代左右收敛。

图4 算法收敛曲线Fig.4 Curve of algorithm convergence

表2 早晚高峰时段停机位分配结果对比Tab.2 Comparison of gate assignment results in morning and evening peak hours

5 结语

在总结国内外停机位分配研究的基础上，以远机位使用率和停机位分配鲁棒性作为上层模型的优化目标，以相同停机位、相邻航班推出冲突时间作为下层模型的优化目标，建立了双层规划模型并运用遗传算法进行求解。通过实际算例分析发现，优化后的早晚高峰时段远机位使用分别降低了31.25%和23.53%，停机位冲突时间分别减少了16 min 和24 min，在提高机场运行效率的同时减少了相同停机位、相邻航班间的运行冲突，验证了双层规划模型的有效性。停机位分配问题一直是一个复杂的NP 问题，该优化方法可以为大型繁忙机场运行效率提升、停机位运行风险降低提供解决方案和技术支持。