民用机场停机位分配问题研究综述

袁 媛，翟好鑫，吴宏元，闫 萍

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

民用机场的停机位作为进港飞机运行的终点和离港飞机运行的起点，为飞机停放、旅客上下飞机、行李货物装载提供了场所，也是航空与地面运输的转接点。随着航空运输业的快速发展，国内各大机场的航班数量都有明显增长，有限的机场设施资源逐渐成为限制民航事业发展的重要因素，因此，合理地分配使用各项设施资源是机场需要解决的主要问题。停机位作为机场运输资源的核心，其分配结果对大量物资、旅客以及相关工作人员都会产生影响，分配计划对机场航班和航线也均有直接的经济影响。作为机场运营管理人员日常面临的重要问题之一，停机位分配的目的是把每个航班分配至可用的登机口，同时也最大限度地为乘客和机场的运营效率提供便利，这就需要一个方法来实时更改和更新停机位分配数据。

为解决这一问题人们进行了大量的研究，许多学者针对经典停机位分配问题 (Gate Assignment Problem,GAP)进行研究和改进，包括综合考虑停机位分配各主体利益的多目标优化问题[1]，最大化预分配方式鲁棒性的优化算法设计[2]，考虑机位类型时最大化航班靠桥率的优化算法设计[3]，考虑航班时刻受到干扰时对停机位实时再分配问题的优化建模和算法进行设计[4-5]等。

结合国内外文献对停机位分配问题的分析，本文首先对停机位分配问题的特征进行描述，总结以往文献中常见的约束条件和优化目标，并对解决停机位分配问题的方法进行分类总结，分析未来该领域发展可研究的方向。

1 问题特征

1.1 约束条件

停机位分配涉及机场、旅客以及航空公司三方的切身利益，需要综合考虑多方面的因素：机场的停机位数量、航班类型与停机位类型的匹配、飞机机型、停机位的分布构造、停机位利用率、靠桥率、航班时刻、航班数量与密度、地面作业时间、旅客总人数、旅客行走距离、停机位间距离、行李托运距离等。

在为航班分配停机位时，两个基本约束应该首先满足：

(1)唯一性约束

每一个航班能且只能被分配到一个停机位。

(2)独占性约束

飞机在时间上和空间上对停机位具有独占性。

除了以上两个基本约束之外，在实际机场运行过程中和以往文献研究中也经常考虑下列8个重要约束(见表1)。

(3)缓冲时间约束

对于连续分配到同一停机位的两架飞机来说，它们应该有必要的安全时间间隔，被称为停机位缓冲时间，用来保障前后航班的安全，还要给地面作业人员充足的准备工作时间。同时缓冲时间还可以吸收实际运行中存在的随机延误，大多数文献都会考虑此约束，一般取值在10～50分钟不等。

表1 约束条件文献概况

(4)等待时间限制

航班到达机场上空时，可能会因为分配要求不允许立刻降落而执行空中等待指令，但其有最大的空中等待时间限制。

(5)航班机型与停机位类型匹配性约束

机场停机位有大停机位和小停机位之分，一般情况下大型飞机不允许停放至小型机位，而大型机位由于可以满足小型飞机的服务需求，也可以停放小型飞机，但会降低停机位的利用率，影响到后续大型飞机的停机位分配，因此机场一般会尽量减少小型航班停放到大型机位的情况。因此，关注机场停机位利用率的文献大都会考虑此约束。

(6)停机位与航空公司的约束

即航空公司属性约束。机场为了方便地勤服务的需求，会对不同航空公司分配其专属的机位，应尽量将该航空公司航班分配至专属停机位，以提高停机位分配效率。由于不同航空公司之间的竞争性，考虑航空公司公平性的文献一般会采用此约束。

(7)航线属性约束

即停机位与停放航班的航线属性匹配。一般情况下，中小机场的大部分停机位只能停放飞往国内航线的飞机，少量机位可以停放飞往国际航线的飞机。

(8)同一跑道飞机下降时间限制

在同一跑道上相继降落的航班之间有最小降落时间间隔，用以保证安全，研究多跑道机场的停机位分配问题一般会考虑此约束。

(9)宵禁限制

宵禁限制用来保证时间窗结束前安排好航班的停机位。

(10)使用登机桥登机的旅客占比约束

中国民用航空局发布的《民用机场服务质量》中规定，旅客通过登机桥登机的数量不宜低于80%。

以上所列举的约束是一些比较常见的约束，除了上述约束规则还有许多其它约束，机场的实际情况不同，其对应的约束也会相应发生变化。

1.2 主要优化目标

停机位分配问题涉及到机场、旅客以及航空公司多方主体的利益，为多目标组合优化问题。以往的停机位分配研究由于不同的机场侧重点不同，主要注重提高旅客服务质量、优化机场和航空公司的运行效益。本文从以下3个方面对主要优化目标进行介绍(见表2)。

表2 优化目标文献概况

(1)机场方面

①最大化停机位预分配方式的鲁棒性

停机位分配的鲁棒性是指停机位预分配方式自身具有一定的“抗干扰能力”。由于目前机场停机位资源非常紧缺，当进离港航班发生不确定性延误时，就不可避免地影响到其他航班而导致重新分配。因此，为提高机场的服务质量，降低机场的运营成本，在确保机场快速恢复的情况下，还应该使航班的机位分配与原计划机位分配尽量保持一致[6]。

②停机位占用均衡

综合考虑旅客候机便捷与舒适和行李提取、机场安检等问题，当停机位空闲时应尽量分散停靠的航班，停机位空闲时间段的相对均衡可以明显降低航班由于延误起飞或到达而产生的影响，同时也能保证机场调度人员工作强度与时间的均衡。因此，该目标函数在近几年的文献中使用较多。

③最少化占用停机位数目

在考虑旅客登转机时间、停机时间、空中等待时间、航班机型与停机位匹配、航班类型、数量与密度等优化目标的条件下，将有限的停机位资源快速合理地分配给更多的航班。这需要更加经济合理地使用机场固定设施资源，从而使停机位尽可能多地安排航班的停机位进行作业。

④最大化停机位效率

一方面，由于机场停机位是有限的，如果航班没有合适的近机位可供起降，就只能使用远停机坪，采用摆渡车上下旅客，增加旅客在机场停留的时间，也会增加地面作业成本，因此应寻求一种分配方案，使未分配至近机位的航班尽可能少。而最大化航班靠桥率是繁忙机场评价停机位分配方案的依据，航班靠桥率即停靠近机位的航班数量占航班总数的比例[7]。另一方面，为了最大化机场停机位利用率，飞机机型要与所停放的停机位大小匹配。如果当前暂时没有空闲机位，应该将到达的飞机先停放至远机位等待再次分配机位。由于机型与停机位不匹配将导致停机位资源的严重浪费，最大化停机位利用率、最大化靠桥率也就是最小化停机位资源的浪费[8]。因此，如何高效率地利用机场有限的资源也是国内外文献研究的热点。

⑤最小化停机位计划成本

机场进行停机位分配时会消耗一定的成本，如机场资源的使用成本，相关工作人员的调度成本。如何经济有效地利用机场有限的资源进行停机位分配是机场主体方常考虑的优化目标。

(2)旅客方面

①最小化旅客等待时间

在机场运行管理中，同一个时段可能会有多个航班起降，航班降落后停靠在相应的停机位，并随之进行清洁、加油、食品供应等一系列的地面作业，等到飞机准备就绪后再起飞，因为航班数量众多，机场的停机位可能不满足一对一的停靠。当前一航班降落并停靠至某一特定停机位完成地面作业起飞之后，后续的航班才能停靠在同一机位，因此优化目标需要考虑最小化航班延误时间，即一个时段降落的航班都安排在停机位停靠并且使航班延误时间最小，以此减少旅客候机时间，即提升旅客的满意度。如何最小化航班延误给旅客带来的影响也是大多数文献的研究热点。

②最小化旅客中转等待成本

该目标充分考虑航空公司的时隙互换性以及多航站楼的资源共享性，以最小化多方延误费用，降低航班延误引起的旅客中转等待成本，在航班波的环境下可以实现航空公司与机场的协同决策[9]。

③最小化旅客进离港行走距离

旅客到达或离开机场时，进离港的距离较先决定了旅客的行程体验，为提高服务质量，应减少旅客行走距离，为旅客带来便利。因此，关注旅客满意度的文献大都会使用该目标函数。

④最小化旅客转机行走距离

旅客由于不确定因素需要转机，为了给旅客提供方便，提高旅客满意度，最小化旅客转机行走距离的优化目标常被提及。

(3)航空公司

①最少化耗油量

燃油成本是航空公司最直接的运行成本，最少化航空公司的耗油量将降低飞机的燃油消耗，使机场的运营成本降低，其中减少航班在机场的滑行距离也会节省航空燃料。因此，国内外很多文献都从降低航空公司油耗成本角度考虑停机位分配问题。

②最小化总延误成本

在协同决策机制下综合考虑多方主体利益，建立多目标一体化停机位实时分配模型，考虑航班延误、飞机交换、空中等待等多方面成本，有利于从根本上节约成本。

③最小化场面滑行时间

目前对于停机位分配的研究主要针对机场的陆侧部分，但对于枢纽机场来说，旅客在机场飞行区的停留时间大大超过了航站楼内部行走所需的时间，这也是航班延误的主要原因。因此优化目标应考虑最小化场面滑行时间，以确保航班的正常运行。

④最大化航空公司的公平性

航空运输业作为高风险、高投入的资金密集型行业，降低成本对于每一个航空公司都具有非常重要的意义。近几年的文献非常关注航空公司之间竞争的公平性，且大部分从耗油成本和延误损失等方面考虑均衡的机位分配策略。

2 研究方法

停机位分配问题是近年来学术界研究的热点。该问题是一个NP-hard问题，其计算的时间复杂度随着机场和航班规模的增加呈指数增长，对于大规模问题在较短时间内难以获得最优解。停机位分配有许多分类方法，文献[10]研究了理论和实际的AGAP问题后将研究方法分为精确算法、启发式算法和元启发式算法；文献[11]把停机位研究方法按专家系统、数学规划和人工智能进行分类；文献[12]把解决停机位分配问题的文献总结为集中在建模算法上和集中在模型仿真上两种类型。本文从数学规划、智能优化和系统仿真三类方法来综述停机位分配问题的研究现状。

2.1 数学规划法

数学规划法是指将机场的各种约束规则，如航班类型、位置、航班时刻、机位类型等用关系式或符号表示，再根据实际情况建立相应的数学模型，最后从运筹学角度对优化模型进行求解[13]。数学规划方法的主要问题在于目标函数的选择，由于影响停机位的因素非常多，怎样综合考虑多种影响因素并提出符合实际问题的优化目标函数、快速地设计出有效的求解算法是当前研究急需解决的问题。早期的运筹学中的传统方法，如整数规划、混合整数规划、线性规划、非线性规划、动态规划、分支定界法等大都属于此类。基于单纯形法、分支定界技术和列生成法，一些学者提出了如图着色模型及算法、顶点着色模型及算法、排序算法等。

(1)整数规划

国外早期就对此方法进行研究，主要运用混合整数规划、0-1整数规划进行建模：文献[14]建立了基于混合整数规划的数学模型来解决机型指派问题；文献[15]研究了基于专门分支和定界程序的求解技术，同时提出基于大邻域搜索原理的改进方法；文献[16]在传统的确定性模型基础上，提出了0-1整数规划，用于航班在延误的情况下对停机位进行最优重分配，该计划最大限度地减少了进离港和中转旅客的总步行距离，但并未提出求解该模型的算法。近些年停机位分配建模逐渐开始关注鲁棒性问题，文献[17]就采用0-1整数规划方法来提高停机位分配问题的鲁棒性。因为NP-hard问题，大规模整数规划模型求解上一般需要借助其他智能算法。

国内对于停机位分配热点问题的关注稍晚于国外，早期文献[6]总结并分析了国内繁忙机场停机位分配情况和机场运行管理方式，并建立了以最小化更换停机位的航班数和机场恢复正常起降后分配到远机位的航班数之加权和为优化目标的整数规划模型。近五年内紧跟科研热点利用整数规划进行建模，许多文献开始关注旅客满意度，文献[18]建立了以停机位保障能力和客户满意度为目标优化模型，文献[19]-[20]以最小化旅客行走距离为目标建立了停机位分配优化模型，对旅客满意度的关注在一定程度上提升了机场的服务质量。还有一些文献则较为关注非正常运行情况下的停机位调度问题：文献[21]建立了以最小化航班延误时间为目标的整数规划模型对机场航班停机位调度进行研究；文献[22]从机场和航班非正常运行的角度出发，建立了混合整数规划模型并取得较好效果，解决了研究领域热点停机位实时分配问题；文献[23]把国际和国内航班的停机位作为研究对象，以最小化等待停机位的航班数量为目标建立了整数规划模型。对航班延误等非正常运行情况的研究大大提高了机场的运行效率，同时也使旅客满意度有所增加。另外，分支定界法作为一种较为常用的整数规划方法，较适用于变量数量和约束条件都较少的问题求解，但因为不能满足动态实时性要求而不适用于解决停机位分配一类规模较大的问题。

(2)图论相关方法

图论是用图示的方法把任务成员特征和接受任务成员特征描述出来，用图论的方法在任务和系统成员之间建立匹配，并据此设计出可行合理的任务分配方法。而图着色法是针对冲突图中的顶点来着色，在满足一定条件的情况下让任意2个相邻顶点不具有同样的颜色，且使所需要的颜色数最少，即停机位数量最少。

① 图着色模型及算法

图着色问题在调度领域应用非常广泛，目前已被应用于资源分配、货物存储、课表编排和频率分配，国外文献[24]-[25]提出了用图论方法来解决具有确定性和随机目标的停机位分配问题，并在后来的工作中针对同样的问题提出了可靠方法。国内有部分学者早期对图着色模型研究较多：文献[26]根据停机位排序模型设计出一种标号算法，并据此设计了顶点序列着色算法；文献[27]利用划片时间片算法将停机位分配问题转化为图定点着色问题；文献[28]使用时间冲突算法建立了停机位分配计划的顶点着色模型，结合图着色问题分解算法应用到具体的机场管理中，这种方法使机场设施资源更高效地被利用。但该模型主要关注使用停机位数量最少的目标函数，因此对所研究问题的范围有一定限制。最新的文献一般基于图论的思想来求解其他目标函数，文献[29]引入有向无环图并基于网络状态图建立了线性规划模型，设计了一个成本最小化和飞机使用均衡的目标函数。

② 多商品网络流模型

多商品网络流停机位实时分配模型把停机位映射为商品，这些商品在源节点和终节点之间通过众多到达节点和离开节点连接，当连接节点之间的弧可以利用时商品就会流经此弧，即停机位可以分配给该航班，否则不能分配给该航班。

国外文献较早将网络流理论运用到停机位分配中，针对暂缺飞机的实时扰动问题，文献[30]采用调机策略，并且对延误和取消策略分别建立了最小费用网络流模型，但是这两个模型只能单独使用。近年来大部分文献用其解决多目标优化问题：文献[31]对多商品网络流模型进行了分析，建立一种多目标鲁棒优化模型并将其转化为单目标优化模型进行求解；文献[32]基于0-1整数多商品网络流模型提出了最小化飞机滑行的燃油消耗成本和因再分配停机位而引起的乘客不适的优化目标，该方法在实际问题的分解方法中被证明计算效率很高；文献[33]创新性地建立了两个多商品网络流模型，该模型针对停机位再分配问题提出了一种有效的方法，并以最小化航班总延误的加权和、再分配的次数和延误转机乘客数量为优化目标，文献[33]中的模型是文献[34]的重大改进，虽然文献[34]提出了类似的网络流模型，但因为制定流量平衡的方式使决策变量的数量随着模型大小的增长而迅速增长，而抵消了多商品网络流模型所带来的高效率优势。由此可见，多商品网络流在大规模停机位分配应用中具有高效性，同时还可以对多目标优化问题有效求解。

国内学者主要将网络流模型与算法相结合来解决停机位分配问题。文献[35]研究了不正常航班的飞机调度和机组调度，建立多商品网络流的数学模型并采用算法进行求解，并最终得到了一种基于列生成法的合理的飞机调度法。文献[36]对列生成算法进行改进，将由于飞机资源短缺造成的不正常航班停机位分配问题视为带容量约束的多商品最小费用流问题，并建立了网络流模型。网络流理论和算法的结合使得停机位分配问题的求解速度有了进一步的提升。此后，文献[37]还将其应用在航线、机型调度中，建立了多机型一体化飞机排班的多商品网络流模型。最新的文献[19]也采用0-1整数多商品网络流模型，解决了乘客满意度不高和停机位再分配的延迟问题。

(3)混合集合规划方法

混合集合规划方法建模的一般步骤为：数据建模、逻辑建模和求解规则设计。混合集合规划方法首先通过约束推理对解空间进行切割，然后查询关键变量对解空间进行搜索，这使得关键变量从模糊变为确定[7]。

近几年国内个别学者开始关注此方法，并将其运用在繁忙机场和协同决策机制中。针对繁忙机场的停机位分配问题，文献[7]采用混合集合规划方法进行了数据建模和逻辑建模，运用自然约束语言编程设计出高效的求解策略，并以国内某繁忙机场为例进行求解，结果表明混合集合规划方法得出的分配相对于人工分配靠桥率提升了20.7%。文献[9]与[38]较为重视协同决策机制，从多区域多航站楼的角度出发，综合考虑机场、旅客和航空公司多方主体利益，借助混合集合规划方法建立了停机位实时分配模型以保障航班波有效衔接，并求解了该模型。停机位分配问题本身涉及机场、旅客、航空公司、空管等多方主体利益，因此混合集合规划法在机场协同决策中的应用对机场整体的运营效益非常重要。

(4)列生成算法

列生成算法将原线性规划问题分为主问题和子问题两部分。其中因为主问题包含的变量数目非常多，故需从中选择部分变量来构建一个限制主问题，通过对限制主问题求解得到对偶变量，并将对偶变量传递给子问题。然后对子问题进行求解，得出主问题非基变量的最小简约成本，如果最小简约成本为负，则把其对应的列加入到限制主问题中继续求解，直到最小简约成本大于等于零为止，此时即使得原问题最优。当限制主问题的解不是整数解时，采用分支定界法求出整数解。

对于列生成算法，国外文献主要在算法设计上进行创新。文献[39]通过对有限变量集的迭代线性规划求解，得到一个近似最优解，首先用列生成的方法求解整数规划松弛问题，发现一个限制集，在每一个列生成迭代中都会生成少量的附加列，并将其放入列集中，在线性规划松弛问题得到最优解后，利用列集中生成的列和所有附加列来解决线性规划问题。文献[40]还提出了使用列生成算法直接将航班分配给物理停机位的可能性。这些研究都为将来的应用研究提供了重要参考，但列生成算法的实施比较复杂，也一定程度地限制了该算法的应用。

国内文献较为关注求解速度，由于一般的列生成算法在每次迭代过程中只加入一个列，造成算法迭代次数过多降低了效率，因此文献[41]把具有相同性质的停机位划分为同一停机位类型，从而将停机位分配问题转化为选择适合航班对应机位类型的最佳停机位计划，并在此基础上建立了最大化停机位分配鲁棒性的数学模型，并采用列生成算法较快求得结果。近几年很多文献也在算法上进行改进，文献[36]在每次迭代中加入多个列，并对加入的多个列应该满足的条件进行分析，提高了该算法的效率，最后用实例验证了此方法的有效性和正确性。为了实现模型的有效求解，文献[37]提出了一种基于约束规划的动态列生成算法，该算法可以利用约束规划实现快速求解，计算各个航班串的简约成本，实现动态选择列集并与限制主问题进行迭代，该方法对提高航空公司盈利能力的现实意义非常重要。

2.2 智能优化算法

(1)遗传算法(Genetic Algorithm)

使用遗传算法，由于其生成的初始种群已经找到一定数量的可行解，即使问题规模变大，在要求时间内不能够完成规定代数的运算时，也可以中止运算，并得到较为优化的分配结果。另外，遗传算法具有并行性，解决问题时可以依赖这一特性增加物理投入来减少运行优化时间。

国外文献早期主要直接在停机位分配领域应用该算法，文献[4]运用遗传算法最小化航班等待时间。随着该算法的普及，部分学者将其与其他算法相结合应用，文献[42]结合遗传算法和蚁群优化(ACO)算法，以客运量、航空公司和机场运营的损失为目标，建立了停机位分配的数学模型，并提出了一种两级混合算法(GAOTWSH)用来解决延误航班停机位调度的数学模型，对非正常航班停机位再分配的数学模型进行了仿真和论证，为非正常航班飞行提供了一种新的方法和思路。很多文献将遗传算法应用到多目标优化模型中，文献[43]采用遗传算法针对停机位分配问题建立了多目标优化模型。最新文献[44]将第二代非支配排序遗传算法(NSGA-II)作为并行进化优化算法进行求解，与其他多目标算法相比在寻找较优解方面显示了良好的前景。

利用Citespace对近20年停机位分配领域的国内文献分析可以发现，国内学者最常用的算法就是遗传算法，且主要考虑在一些约束条件下对遗传算法的应用：文献[45]主要考虑航班衔接和过站时间要求，建立了航班串的数学优化模型，并构造了一种自适应遗传算法进行求解；文献[46]采用遗传算法对考虑安全运行约束的停机位分配模型进行有效求解；文献[47]以各航空公司飞机滑行耗油均衡为目标建立了停机位分配策略，采用遗传算法进行求解，证明了模型和算法的有效性。近年来部分学者也开始在遗传算法设计上进行改进，文献[48]引入了合作型协同进化遗传算法有效地解决了传统遗传算法种群多样性低、易早熟的问题。文献[49]设计了求解最小化航班延误成本模型的初始、改进遗传算法，而改进后的模型算法提供的停机位再分配方案更优。因此，对遗传算法进行改进或将其与其他算法相结合是未来该领域可研究的方向之一。

(2)禁忌搜索算法(Tabu Search)

禁忌搜索算法主要通过引入一个灵活的储存结构及其禁忌准则来避免反复搜索，用来避免此搜索陷入局部最优状态，该算法还通过藐视准则使部分被禁忌的优良状态得到利用，保证了多样化、有效地搜索来实现全局优化。其最重要的思想是对应已经搜索到的局部最优对象进行标记，并在下一步迭代搜索中尽可能避开这些对象。

1989年Glover教授提出了禁忌搜索算法，该算法是一种通过模拟人类智力的元启发式搜索技术，也是对局部邻域搜索算法的一种丰富。禁忌搜索算法对于大规模问题的求解有明显优势，文献[50]利用禁忌搜索算法来解决航班数量远大于可利用停机位数量时的停机位分配问题。文献[51]建立的随机规划模型是一个规模很大的混合整数规划，该模型采用禁忌搜索算法求解并取得了较好效果。随着禁忌搜索算法在该领域的逐渐应用，很多学者开始对其进行改进，文献[52]提出了一种新的禁忌搜索算法并与模拟退火方法作比较，证明了新提出的元启发式算法较优，并把开发出一种超启发式算法作为未来的研究方向，希望其根据实现的问题自动选择更有效的元启发式算法。

国内文献早期将禁忌搜索算法应用于应急停机位调度领域，文献[6]设计了禁忌搜索算法来实现计算机辅助停机位分配，解决了由于天气等特殊原因导致航班大面积延误情况时机场正常起降后的停机位应急调度问题。为综合考虑多目标优化问题，文献[53]建立数学模型并设计了求解该模型的禁忌搜索算法。经过不断发展，很多学者开始对该算法进行改进，并关注其对停机位分配鲁棒性的影响。文献[8]引入了改进后的动态禁忌搜索算法，并利用实例对此算法进行演算，证实了突出可变禁忌长度能够缩短全局寻优的循环次数，此算法可以得到更优的停机位分配方案。文献[54]也设计了求解模型的禁忌搜索算法对考虑缓冲时间成本停机位分配模型求解，提高了分配计划的鲁棒性。国内外很多文献[64]在实例中证明了禁忌搜索算法相对于其他经典算法的高效性，这也促进了其在停机位分配领域的广泛应用。

(3)蚁群算法(Ant Colony Optimization)

Dorigo等意大利学者在20世纪90年代初期通过模拟自然界中蚁群集体寻径的行为，从而创立了一种启发式仿生进化算法，被称为蚁群算法。国外文献对蚁群算法的研究主要关注高效率地获得全局最优解，为了在特定程度上减少蚁群算法陷入局部最优的可能，文献[55]提出了一种修正的蚁群算法，对转移概率进行了修正，并证明其可以有效地提高收敛速度。很多文献对蚁群算法的创新性应用深入研究：文献[56]将蚁群优化算法和遗传算法相结合，提出了一种两阶段混合算法，对延误航班停机位重分配问题进行有效求解；文献[57]在蚁群算法的基础上创新性地提出了一种基于全局最优候选的自适应人工蜂群算法用来求解全局优化问题；为了充分利用精英策略、最小最大蚁群策略、共生机制、混合机制和协同进化思想的优势，文献[58]也提出了一种新的自适应协同进化蚁群并设计了一种基于互补优势的优化算法(SCEACO)，该算法可以更好地获得有效的停机位分配结果，并且为解决复杂优化问题提供了一个新的思路。

为了避免启发式搜索容易陷入局部最优的情况，文献[11]设计了一种基于蚂蚁径路搜索规则的迭代寻优算法，即通过设置邻接矩阵，使每只蚂蚁在可行域内一步步构建优化解，最后验证了该算法的合理性。由于蚁群算法具有对扰动下停机位分配的优越性，大部分国内文献将蚁群算法应用到随机扰动下的停机位再分配中。文献[59]与文献[56]提出一种类似的基于蚁群算法和遗传算法的两阶段优化算法，并研究了基于两阶段算法的延误航班停机位再分配方案。而文献[60]对全局人工蜂群算法进行改进，并在实例中验证了其对随机扰动下停机位分配的有效性和优越性。近几年国内文献逐渐将蚁群算法应用到多目标优化模型中，文献[61]综合考虑旅客满意程度，机场和航空公司效益最大化而建立了枢纽机场停机位分配优化模型，提出了一种基于自适应协同进化蚁群优化算法的解决办法。文献[62]也采用蚁群算法对多跑道航班协同调度的多目标动态规划问题进行仿真取得较优结果，同时提高了多目标优化问题的求解速度。

(4)启发式算法

启发式算法通常建立在经验和判断的基础之上，通过尽量削减解的搜索范围，避免盲目搜索，同时又可以得到较好的近似最优解。但该算法并不保证一定可以找到最优解。从停机位分配问题的研究文献中可以看到，学者们开发出了多种启发式算法对该问题进行求解。

停机位分配问题本身可归纳为一种有限域约束满足问题(Constraint-Satisfaction Problem over finite domain)，文献[63]引入了进化启发式进化算法来解决CSP。国外文献往往将启发式算法与其他算法结合或对比，进而选出快速获得较优解的算法：文献[64]提出一个基于划分的搜索域编码使单个或多个航班再分配的两个邻域交换，最后结合禁忌搜索和局部搜索的启发式算法来解决最小化停机位再分配航班数量的问题；文献[33]提出使用两种启发式算法对模型进行求解，并对所提出的模型和算法进行测试，证实了所提出的方法可以在短时间内提供高质量解；文献[65]研究了三种经典的元启发式算法和一种混合算法，通过实例证明了混合算法在解的质量和计算时间方面更好，这为停机位分配的研究提供了发展方向。另外文献[66]还用Pareto模拟退火法解决了停机位的多目标分配问题。由此可见，对多种算法的混合使用可以大大提高求解速度，需要进一步研究。

近几年国内文献常对贪婪算法、模拟退火算法等启发式算法进行对比或结合使用，文献[67]设计了一种贪婪模拟退火算法用以求解枢纽机场的停机位分配问题，得到了一个未分配停机位的航班数量最少的初始解，并利用经典模拟退火算法求解得出最优分配方案。部分文献也对其他启发式算法进行设计，文献[26]引入机位标号函数和航班标号函数进而设计了一种停机位排序模型的标号算法。文献[35]设计了一种深度优先搜索的启发式算法应用到不正常航班的飞机和机组调度中，而该算法可以对被破坏的机组任务进行修复，使得飞机和机组任务配对在较短的时间内恢复正常状态。可见，启发式算法的丰富创新为不正常航班的快速恢复提供了解决方法。

2.3 系统仿真法

在获得基础数据以后，系统仿真法通过建立各种类型仿真系统，并使用仿真技术对机场的停机位进行实时模拟，主要为解决航班在停机位上的冲突控制问题[22]。

在系统仿真研究方面具有代表性的是Yu Cheng在1998年的研究，他提出对于繁忙机场来说，由于许多不确定性因素的影响，飞机在机场空侧区域经常会发生停放位置和运动轨迹冲突的情况，对于这个问题人为控制难以解决，必须充分利用仿真技术。为此，文献[68]分析了航班起飞和降落、进离港、登机门分配等活动及其相关控制过程，在此基础上提出了基于网络技术和规则的停机位分配仿真模型，来解决此类冲突控制问题。随后文献[69]提出了基于网络技术的仿真模型，模拟飞机的起降过程及其约束条件，用以避免飞机在跑道上的冲突。但随着航空运输业的发展，机场在对停机位预分配时就能提前避免大部分航班在停机位上的冲突，文献[15]也提到停机位分配的一个主流研究方向集中在仿真和基于规则的专家系统构建上，许多学者将注意力集中在所谓的基于规则的专家系统的设计上。此后国外文献偏向用仿真实验的方法对停机位分配规则和决策进行评估。文献[70]设计了一个仿真框架，用来分析随机航班延误对静态停机位分配的影响，并且达到了对缓冲时间和实时停机位分配规则评估的目的。文献[71]提出了一种基于仿真的实验方法，该方法可以在航班延误情况下计算出进离港航班所需的最小停机位数量，并且提出了一个因果模型来评估不同的停机位分配政策和策略在缓解不良后果方面的优缺点。

由于飞行区多跑道情况的复杂性，国内文献将计算机仿真应用在多跑道机场中。文献[72]综合考虑场面运行约束并建立模型，用以寻求场面滑行时间最短的分配方案，利用计算机进行仿真模拟，并与随机分配算法进行比较，仿真结果说明该算法降低了冲突探测与解脱次数，提高了多跑道机场的地面容量，还大大减少了航班延误时间。随后文献[73]利用机场的运行模式、地面网络数据以及航班计划等相关信息，用计算机仿真进行了算法设计，并借助编程语言进行了计算，将结果同机场地面容量评估系统中的停机位随机分配模型进行对比，表明仿真模型使得机场运行效率与资源配置情况得到改善，所提模型与算法比较有效。由于多跑道机场系统运行管理的复杂程度明显超过单跑道机场，文献[74]基于Flexsim仿真软件建立的飞行区仿真模型大大提升了航班滑行效率，在可接受延误水平下使得滑行系统服务航班量增加，当服务航班量超过容量时使得航班滑行的平均延误时间缩短。仿真软件的不断应用为解决多跑道机场的停机位规划问题提供了技术支持，提升了机场的运营效率。

2.4 三种方法对比分析

以上三种方法在停机位分配问题中较常使用，但各有优劣。数学规划法在理论上能够获得最优分配方案，但在运算时间上却不能够完全满足实际需要，当航班数量较多时，该方法往往得不到最优解或满意解，大部分研究都需借助优化算法实现快速求解。其次，该方法不够灵活，航班时刻发生的细微变化都会引起停机位分配的混乱，导致需要分配结果重新计算。

使用智能优化算法对问题进行求解花费时间较少、效率较高，但大多数算法未能考虑到延误航班对停机位分配的重要性，而且该类算法目的是在允许时间范围内在计算时间和解的质量之间折中计算出停机位分配问题的满意解，而不强求最优解，所以求解的结果是往往只能达到局部最优。其中每一种算法有自身的优缺点：遗传算法本身具有并行性，通过使用概率机制进行迭代而具有随机性，但是由于比较其依赖初始解的质量，搜索速度较慢，还需要对问题编码和最优解解码，编程较为复杂；由于禁忌搜索算法的局部搜索能力很强，故可以实现全局迭代寻优，且求解速度与其他经典算法相比较优，但其非常依赖初始化的局部领域；贪婪算法比较容易实现，计算效率较高，但得到的解往往也是局部最优解；模拟退火算法具有渐近收敛性，但很难控制其内部的参数，优化的结果很大程度上依赖参数取值。而混合算法相对于单个经典算法无论在求解速度还是求解质量上都有较大优势，并且在研究中为大部分学者所接受并使用。

而使用模拟计算机仿真技术可以对机场的停机位分配进行实时模拟，但必须保证模拟环境与实际环境较为相似。复杂系统问题很难用一般的数学建模方法进行建模，但是仿真技术可以通过采用智能体建模的方式将复杂系统中的各个要素以及各要素间的交互方式进行仿真，将复杂系统的微观行为和宏观现象进行有机结合，该方法是一种有效的、自底向上的仿真建模方式。

3 未来发展趋势

3.1 实现动态实时分配

根据机场实际操作过程所处的阶段不同，停机位分配问题可以分为停机位预分配和实时分配两种。停机位预分配在停机位分配信息发布之前就做好制作计划，而停机位实时分配则是对停机位当前的运行状态进行协调补充。然而目前国内对于停机位实时分配的研究还相对较少。停机位分配本身是动态的，它属于应急停机位调度范畴。在停机位动态运行的过程中，停机位的实时分配过程可能会受到天气和空中流量管制等因素的影响，当出现特殊情况尤其是航班延误情况下时，停机位预分配策略可能会失效而需要大量机位调整。当前在此类情况发生时，主要是依靠停机位分配员对当时情况的综合判断进行停机位再分配，缺乏科学理性的指导。所以提前做好停机位实时分配工作是停机位分配研究问题的发展方向。

3.2 采取多目标优化

根据国内外机场的特点，不同目标优化问题之间相互制约、相互影响，这就为多目标优化问题提供了现实依据，也印证了典型优化问题的局限性，因此在实际分析各优化目标的前提下应考虑采取多目标优化决策模型。停机位的多目标优化问题是机场调度研究的一个方向，因为需要考虑的因素较多，各种因素相互交叉，复杂性也较大。由于各优化目标之间往往存在着相互竞争的关系，如何科学地选择多目标函数，针对多目标优化问题进行深入分析，并设计合适的算法求解，在得到最优解的同时，又能缩短获得最优解的时间，是该领域未来研究工作中一个重点和难点。

3.3 合理赋予目标权重

由于机场运行过程的复杂性，一个停机位分配问题选取的多个优化目标并不能包含需要考虑的全部方面，这就需要结合单个目标进行细致的权重考量，才能使理论结果更具有意义。现有停机位分配文献中的优化目标大多为单目标优化，考虑多目标优化时赋予参数的权重也没有统一适用的方法，对于最优权重比没有科学有效的研究，通常都是凭经验选择。国内外文献对于多目标模型求解方法的研究很少使用线性加权法以外的方法，而线性单目标公式需要反复求解才能生成Pareto最优解，因此求解方法上还有待进一步的研究。

3.4 创新优化算法

在算法上，由于停机位分配问题是一个NP难问题，约束条件和目标函数不同就会有不同的优化解。解决这类问题而被广泛使用的智能优化算法有很多，这些算法都是通过不同的搜索方式来获得局部最优解，只是导致迭代次数和搜索的方向不同。因此，对于此类问题的算法研究中，应该结合问题本身的特点综合考虑各类因素，混合使用多种算法、创新算法或改进现有算法，在出现大量航班和停机位分配时才能取得更好的效果。在实际使用启发式的大趋势下，将这些算法结合起来是非常有意义的。

3.5 考虑不确定因素

在实际的停机位调度过程中不确定因素时有发生，在考虑这些不确定因素或参数存在的前提下对停机位的调度问题进行研究，是未来研究的一个热点。就停机位分配而言，可以尽量考虑预分配鲁棒性、航线性质、飞行任务、航班过夜、飞机的空中等待成本以及地勤工作人员的步行距离等更多的因素所产生的影响，并赋予合适的权重指标来进行合理评价，这样才能使停机位分配计划具有更强的鲁棒性。

3.6 考虑多方面可控因素

在进行停机位分配时如果不考虑飞行区域，分配结果很可能产生更多的跑道和滑行道冲突以及航班延误，造成机场地面容量变小。尽管通过仿真技术可以对机场复杂的场面交通进行引导，但机场的场面交通复杂多变，不但受到特殊航班、天气等不可控因素的影响，机场、航空公司和机组调度等多方面可控因素也会对机场场面的实际运行产生较大的限制，这些情况也是未来停机位分配问题研究的方向。

4 结论

随着民用航空事业的发展，停机位分配技术相关研究开始兴起，研究停机位分配对提高服务质量和机场运营效益具有极为重要的理论和实际意义。但国内针对这方面的研究起步较晚，也不够深入。本文对停机位分配问题的特征、优化目标以及研究方法上的研究进行了详细综述，为国内停机位相关研究提供了综述资料。最后分析了停机位分配问题未来在实时分配、多目标优化、算法创新等方面的发展趋势。