基于鲁棒性模拟的停机位分配问题的数值方法比较

刘海滨 王炬博 巴博圣 王瑞昕

摘要：为了提升机场停机坪分配的鲁棒性，针对大型国际机场航班延误常态化对机场运行稳定性的影响，构建了两种整数线性规划模型，并引入爬山算法与大邻域搜索（LNS）元启发式算法进行效能比较。同时，采用Monte Carlo方法对不同目标函数在处理航班冲突时的效果进行评估。测试结果表明LNS算法在提升大型机场停机位分配方案的鲁棒性方面表现卓越，在求解速度和方案质量上均有显著提升。特别是，当以空闲时间的平方作为目标函数时，其效果尤为突出。

关键词：停机位分配；固定作业问题；机场；组合优化；大邻域搜索；线性规划

中图分类号：U-9；V2   文献标志码：A   文章编号：1002-4026（2024）02-0104-13

A numerical comparison of methods for solving the gate allocation

problem based on robustness simulation

Abstract∶Frequent delays of flights at large international airports can affect their smooth operation， hence， the airport apron allocation problem needs to be robustly optimized. In this study， we proposed two integer linear-programing models for solving this problem and used two algorithms for performance comparison： the hill-climbing and large-neighborhood search （LNS） metaheuristic algorithms. In addition， we used the Monte Carlo method to evaluate the effectiveness of different objective functions in dealing with flight conflicts. The final test results show that the LNS algorithm not only improves the robustness of the gate allocation scheme for large airports but also excels in speed and quality， especially， when the square of idle time is used as the objective function.

Key words∶gate allocation； fixed job problem； airport；combinatorial optimization；large-neighborhood search； linear programing

隨着民用航空运输业的蓬勃发展，高效合理地将有限的停机位分配给日益增加的航班成为大型机场资源调度的核心问题。考虑到天气变化及其他多种因素，航班延误成为常见现象。特别是，前序航班的延误可能导致后续分配至同一停机位的航班产生冲突，从而影响机场整体运营的平稳性。基于此，本研究专注于大型机场停机位分配方案的鲁棒性，旨在最小化航班延误对于停机位资源调度的负面影响。

在本研究中，我们将停机位分配问题（gate allocation problem， GAP）界定为一种固定作业调度问题（fixed job scheduling， FJS），其中，每架飞机均被视作一个具有确定到达及离开时间的作业。在理想情况下，若每个停机位能够适配任何飞机型号，那么FJS问题可以转化为最小化颜色数的区间图着色问题，并可在多项式时间内解决[1]。但实际情况是，由于停机位的大小不同，不是所有型号的飞机都能适配，因此大型机场的停机位分配问题实际上是一个NP（non-deterministic polynomial，非确定多项式）完全问题，即列表着色问题[2]。鉴于此，本文的研究重点是探索大型机场停机位的高效分配方案。

鉴于停机位分配问题在机场运营中的重要地位，国内外学者对该问题进行了深入研究。Bolat[3]在1999年借助整数线性规划（ILP）对该问题进行建模，由于当时缺乏解决ILP所需的计算能力，作者采用了分支定界法和启发式算法的混合方法。2001年，Bolat[4]运用遗传算法处理了更大规模的实例。随后的研究进一步改进了Bolat的整数线性规划模型[5-6]，通过减少约束条件的数量来实现求解速度的提升，另有研究应用动态规划、分支界限算法以及多目标遗传算法对停机位偏好设置[7] 、停机坪利用率[8]、航空公司间的公平性[9]和乘客步行距离等[10-11]进行了优化。

然而，考虑到机场日间不断变化的运营需求，停机位分配算法需要实时响应。目前最优的精确算法尚不能对较大停机位分配问题实例进行快速求解。因此，本研究提出针对性的爬山算法和大邻域搜索元启发式算法，力求显著提升停机位分配问题的求解效率和分配质量，实现停机位分配方案的实时响应。

1 数学模型

本研究首先对所研究的问题进行数学建模，随后通过仿真方法对冲突时间的期望值进行分析。文章中所采用的符号注释详见表1。

将n个航班的集合定义为F，m个停机位的集合定义为G。为每个航班fi∈F分配一个停机位gk∈GiG，其中Gi是可以接受航班fi的停机位的集合。决策变量为xi∈［［1，m］[KG-2.8mm]］，i∈［［1，n］[KG-2.8mm]］。

其中，［［·］[KG-2.4mm]］表示区间内取整数。对于优化目标，本文聚焦最大限度提高飞机之间的空闲时间，以确保停机位分配方案的鲁棒性。因此引入空闲时间的成本函数c。每次航班起飞前有一段空闲时间，同时每个停机位关闭前有额外的空闲时间，因此共有n+m个空闲时间。引入空闲时间变量Il，l∈［［1，n+m］[KG-2.8mm]］，则问题可以表述为：

文中的约束条件 （2） 旨在确保同一停机位上的飞机之间不会发生时间上的重叠，而约束条件 （3） 则限定每架航班必须被分配到与之兼容的停机位。正如前文所述，本研究提出了若干关于空闲时间的目标函数，并对这些函数对平均冲突时间的影响进行了比较分析。

1.1 目标函数

本研究采用Monte Carlo分析方法对给定航班时刻表的预期冲突时间进行模拟，并基于此比较了不同目标函数选择对停机位分配方案鲁棒性的实际影响。

1.1.1 预期冲突时间的估计

本研究的目标函数着眼于最大化停机位分配（gate allocation problem，GAP）方案的鲁棒性，同时力求最小化预期冲突时间，即在同一时段内两架航班共享同一停机位的总时长。这种冲突通常发生在两架分配至同一停机位的航班间存在较短空闲时间的情况下，其中一架航班的延误可能导致两架航班的停机时间发生重叠。因此，本文试图将最小化冲突时间问题转化为避免在停机位分配时刻表中出现短暂空闲时间的问题。

Bolat等 [3]和 YU等[11]，分别给出了不同的目标函数，来提升停机位分配的鲁棒性，如最小化空闲时间的平方和等。对于停机位分配问题来说，最小化平方和函数实际上等同于最小化空闲时间的方差，详见方程 （4） 。实际上，所有停机位占用的空闲时间总和与停机位分配方案本身是无关的，因此成本函数c不受时刻表的影响。

V（X）=EX2－E（X）2=EX2－C2～EX2（4）

其中V（X）表示空闲时间的方差，EX2表示空闲时间平方的期望，E（X）2表示空闲时间期望的平方，C为常数。最小化方差是指若所有空闲时间长度一致，则无法进一步降低短空闲时间的出现频率，这在航班延误的情况下更容易引发冲突。因此，通过最小化所有空闲时间的方差，可以有效减少短暂和过长空闲时间的数量。

为了验证选取哪种目标函数能最有效提高停机位分配方案鲁棒性，本文还需在给定的航班时刻表下模拟飞机延误情况。Castaing等[12]对4种不同的成本函数进行了比较，这些函数旨在最小化飞机间的冲突，包括冲突次数、冲突总时间、冲突的最长持续时间以及因停机位占用冲突导致乘客错过转机的航班数。结果表明，通过最小化冲突总时间可以有效改善其他三个成本函数的表现。Yu等[11]和Slveling等[13]指出，对数正态分布能更准确地预测飞机到达或起飞的延误时间。其中，Yu等[11]采用指数成本函数来最小化设定间隔时间内的停机位预期冲突时间。Pérez-rodríguez等[14]的统计分析显示，约77%的航班到达时间与计划时间相差不超过15 min。

基于上述研究成果，本文选用对数正态分布来模拟航班的到达和离开延误，并据此计算预期冲突时间。本文提出的估算预期冲突时间的Monte Carlo算法如下：

算法1 模拟冲突时间

输入：给定的航班时刻表s，迭代次数N

本模拟方法的优势在于，其输出结果可以直接反映停机位分配方案的鲁棒性，原因是本研究能够估算出特定调度方案下的冲突时间。然而，缺点在于计算时间较长，导致不适合作为算法的目标函数使用。因此，本文利用这一函数来评估结果的质量，并比较不同的目标函数，从而确定哪一个最能满足需求。

1.1.2 目标函数的选取

停机位分配的鲁棒性在于其方案能否有效应对由航班延误等因素引起的潜在停机位占用冲突。航班延误引发的主要问题是飞机对停机位的实际占用时间发生变化。因此，相较于简单地为飞机分配停机位，更关键的是为分配到相邻停机坪的飞机设定较长的空闲时间。鉴于所有飞机对停机位的总占用时间是固定的，所有空闲时间的总和也相应固定，意味着无法通过增加所有飞机间的空闲时间来提升停机位的鲁棒性。本研究探索了以下三种优化目标函数，空闲时间的平方函数和两个递減函数，并在2.2.2节中讨论了三种目标函数对停机位分配鲁棒性的提升效果。

（1）平方函数

R+→R+，II2。（5）

（2）指数函数

（3）指示函数

其中，S和S′是超参数。

在处理给定的空闲时间时，本文采用Yu等[11]中关于最小化预期冲突时间的指数函数，用以计算两架航班发生冲突的概率。此外，指示函数作为约束短空闲时间的基本函数也被考虑在内。若指示函数与指数函数在效果上相似，则优先选择简单的指示函数。如图1所示，展示了三种目标函数的结果，其中平方函数指的是空闲时间的平方与平均空闲时间平方之差，间接表示了以空闲时间平方为目标的函数。

1.2 线性规划模型

对该问题的求解可以用线性规划来模拟，本节提出了两种不同的数学模型。

1.2.1 基本ILP模型

基于线性规划的算法以及文献[4]，本节首先提出一个基本ILP（integer linear programming，整数线性规划）模型。在该模型中，使用二元决策变量xi，j，k，当飞机fj紧随飞机fi分配在停机位gk时，xi，j，k=1，i =0和j=n+1表示停机位的第一个和最后一个虚拟飞机（x0，i，k表示飞机fi是停靠在停机位gk的第一个飞机）。设所有二元决策变量xi，j，k所组成的集合为X，由于航班按起飞时间递增排序，因此只考虑i

式（9）表明存在n+m个空闲时间。式（10）～（12）确保每架飞机都被分配了一个停机位；每架飞机都有一个前置飞机，即该停机位上的第一个虚拟飞机；每架飞机也有一个后置飞机，即该停机位上的最后一个虚拟飞机。式（13）～（15）则规定任意一架飞机只能被分配到同一个停机位上，避免出现多个停机位之间的分配重叠，并确保飞机类型与停机位的兼容性。然而，式（13）产生了O（n2m）个约束条件，这使得模型变得庞大并且求解时间较长。鉴于此，本文将介绍一种约束条件数量较少的模型。

1.2.2 多商品流模型

停机位分配问题可以看作有向无环图G=（V，E）的多商品流问题

V=VF∪VsG∪VeG，（16）

E=EF∪EsG∪EeG。（17）

本文将停机位的开启节点视为源节点，将停机位的关闭节点视为汇节点，式（16）中VF代表飞机节点，VsG代表停机位开启节点，VeG代表停机位关闭节点。两个节点vi和vj之间的边e（vi，vk，k）表示飞机fj可以直接跟随飞机fi并分配到停机位gk。式（17）中EF代表飞机之间的边的集合，EsG代表停机位开启与第一个飞机之间的边的集合，EeG代表停机位最后一个飞机与停机位关闭节点之间的边的集合，每个边集的容量为{0，1}。

如图2所示为一个停机位分配问题的实例图。在该实例中，停机位g1可以停放飞机f1和f2，但不能停放飞机f3，而停机位g2可以接受所有飞机机型。飞机f1和f3是重叠的，因此这两个飞机之间没有相连的边。本文将每个源节点k与其汇节点连接起来，使其流经一组飞机。使用流量函数Φ：E→{0，1}来表示每条边的取舍，并为每条边设定空闲时间Ii，j，k的成本函数c（e）=c（vi，vj，k）。

故此，成本函数如式（18）所示，针对节点v，定义其进入边和离开边的集合分别对应式（19）和式（20）。同时，式（21）～（23）描述了本模型的约束条件，确保每个停机位和飞机都被纳入考虑范围内，并要求每架飞机被分配到唯一的停机位。此外，模型还要求任意一架飞机的前后飞机必须停靠在同一个停机位上。因此，如果流的源节点是停机位k，则存在一条离开边连接到停机位k。

该模型的线性规划模型表示如下，此模型使用与基本ILP模型相同的二元决策变量xi，j，k，式（24）所定义的目标函数保持不变。式（25）～（28）分别规定了每个源节点的流出量之和为1，这表示每个非空置的停机位都有第一个虚拟飞机；对于每个汇节点，流入量总和为1，确保每个非空置的停机位都有最后一个虚拟飞机；所有代表飞机的节点的流出量总和为1，表示该飞机之后只有一个飞机与之相连，或者该飞机指向一个汇节点；对于每个代表飞机的节点，其流入量总和必须等于通往相应停机位的流出量总和，此约束条件由式（23）来表述。式（29）～（30）规定了分配至同一停机位的飞机之间的停机时间不得重叠，并且飞机机型必须与停机位兼容。式（28）是影响模型复杂度的关键因素，它使模型具有O（nm）个约束条件，这远少于基本整数线性规划（ILP）模型的约束条件数量。

1.3 元启发式算法

鉴于大型机场在实际运行中需要迅速做出决策，能够在极短时间内（＜10 s）提供高质量解决方案的需求至关重要。因此，本文将着重介绍两种元启发式算法，旨在快速寻找停机位分配问题的近似最优解。

1.3.1 爬山算法

爬山算法是一种在邻域内寻找更优解的优化算法，直至无法进一步获得更佳解时才停止，见算法2。

算法2 爬山算法

输入：停机位分配问题的可行解s

输出：停机位分配问题的局部最优解s

1： s ← GenerateFeasibleSolution

2： WHILE 领域内存在更佳解s DO

3：  s ← BestLocalMove（s）

4： END WHILE

5： RETURN s

本文提出將固定邻域搜索（或称局部移动）与爬山算法结合应用于解决停机位分配问题。这种方法对于各类成本函数均具有较高的实用性（并不局限于特定类型的成本函数），能够迅速找到局部最优解。

在邻域搜索（local move）中，针对当前的停机位分配方案s，选择以下两种优化策略中的一种：交换两架飞机的停机位（称为交换移动）；或将一架飞机从当前停机位调整到另一停机位（称为移位移动）。本文将对每一种可能的移动（包括交换移动和移位移动）进行评估，以确定最优的局部移动（best local move）。为了提高求解效率，本文采用记录上一次迭代评估结果的方法，仅对因上一次移动而变化的移动进行重新评估。

生成可行分配方案（generate feasible solution）的函数，本文实施了修复启发式算法。当前飞机无法分配停机位时，该算法将对每架飞机进行强制分配。这一方法参考文献[15]中介绍的突破性局部搜索（breakout local search）算法。修复启发式算法的具体描述见算法3：

算法3 初始化迭代得到可行解

输入：所有未分配到停机位的飞机集合s，最大迭代次数K

输出：未分配停机位飞机的集合s

1：Q ← ALLFlights（s）

2：flightAfterProblem ← -1    -1 表示当前无飞机待分配

3：counter ← 0

4：WHILE Q≠ DO

5：  i ← FirstElementFromList（Q）

6：  Q ← Q＼＼{i}

7：  IF flightAfterProblem=i THEN

8：   flightAfterProblem ← -1    分配结束

9：   counter ← 0

10：  END IF

11：  g ← ChooseRandomValidGate（i，s）

12：  IF g ≠ -1 THEN

13：   s ← Allocate（s，i，g）

14：  ELSE

15：   counter ← counter + 1

16：   IF counter < K THEN

17：    IF flightAfterProblem=-1 THEN

18：     flightAfterProblem ← FirstElementFromList（Q）

19：    END IF

20：    Q，s ← ForceAttribution（Q，s，i）

21：   ELSE   无法找到可行解

22：    EXIT

23：   END IF

24：  END IF

25： END WHILE

26： RETURN s

該算法首先将s初始化为所有未分配到停机位的飞机集合，并设置flightAfterProblem为变量，用于判断是否还有飞机需要分配。如果当前无飞机待分配，则返回-1；若有，则选择一个飞机进行停机位分配（如第17行所示）。ChooseRandomValidGate函数用于在s中随机选择一架可分配的飞机i，若无法找到合适的飞机，则返回-1。第12行指代将飞机i分配至s中的停机位g。此外，第16行中的K代表求解的最大迭代次数，一旦计数器超过K，启发式算法便会停止，并报告未找到可行解。算法第20行定义了强制分配停机位的函数，即将当前航班i强制分配至一个随机停机位，同时将与飞机i分配至该停机位相冲突的其他飞机移出，并将这些未分配的飞机重新加入到列表Q的开头。因此，当飞机列表中的每一架未分配飞机都被重新分配后，算法结束。

1.3.2 大邻域搜索

此外，本文还提出了基于整数线性规划的大邻域搜索（ilp based large neighborhood search，LNS）元启发式算法。LNS的原理如算法4所示：

算法4 LNS算法

输入：停机位分配问题的可行解s

输出：停机位分配问题优化重组后的解s

1： WHILE 不满足停止迭代条件 DO

2：  s′ ← repair（destroy（s））

3：  IF 分配方案s′相较s更优 THEN

4：   s ← s′

5：  END IF

6： END WHILE

7： RETURN s

为了适应停机位分配问题的求解需求，本文在LNS算法中定义了Destroy和Repair两种方法。在Repair方法中，采用了精确算法，具体为第1.2.2节所介绍的整数线性规划（ILP）多商品流模型。而Destroy方法则通过随机选择固定数量的停机位，并对这些停机位上已分配的飞机进行释放。因此，Destroy和Repair方法的具体操作为：首先随机选择nd个停机位；然后利用ILP多商品流模型对所选停机位的航班进行优化重组。其中主循环的迭代总次数和每次循环迭代重组停机位的数量的选取，对LNS元启发式算法的求解效率较为重要。

2 数值结果

本研究的数据来源于巴黎戴高乐国际机场的真实运行数据，该数据集已上传至http：//recherche.enac.fr/～wangrx/gap。该数据集包含了巴黎戴高乐机场历史中最繁忙的30天的运行数据。所有结果均在配置了

120 GB内存及两个Intel（R） Xeon（R） CPU E5-2650 v3 @ 2.30GHz的Ubuntu 18.04.3 LTS系统的工作站上计算得出。

2.1 数据分析

本研究的每个实例包含了当天的每个航班及其分配的停机位。表2展示了在所有实例中航站楼及停机位的平均使用情况。其中，占用率定义为航班在停机位上停留时间与总时间的比例。高占用率意味着航站楼的空闲时间最少，即其运营最为繁忙。由于航班在不同航站楼的分布存在不均匀性，因此解决停机位分配问题的复杂度高度依赖于航站楼的选择。在这些航站楼中，2F航站楼的占用率最高且航班数量最多，因此本文将重点研究该航站楼。需要说明一点，为了确保航空公司运营的高效性、地勤服务的便捷和旅客转机的便利性，巴黎戴高乐机场的停机位分配问题通常不会跨越不同航站楼进行。

2.2 目标函数比较

在本节内容中，我们专注于确定能够使指数函数和指示函数达到最佳表现的超参数，随后将三种目标函数应用于航班延误的模拟测试中，并通过计算模拟分数（simulation score）来进行比较分析。

2.2.1 确定超参数

首先根据算法1的结果确定指数函数和指示函数超参数的初始值，并进一步优化指数函数和指示函数超参数的选取，将航站楼2F的每个实例分别用最终确定的超参数和LNS方法进行求解。图3中的结果显示了航站楼2F实例的平均求解时间和模拟分数。实验表明，就模拟分数和求解时间而言，指数函数的S=20和指示函数的S′=50是最合适的超参数。

2.2.2 目标函数比较

在本研究中，我们对三种目标函数进行了比较，主要依据是模拟分数和求解时间。

图4（a）分别显示了指示函数与指数函数相对于平方函数的相对模拟分数，能看出指示函数在最小化模拟分数方面的效率较低，经计算其模拟分数的平均值为95.78，是其他函数的两倍之多。相比之下，指数函数和平方函数的表现更为接近：在所有航站楼2F的实例中，指数函数的平均分数为54.09，而空闲时间的平方函数的平均分数为54.84。图4（b）为求解时间的结果，可以看到指示函数和指数函数的求解速度大致相当，而平方函数的求解速度更快，大约比其他函数快25%。

综合分析，指示函数在三种目标函数中的表现最为逊色，其模拟分数与其他两个函数相比有明显差距，而在运行速度方面虽然慢于平方函数，但与指数函数相近。在选择最佳目标函数时，虽然平方函数和指数函数的模拟分数相近，但平方函数在求解时间上具有明显的优势。因此，本研究认为平方函数是优化预期冲突时间的最佳目标函数选择。

2.3 方法比较

为了比较不同方法的结果，本文选择仅采用平方函数c（I）=I2 作为目标函数，旨在在最短的时间内最大程度地优化停机位分配方案的鲁棒性。

2.3.1 精确算法

首先，本文对比了1.2.1节和1.2.2节中介绍的基本整数线性规划（ILP）模型和多商品流模型的求解结果。这两个模型均通过Gurobi 10.1进行了优化求解，同时给出了这两种模型在处理全部30天航站楼2F实例的最优解时的求解时间（详见OSID科学数据与内容）。采用基本ILP模型的平均求解時间为4 414 s，而多商品流模型的平均求解时间仅为121 s。显然，多商品流模型更为高效，其约束条件数量的减少显著加快了求解速度。

2.3.2 元启发式算法

在对比两种元启发式算法之前，本文首先着手确定了LNS算法中的最佳参数。为了实现这一目标，本研究在每个航站楼2F实例上对LNS算法进行了20次运行，并记录了每次运行的求解结果。图5展示了在不同的迭代重组停机位数（nd值）下，所得结果与最优解之间的平均差距。

设置迭代重组停机位数（nd值）为5或7时，可以最终获得近似最优解。当nd= 7时的迭代收敛速度与nd=5相近，但单次迭代所需时间较长。因此，在综合考虑求解时间与求解质量的基础上，选择使用nd=5进行100次迭代。

在确定了上述参数之后，本文比较了爬山算法和LNS算法的结果。与之前的实验设置相同，两种算法分别在航站楼2F的30天实例上进行了20次测试。图6展示了所有实例的平均结果概览，详细信息请参见OSID科学数据与内容。

研究结果显示，这两种启发式方法都能在几秒钟内找到与最优解相差不到1%的结果。在求解时间方面，这两种启发式算法的表现更为卓越，寻找高质量解的速度是多商品流模型的20倍以上（平均找到最优解的时间超过了多商品流模型总求解时间的95%）。

2.3.3 模拟分数对最优值差距的敏感度

本节对使用优化分数（基于空闲时间平方和计算得出）和模拟分数时，与最优解的差异进行了分析。图7展示了利用LNS算法和爬山算法对所有航站楼2F实例进行超过20次运行后得到的平均值。图中的虚线表示LNS算法和爬山算法的最优得分与航站楼2F实例最优得分的对数比，实线表示爬山算法、LNS算法的模拟分数与精确解的对数比。结果显示，从优化分数转换到模拟分数时，与最优值的差距有显著增加：LNS算法的模拟分数与最优值的差距为0.27%，但比精确解的模拟分数高出6%；爬山算法与最优值的差距为1.2%，比精确解的模拟分数高出36%。

结果表明，预期冲突时间只对真正的短空闲时间有意义，而求解质量的微小下降会大大增加短空闲时间的数量。

图8展示了爬山算法、LNS和多商品流模型这三种算法对2F航站楼的所有实例20次求解后所得到的空闲时间分布的直方图的对比。三种优化结果中空闲时间主要出现在100～200 min范围内，其中对于小于20 min的空闲时间（机场仿真运行过程中容易出现由于飞机的延误等原因造成对停机位的占用冲突的空闲时间范围），尤其是对于短空闲时间（0～4 min），在LNS算法和多商品流模型优化结果中的出现频次显著低于在爬山算法结果中的出现频次，LNS算法和多商品流模型优化效果更佳。

3 结论

本文的主要目标是为大型机场寻找鲁棒性强的停机位分配方案。为此，提出了两种整数线性规划模型和两种元启发式算法，即大邻域搜索算法和爬山算法。研究结果显示，这两种元启发式算法在求解速度上较精确算法有显著提升，尤其是大邻域搜索算法，其求解结果与最优解的平均偏差小于0.3%。同时，本文还对比了三种目标函数的效果，发现平方函数在优化停机位分配方案的鲁棒性方面表现最佳。对于平方函数，预期冲突时间相对于空闲时间平方和的最优值非常敏感。这一发现表明，尽管精确算法的运算时间远超非精确算法，其在鲁棒性方面仍具有一定优势。所提出算法的高效实时响应能力，可有效运用在机场日常停机位分配中，并可应对增强紧急情况下机场的韧性，保障机场运行的高效性和安全性。未来的研究将致力于将停机位分配、机场跑道调度以及场面飞行器的滑行路径优化等问题进行深度融合，全面优化大型机场场面的整体资源调度。

参考文献：

［1］GUPTA U I， LEE D T， LEUNG J Y T. Efficient algorithms for interval graphs and circular-arc graphs[J]. Networks， 1982， 12（4）： 459-467. DOI： 10.1002/net.3230120410.

[2]HUJTER M， TUZA Z. Precoloring extension. IV. general bounds and list colorings[EB/OL]. ［2023-11-01］. http：//arxiv.org/abs/2104.01007.pdf.

[3]BOLAT A. Assigning arriving flights at an airport to the available gates[J]. Journal of the Operational Research Society， 1999， 50（1）： 23-34. DOI： 10.1057/palgrave.jors.2600655.

[4]BOLAT A. Models and a genetic algorithm for static aircraft-gate assignment problem[J]. Journal of the Operational Research Society， 2001， 52（10）： 1107-1120. DOI： 10.1057/palgrave.jors.2601190.

[5]WANG R X， ALLIGNOL C， BARNIER N， et al. Departure management with robust gate allocation[C]//ATM 2019， 13th USA/Europe Air Traffic Management Research and Development Seminar. Vienna，Austra：ATM， 2019： hal-02090426.

[6]WANG R X， ALLIGNOL C， BARNIER N， et al. A new multi-commodity flow model to optimize the robustness of the gate allocation problem[J]. Transportation Research Part C： Emerging Technologies， 2022， 136： 103491. DOI： 10.1016/j.trc.2021.103491.

[7]JAEHN F. Solving the flight gate assignment problem using dynamic programming[J]. Zeitschrift Für Betriebswirtschaft， 2010， 80（10）： 1027-1039. DOI： 10.1007/s11573-010-0396-9.

[8]BI J， WANG F J， DING C， et al. The airport gate assignment problem： a branch-and-price approach for improving utilization of jetways[J]. Computers & Industrial Engineering， 2022， 164： 107878. DOI： 10.1016/j.cie.2021.107878.

[9]JIANG Y， HU Z T， LIU Z Y， et al. Optimization of multi-objective airport gate assignment problem： considering fairness between airlines[J]. Transportmetrica B： Transport Dynamics， 2023， 11（1）： 196-210. DOI： 10.1080/21680566.2022.2056542.

[10]DING H， LIM A， RODRIGUES B， et al. The over-constrained airport gate assignment problem[J]. Computers & Operations Research， 2005， 32（7）： 1867-1880. DOI： 10.1016/j.cor.2003.12.003.

[11]YU C H， ZHANG D， LAU H Y K. An adaptive large neighborhood search heuristic for solving a robust gate assignment problem[J]. Expert Systems with Applications， 2017， 84： 143-154. DOI： 10.1016/j.eswa.2017.04.050.

[12]CASTAING J， MUKHERJEE I， COHN A， et al. Reducing airport gate blockage in passenger aviation[J]. Computers and Operations Research， 2016， 65（C）： 189-199. DOI： 10.1016/j.cor.2014.02.011.

[13]SLVELING G. Stochastic programming methods for scheduling of airport runway operations under uncertainty[M]. Georgia Institute of Technology， 2012.

[14]PREZ-RODRGUEZ J V， PREZ-SNCHEZ J M， GMEZ-DNIZ E. Modelling the asymmetric probabilistic delay of aircraft arrival[J]. Journal of Air Transport Management， 2017， 62： 90-98. DOI： 10.1016/j.jairtraman.2017.03.001.

[15]BENLIC U， BURKE E K， WOODWARD J R. Breakout local search for the multi-objective gate allocation problem[J]. Computers & Operations Research， 2017， 78： 80-93. DOI： 10.1016/j.cor.2016.08.010.