机场停机位分配问题仿真优化研究综述

刘畅 石丽娜 亓洋洋

摘 要：机位分配对机场的运营效率和航空公司的航班运营效率有着非常重要的影响，但国内目前很多机场的设施容量已经达到或接近饱和，而且机场扩建和设施资源增加的速度也远远满足不了航班需求，这在一定程度上造成了供需不足的矛盾。为提高机场服务水平、提高顾客满意度、有效利用机场资源，进而提高机场运营效率。结合国内外相关文献，从优化目标和优化算法两个方面为主体，对机位分配问题进行详细的梳理和综述，对研究动态进行分析和总结。并基于这两方面对目前停机位分配研究所存在的问题进行了分析，提供新的研究视角和研究思路，提出以考虑机场、航空公司、空管三方协同机制，将处理后的不可控因素作为约束条件，用更智能的优化算法模拟仿真可能成为未来的研究热点。

关键词： 优化算法;机位分配;研究综述;机场停机位;优化目标

【Abstract】 The allocation of aircraft space has a great impact on the operational efficiency of airports and airlines，the capacity of facility in many domestic airports has come close to or reached saturation point，and the airport expansion and the increase off facilities and resources are far from meeting the demand of flights，which caused the contradiction of inadequacy between supply and demand. To improve airport service， increase customer satisfaction and make use of airport resources to improve airport operation efficiency，this paper makes a detailed analysis and review of the allocation of machine space from the optimization of objectives and algorithms by referring to the relevant literature both at home and abroad， and also provides new research perspectives and thoughts. Based on these two aspects， the existing problems in the research of parking space allocation are analyzed to provide new research perspectives and ideas. It is proposed to consider the tripartite coordination mechanism of airport， airline and air traffic control， take the uncontrollable factors after treatment as constraint conditions， and simulate with more intelligent optimization algorithm， which may become a research hotspot in the future.

【Key words】  an optimization method; parking allocation; the research review; airport parking; the optimization goal

0 引 言

機场停机位作为民用航空系统中的重要设施之一，分配是否得当直接影响到机场的运行效率和旅客满意度，因此机位分配成为了国内外诸多学者研究的热点。笔者从停机位分配问题中的优化目标和优化算法两方面出发，对国内外机位分配相关文献进行了系统梳理，提出了国内外现研究的热点和盲点，深入总结了国内机位分配问题目前还存在的问题，并探讨了适合国内停机位分配的发展方向。

1 停机位分配问题的内涵

机场停机位分配问题（Airport Gate Assignment Problem）受诸多因素影响，其中包括：进港、离港航班的飞机机型、旅客登机、中转的行走距离、航班的数量和流量等。因此为每个进、离港的航班提供可为其服务的停机位就成为机场运行中的一个关键步骤。停机位分配问题从研究层面可总结为2类，对此可做分析阐述如下。

（1）是从预战术层面研究，指在飞机进入工作前，以某条件作为优化目标，对机场内各航空公司飞机进行预分配。例如，旅客最小行走距离、近桥率作为优化目标的停机位分配问题就可看作是预战术层面问题。

（2）是从运行层面研究，指在已经完成停机位分配时，由于天气等特殊原因，原停机位的分配不能满足实际运行所需，需要按照实时情况进行重新分配。例如，机位分配的鲁棒性可看作运行层面问题。

在国内外已有的文献中，不论是从预战术层面还是运行层面，均是从2个角度进行探讨研究。对此可做分析论述如下。

（1）是从旅客满意度角度考虑，即优化旅客在登机、转机等情况下的步行总距离和总周转所需时间。这样提高旅客满意度的同时，又能提高机场服务水平。

（2）是从机场运营者的角度考虑，以机位空闲时间、最近靠桥率等作为优化目标，可以提高停机位预分配方案的鲁棒性、降低机场运营成本，减少很多地面复杂化所带来的成本。

但实际的研究中，也会有学者同时从2个角度着想，因为如果单方面考虑旅客行走距离，而不从机场运营者角度考虑，则会造成部分机位过于繁忙，部分机位空闲;如果单方面从机场运营者角度考虑，则会造成旅客满意度下降。通过查阅近期文献发现，还有学者开始从机场运行安全的角度研究该问题。随着对机位分配的研究越来越深入，人们研究的角度也越来越丰富。本文对国内外关于停机位分配问题从优化目标进行了全面汇总，即如图1所示。

从优化目标角度，多数学者默认机位分配问题是在资源充足的条件下，以最小旅客行走距离、最小机位空闲时间及最近靠桥率为主要优化目标进行研究。近几年，有学者认为应结合机场实际运营情况，考虑资源不受限以及多目标优化。

2 停机位分配问题优化算法

停机位分配问题多涉及组合优化模型的研究，对于那些存在n个需要置换的元素，最终组合的结果会有n！个。对于较小的n值，可以进行一一筛选，但如果n是一个较大的数值，那么组合的结果就会非常地多。能否妥善处理停机位分配问题，在于能否合理地选择求解方法。对于停机位分配问题（即NP问题）的求解方法，一般分为两大类。一类是精确算法，其中的大部分为运筹学中的优化算法，该类算法出现比较早，在停机位分配问题初期，学者对该算法的应用频率很高。很多研究也表明，精确算法可以有效解决停机位分配问题。该算法包括：整数规划、分支定界法、线性规划、动态规划、单纯型法、线性松弛法、列生成算法等。此外，排序算法、图着色算法、顶点着色算法也属于精确算法的范畴，但是这几种算法相对来说应用较少。另一类是启发式算法（又称近似算法），主要包括：遗传算法、模拟退火算法、禁忌搜索算法等。

随着优化目标的不断推新，启发式算法逐渐成为停机位分配问题的主流解决方案。由于单一算法的局限性较大，不能充分地解决机位分配问题，因而有学者将2种算法相结合，精确算法之间、启发式算法之间、或精确算法与启发式算法相结合，用此算法来弥补彼算法的不足，从而更好地解决机位分配问题。

事实上，停机位分配问题是典型的非间断性问题，没有起始和结束点，问题的解无疑就成为了一个无限的离散系统，这样的问题解决起来会有一定的难度。因此有的启发式算法在求解停机位分配问题时会加入初始状态，得到局部最优解，大大降低研究难度，这也是近年来启发式算法成为研发焦点的重要原因。

针对停机位分配问题，查阅历年来的文献可知，研究该问题的学者大部分在都在使用近似算法，算法的结合也多数选择在近似算法中选择算法两两结合，为更好地研究各算法的优缺点以及停机位分配问题中的应用，将常用的数种算法经过整合分析后得到结果列表，详见表1。

3 停机位分配问题的研究

停机位分配问题的研究角度已经多样化，Braaksma和Shortreed（1971）[1]是最早将旅客最小行走距离作为优化目标来研究机位分配问题的学者。也就是从此时开始，国内外航空学者意识到机位分配问题在日后航空发展中的重要作用，同时也深刻认识到优化目标和优化算法在解决实际问题时的重要性。因此，后来的研究学者不断地在优化目标和优化算法上寻求做出改进与创新。对这部分研究内容，本文将给出重点论述如下。

3.1 机位分配问题的优化目标

在优化目标问题的研究上，由于停机位分配问题涉及旅客、机场、空管和航空公司，从不同的方面入手，可以设计不同的目标函数。主要包括如下几个方面：从旅客的角度出发，可以以旅客最小步行距离为优化目标，也可以旅客的等待时间最短为优化目标。在国内外的大型枢纽机场，有学者还以中转旅客的利益为主要讨论对象。从提高机场机位利用率角度出发，可以最小化机位空闲时间和最小化远机位数作为优化目标。从航班延误角度，可以最小化航班延误时间或以航班延误时间均衡为优化目标。上述几种为停机位分配问题中优化目标的主流选项，但近几年，有学者另辟其径，以最小化航班-机位匹配差异度作为优化目标，或在优化目标的选取中考虑了不同类型航班的单位时间延误成本等因素，也有不小的成果。为此，本文拟展开研究分述如下。

3.1.1 以最小旅客行走距离为优化目标

在进行机场的航站楼设计时，旅客在登机、转机等情况下的步行总距离和总的周转时间是需要详细考虑的因素，不仅影响到旅客登机的方便性和满意度，同时也是机场运行中的重要评价指标之一。

对此方面的研究主要是通过合理的路径固化，在航站楼步行距离这一指标上进行定量研究，并以此作为参考来做出停机位分配。

在以最小旅客行走距离为优化目标的研究中，Babic等人（1984）[2]、Mangoubi等人（1985）[3] 、Haghani等人（1998）[4]、Bihr（1990）[5]都把機位分配问题作为一个整数规划问题进行研究。其中，Babic等人[2]、Mangoubi等人[3]采用的是整数规划算法，分别使用分支定界法、线性松弛算法进行求解;而且Mangoubi等人[3]在Babic等人[2]没有考虑中转旅客的基础上，改进了优化目标，增加了中转旅客的出行特点。Haghani等人[4]则采用启发式算法来求解描述为整数规划问题的机位分配问题。

Yan等人（1998）[6]选择将机位分配问题描述成一个多重的网络流问题，采用了拉格朗日算法进行求解。

Ding等人（2004）[7]考虑到资源受限的情况，在繁忙的高峰时期跑道、机位也会供不应求。因此在机场中虚拟一个可同时为多架飞机服务的停机坪，并将分配到远端停机坪航班数量和旅客行走距离相结合作为优化目标，分别采用贪婪算法和禁忌搜索算法进行求解，在一定程度上解决了在资源受限情况下的停机位分配问题。

Diepen等人（2012）[8]、Yu等人（2014）[9]均以某特定机场为例，最小旅客行走距离作为优化目标进行研究。

3.1.2 以最小机位空闲时间为优化目标

随着机位分配研究的深入，有一些学者不再只考虑以旅客最小行走距离为优化目标，而是不断地改进优化目标，于是就出现了另一种备受瞩目的优化目标，即最小机位空闲时间为目标的研究。

Balat（1996、1999）[10-11]、Andrew等人（2005）[12]、田晨等人（2005） [13]、卫东选等人（2008）[14]、王笑天（2015）[15]均以最小化机位空闲时间作为优化目标，解决机位分配问题。但是每个学者对同一个优化目标采用的优化算法各有千秋。

其中，Balat[16]采用分支定界法和启发式算法，而后在2001年又再一次对该问题予以深度剖析，认为机场的停机位分配问题需要对集中优化目标进行详细分析，探讨了遗传算法在停机位分配问题中的应用。Andrew等人（2005）[12]认为在实际运行中，航班进港、离港的时间受天气等特殊情况的影响，因此需要考虑停机位分配的鲁棒性，建立了一个基于计划航班时刻表的模型，以实时运行中最小化停机位上航班冲突次数为优化目标，采用禁忌搜索、局部搜索组合算法进行求解。田晨等人（2005） [13]，卫东选等人（2008）[14]和王笑天（2015）[15]在选择最小化机位空闲时间作为优化目标时，均做了适当的改进。具体来说，田晨等人采用遗传算法优化空闲时间段方差，卫东选等人采用贪婪算法优化空闲时间段的离差，王笑天采用列生成算法来最小化所有停机位空闲时间段的离差平方差。在满足停机位预分配求解速度的前提下，提高了解的精度。

3.1.3 以最近靠桥率为优化目标

由于航班被分配至远机位时，会给航空公司和机场增加很多运营成本，例如在进港时停在远机位的航班需要配置摆渡车，还有其余地面作业复杂化所带来的额外的费用。摆渡车的设置不仅增加旅客离机所需的时间，降低了旅客满意度，还会增加机场的运营成本。因此近些年，很多研究学者开始在优化目标上引入了最近靠桥率这一条件，在停机位分配问题研究上颇有成果。如王岩华（2015）[17]和李倩雯（2018）[18]均以最近靠桥率为优化目标，运用基本遗传算法及改进的免疫遗传算法进行求解。

3.1.4 多目标优化

由于机位分配的研究越来越多，人们不断在优化目标上推陈出新，出现了将优化目标两两组合作为多目标的优化研究，但由于难度较大，这类研究相对比较少。

其中，鞠姝妹（2008）[19]，卫东选（2010）[20]均把旅客最小行走距离和最大靠桥率结合在一起作为优化目标。鞠姝妹采用的是贪婪算法和模拟退火算法，卫东选采用的是初始化算法和禁忌搜索算法;李军会等人（2011）[21]将停机位空闲时间、最小旅客步行距离相结合作为优化目标，采用贪婪-禁忌搜索算法来解决所构建的机场停机位指派模型;李峰（2011）[22]把机位空闲时间均衡和机位使用效益最大相组合作为优化目标，运用线性变换、遗传算法来求解所建立的机位分配模型。

尽管从优化目标角度来说，主流仍是旅客最小行走距离、最小机位空闲时间和最近靠桥率，但还是有个别学者进行了一定的创新尝试。Yan等人（2001）[23]、Hu 等人（2008、2009）[24-25]考虑在机位资源短缺时，会造成旅客等待的时间增加，因此从降低航班延误的角度出发，将此作为重要的优化目标。

3.2 机位分配问题的优化算法

在研究机位分配优化问题时，前述学者把研究焦点放在优化目标上，把优化算法仅仅作为一个工具，还有一部分学者则将重心放在了优化算法的研究上，以便验证不同的优化算法在机位分配问题上带来的不同效果。而且多数学者也不再只局限于使用单一的启发式算法或精确算法，而是将算法两两结合，能更好地弥补单一算法的不足。

Ding等人（2004）[26]分别用了模拟退火算法、禁忌搜索算法，以及2个算法相结合改进后的模拟退火-禁忌搜索算法做了3次研究，结果表明改进后的算法更能够高效地解决机位分配问题。

随后，Lim等人（2005）[27]，刘兆明等人（2007）[28]，Marinelli等人（2016）[29]分别采用文化基因（Memetic）算法、遗传算法、基于生物地理学的蜂群算法，解决机位分配和滑行道分配问题。

不难看出，在以优化算法为中心的机位分配问题研究中，除了学者们不断地推出更为先进智能的算法以外，组合算法正成为学界的一种潮流与方向。

刘长友等人（2006）[30]在遗传算法中选择加入近似算法中禁忌搜索算法的思想。孔佳玉（2008）[31]在已有的遗传算法的基础上对整数编码方式进行改进。

值得一提的是，有学者在选择多目标进行优化时，将地面运行安全问题也纳于其中。由于国内繁忙机场的航班量不斷增加，机场地面交通日益拥堵，飞机进出停机位变得频繁，地面冲突情况在日后可能会非常普遍，一旦发生地面冲突，对于机场的运行效率和航空公司都有很大的影响。因此从运行安全的角度出发，考虑3种飞机滑入-推出停机位时可能会发生的冲突情况，加入对全时段航班处理，对始发航班、过站航班和过夜航班的整体性处理。较之不考虑鲁棒性和最小化空闲时间离差平方和的停机位分配，此方法大大降低了航班冲突情况。

4 机位分配问题研究的焦点和存在的问题

由于实际机场运行是一个非常复杂的过程，所涉及的因素也是多种多样，因此并不存在一个完全适合的停机位分配方案，在实际运行时，也是理论结合实际灵活选用各类操作。基于本文对停机位分配问题的研究综述，可以得出如下结论：

（1）现有的研究在优化目标上多数还停留在单一的优化目标，即使是多目标优化，也是以旅客行走距离最小化为首要优化目标，再结合其它目标建立多目标优化模型。这在一定程度上反映了停机位分配问题的研究必须以旅客效益为首要目标，在此基础上才是兼顾其它方面的效益。

（2）在建立优化模型的约束条件时，很多学者考虑到可行性，剔除了一些不可控或不确定的约束条件，导致优化结果并不能反映实际的机场停机位分配现状。

（3）在算法研究上，由于精确算法出现较早、应用较为广泛，因此学者多采用精确算法进行求解，对于启发式算法主要采用的还是遗传算法、贪婪禁忌算法等。

（4）在现有研究停机位分配问题的文献中，多数学者在研究时，就已经假定机场设施资源是不受限的。即认为停机位的数量是充足的，在有任意一个航班进港、离港时，总存在一个可利用的停机位为其服务。

（5）国内外对于停机位实时分配的研究还相对较少，由于会受到天气和航空管制的因素，在出现特殊情况而导致航班大面积延误时，停机位的预分配方案就会失去效果。

5 结束语

目前及未来空域的限制、机场容量、机场构型的复杂性、航班运输量的增长依旧会使这种供需不足的矛盾继续突出，说明机场停机位分配问题仍然面临许多挑战。根据现有的研究角度和方法，以及存在问题，未来在此問题上亟待改进与完善的研究内容主要包括：

（1）组合优化目标。既要考虑旅客效益，又要考虑机场运行效益、某些大型枢纽机场的布局，以及机场的运行安全。此外，还要顾及航空公司、空管等在停机位分配问题上具有一定主导意见的主体。机场是一个涉及各种资源的复杂交通系统，许多资源的分配是在停机位分配的基础上实现的，可与其它资源进行协同调度研究。

（2）由于技术手段的优化，以往研究时的不确定因素或不可控因素可以通过现有方式进行加工处理后将其作为约束条件，建立优化模型，更能反映实际运行情况。

（3）随着计算机科学技术、人工智能、大数据等技术快速发展，可以考虑运用更智能的优化算法进行模拟仿真。

（4）由于国内机场航班量不断增加，地面安全问题也应列入研究考量中。除了飞机的推出-滑入冲突以外，还包括飞机与摆渡车的机场地面保障车辆的冲突问题，需要予以详尽分析研究。

（5）随着民航业的发展，国内各大机场吞吐量不断突破新高，机场建设相对来说比较迟缓，特别是在高峰时段和大规模延误的时候，跑道、停机位等固定资源便会出现容量不足的情况。且国内外停机位实时分配的研究相对较少，一旦发生延误情况，主要是靠停机位分配员根据实时情况自主调配，缺乏科学性。因此，考虑资源受限条件和停机位实时分配方案的停机位分配问题尽管相对来说难度较大，研究成果也还不多，毋庸置疑这将是未来机位分配问题的研究热点。

参考文献

[1]BRAAKSMA J P，SHORTREED J H.Improving airport gate usage with critical path[J].Transportation Engineering Journal of ASCE，1971，97（2）：187-203.

[2]BABIC O，TEODOROVIC/ D，TOSIC V.Aircraft stand assignment to minimize walking [J].Joumal of Transportation Engineering ，1984，110（1）：55-66.

[3]MANGOUBI R S ， MATHAISEL D F X . Optimizing gate assignments at airport terminals[J]. Transportation Science， 1985， 19（2）：173-188.

[4]HAGHANI A，CHEN M C.Optimizing Gate Assignments at Airport Terminals[J].Transportation Research Part A：Policy and Practice，1998，32（6）：437-454.

[5]BIHR R A. A conceptual solution to the aircraft-gate assignment problem using 0， 1 linear programming[J]. Computers & Industrial Engineering，1990，19（1/2/3/4）：280-284.

[6]YANV S ， CHANG C M . A network model for gate assignment[J]. Journal of Advanced Transportation， 1998，32（2）：176-189.

[7]Ding H ， Lim A ， Rodrigues B ， et al. Aircraft and gate scheduling optimization at airports[C]// Proceedings of the 37th Annual Hawaii International Conference on System Sciences.Washington， DC， USA ： IEEE， 2004：1-8.

[8]DIEPEN G ， AKKER J M V ， HOOGEVEEN J A ， et al. Finding a robust assignment of flights to gates at Amsterdam Airport Schiphol[J]. Journal of Scheduling， 2012， 15（6）：703-715.

[9]YU C H ， LAU H Y K . A hybrid algorithm for solving gate assignment problem with robustness and tow considerations[M]//BRAMER M， PETRIDIS M.Research and Development in Intelligent Systems XXXI. SGAI 2014. Cham：Springer， 2014：269-279.

[10]BOLAT A， AS-SAIFAN K. Procedures for aircraft gate assignment[J].Mathematical&Computational Applications，1996，1（1）：9-14.

[11]BOLAT A. Assigning arriving flights at an airport to the available gates[J].Journal of the Operational Research Society，1999，50（1）：23-34.

[12]LIM A，WANG Fan.Robust airport gate assignment[C]//17th IEEE International Conference on Tools with Artificial Intelligence （ICTAI 2005）. Hong Kong， China：dblp，2005：74-81.

[13]田晨，熊桂喜.基于遺传算法的机场机位分配策略[J].计算机工程， 2005，31（3）：186-188，228.

[14]卫东选，刘长有.机场停机位分配问题研究[J].交通运输工程与信息学报， 2008， 7（1）：57-63，69.

[15]王笑天.机场停机位分配优化技术研究[D].南京：南京航空航天大学，2015.

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

[17]王岩华.繁忙机场机位分配的混合集合规划方法研究[D].南京：南京航空航天大学，2015.

[18]李倩雯.机场停机位优化分配模型构建[D].北京：北京交通大学，2018.

[19]鞠姝妹.枢纽机场停机位指派的算法优化与仿真[D].南京：南京航空航天大学， 2008.

[20]卫东选.基于运行安全的机场停机位分配问题研究[D].南京：南京航空航天大学， 2010.

[21]李军会，朱金福，高强.基于贪婪禁忌算法的停机位指派问题研究[J].交通运输系统工程与信息， 2011， 11（4）：173-179.

[22]李峰. 民用机场停机位资源分配方法优化研究[D]. 德阳：中国民用航空飞行学院， 2011.

[23]YAN S ， HUO C M . Optimization of multiple objective gate assignments[J]. Transportation Research Part A （Policy and Practice）， 2001， 35（5）：413-432.

[24]HU Xiaobing，Ezequiel Di Paolo.Genetic algorithms for the airport gate assignment：linkage，representation and uniform crossover[M]//CHEN Y， LIM MH.Linkage in Evolutionary Computation. Studies in Computational Intelligence.Berlin/Heidelberg：Springer， 2008，157：361-387.

[25]HU Xiaobing，PAOLO E O. Anefficient genetic algorithm with uniform crossover for the multi objective airport gate assignment problem [M]//GOHC K， ONGY S， TANK C. Multi-Objective Memetic Algorithms. Studies in Computational Intelligence. Berlin/ Heidelberg：Springer，2009，171：71-89.

[26]DING H， LIM A， RODRIGUES B， et al. New heuristics for over-constrained flight to gate assignments[J]. Journal of the Operational Research Society， 2004， 55（7）：760-768.

[27]LIM A， RODRIGUES B， ZHU Y. Airport gate scheduling with time windows[J]. Artificial Intelligence Review， 2005， 24（1）：5-31.

[28]刘兆明，葛宏伟，钱锋.基于遗传算法的机场调度优化算法[J].华东理工大学学报（自然科学版）， 2008， 34（3）：392-398.

[29]MARINELLI M， PALMISANO G， DELLORCO M， et al. Optimizing airport gate assignments through a hybrid metaheuristic approach[M]//ZAK J， HADAS Y， ROSSI R.Advanced Concepts， Methodologies and Technologies for Transportation and Logistics. EURO 2016， EWGT 2016. Advances in Intelligent Systems and Computing.Cham：Springer，2016，572：389-404.

[30]刘长有，卫东选.基于遗传算法的机场停机位分配问题研究[C]//中国控制与决策学术年会论文集.中国天津：《控制与决策》编辑委员会，2006：1077-1080.

[31]孔佳玉.机场机位分配建模及其遗传算法研究[D].南京：南京理工大学， 2008.