机场机位分配的一种实用方法

杨 越，王 犇，刘 杨

（1.中国民航大学空中交通管理学院，天津 300300；2.西安咸阳国际机场现场运行中心指挥室，西安 712035；3.天津市博盈科技发展有限公司，天津 300200）

机场停机位分配问题是指综合考虑航班和机位信息，为未来一段时间内的进港和离港航班指派合适的停机位资源，是机场现场指挥室的重要工作内容之一[1]，国内很多学者分别采用不同方法进行了多角度的探讨和研究。文军[2-3]根据“先到先服务”的原则，通过引入机位标号函数和航班标号函数设计了一种停机位排序模型的标号算法，并给出了机位分配的顶点序列着色算法；鞠姝妹[4-5]设计了一种贪婪模拟退火算法，以求解枢纽机场的停机位指派问题，该算法首先可得到使丢失“航班数”最少的初始解，随后采用经典模拟退火算法求解出最优的指派结果；王力[6]提出结合考虑旅客登转机时间、机型与停机位类型匹配、航班类型、航班数量与密度、停机时间为优化目标的数学模型，设计了求解模型的禁忌搜索算法。尽管算法研究层出不穷，但目前国内的多数机场仍然采用人工指派机位的方式，即以每日的航班时刻表为依据，对进场航班进行手工的机位指派。其原因有二：一是算法理论过于复杂，不适合现场指挥人员的工作需求；二是多数算法未考虑到延误航班对机位指派的重要影响。因此，制定一种实用且可靠的机位指派方法符合目前机场发展的要求。本文提出了一种机位预指派的搜索算法，并设计了针对延误航班的机位再分配方案，以解决延误航班对预指派结果的干扰问题。

1 研究方法与结果

1.1 机位预指派方法

停机位指派是经典指派问题的一种变形，涉及到各航空公司的航线类型、机型、航班数量、航班密度、停机时间、旅客步行距离等多方面因素。合理编制停机位分配计划是机场现场运行中心完成作业任务的核心工作之一。建立停机位分配模型并设计相应的算法是实现计算机辅助编制停机位分配计划的重要内容。为此，需要建立关于机场停机位分配问题的数学模型和算法。一般而言，构建机位指派模型需要已知的条件包括：①机场终端区域的规划和停机位的数量；②每日的航班时刻表，即当日每架飞机的进港、出港时间；③每架飞机的机型、所属航空公司等属性。

1.1.1 目标函数和约束条件

由于机场机位指派涉及到旅客行走距离、航空公司的经济效益、机场资源的有效利用和地面服务部门的工作场所等多个方面，因此从不同角度出发可以得到不同的优化模型。本文主要以提高机场的运营效益和服务质量为目标，设计预分配算法时主要考虑以下两个方面：

1）运营效益目标函数：为提高机场的桥位利用率（靠桥率），以达到近机位利用率最大为优化化目标

其中

z为当日航班总量。

2）服务质量目标函数：为缩短进出港旅客的步行距离，以旅客步行距离最短为优化目标

其中：ri表示航班i的旅客数。由于在机位指派前各航班的旅客数未知，本文采用不同机型的最大座位数e与各航班的客座率u的乘积来表示所研究机型的旅客数，即

其中：dk表示停机位k至安检口的距离。在此假设所有旅客从安检口到停机位所走的路线是一致的，即同一个航班的所有旅客在进登机口时所走的距离是相等的。若机位为远机位，距离则统一取一个稍大的值1 000 m。

机场停机位指派的约束条件是由停机位指派的规则转化而来。具体指派停机位时，在一日的不同时间段内，由于进港和离港的航班种类、数目和时间不同，确定航班使用停机位的种类和时间也就不同。本文所考虑的限制约束条件主要包括5个方面：

1）航班唯一属性约束：每个进港航班只能分配一个机位

其中：M为待分配机位集合；N为当日航班集合。

2）机位唯一属性约束：每个机位一次只能指派给1架飞机

3）机型属性约束：停机位只能停放与其匹配机型的飞机。例如：机场的部分机位可以停放机型为E类的大型飞机，一些机位只能停放C类及以下的小型飞机

4）航线属性约束：停机位与所停航班的航线属性匹配。例如：多数中小机场的大部分停机位只停放飞国内航线的飞机，少量机位可停放飞国际航线的飞机

5）航空公司属性约束：停机位与航空公司属性匹配。为方便地勤服务需求，机场会要求不同航空公司的航班停放在其专属的机位

1.1.2 机位预分配算法设计

在本文涉及的算法中，要求预指派的机位在满足上述各约束条件的基础上达到提高近机位利用率和缩短旅客步行距离两个目标，并且根据航班到达机场的时间进行先到先服务的排序，以尽量减小本场的延误时间。算法的计算步骤如下：

1）根据当日航班时刻表，将所有进港航班和出港航班按到达本场和从本场出发的发生时间的先后重新排序。为提高机位的利用率，当到达与出发航班同时发生时，总是安排出发航班在前。

2）整理当日机位的初始占用情况，将已占用机位标记为koccupied，将空闲机位标记为kfree，并将每个机位的机型属性Pk、航线属性Qk和公司属性Tk按照本场要求赋值。

3）顺序读取已排序的航班。若航班Fi为出港航班，则释放当前Fi所占用机位k，将该机位标记为kfree，并令Mfree=Mfree+1。若航班Fi为进港航班，则找出一个空闲机位k∈Mfree，使其满足

若满足上述条件的机位k存在，则赋值该航班的机位号为Flt（i）=k，将该机位标记为koccupied，并令Mfree=Mfree-1；如果符合上述条件的机位不存在，则在当前所有空闲机位Mfree中，寻找机位k，使其满足

若满足上述条件的机位仍不存在，则令Flt（i）=0，分配结果显示“再分配”。

4）按顺序读取下一航班，重复步骤3）。

5）直至处理完最后一个航班，输出Flt（i），i=1，2，…，N。

该算法的流程如图1所示。

图1 机位预分配算法流程图Fig.1 Process of gate pre-assignment algorithm

1.1.3 预分配算例分析

算例采用中国主要干线机场之一的西安咸阳国际机场在2012年某日10：00—12：00时段内40个按飞行计划执行任务的航班数据，所研究的机位范围如表1所示。

表1 咸阳机场停机位的统计数据Tab.1 Statistic of gates in Xianyang Airport

涉及的算法按照图1所示的流程在Matlab7.0的运行环境下编程实现，结果如表2所示。其中，计划进港时间指按照当日的航班时刻表进入咸阳机场的时间；预计进港时间指根据前方机场起飞时间和相关情报预计到达咸阳机场的时间；预计离港时间指根据预计进港时间和计划过站时间推断的航班能够从咸阳机场起飞的时间。预分配是指由预指派算法分配的机位；实际分配是指现场指挥室工作人员实际手工分配的机位。表中的0时刻作为起始时间，表示上午10：00。括号中的数值表示该停机位距离安检口的直线步行距离的粗测值。

预指派算法按照先到先服务的原则，根据航班计划进离港的时间顺序进行排序，以实现航班的机位自动指派，同时满足规定的机型、航线和航空公司的属性约束。若分析某一航班，预指派算法的计算结果可能不比指挥室的实际指派结果更为优化，如5号航班被指派到了远机位144，旅客需步行1 000 m；实际指派机位为107，旅客需步行280 m。这是因为该算法根据当前所有机位的空闲状态来对航班进行分配，可能会产生某些步行距离短的近机位已被占用的情况，从而影响了航班的机位指派效果。但是，由于算法在对每个航班进行分配时，都是以近机位占用为原则，在此基础上以旅客步行距离最小为优先考虑的，因此从全天运行的近千架航班来整体对比分析，所要求达到的优化指标足以保证。为此，给出了2012年某一周内所有按计划执行飞行任务的航班的机位预指派结果，比较了预分配算法与实际指派结果在靠桥率和旅客步行距离这两个关键指标的表现，如表3所示。

表 3中数据是按照式（1）、式（2）的计算方法，以反映机场运营效益的指标靠桥率和反映机场服务质量的指标旅客步行距离来分别评价算法和实际分配结果的。可以看出，在所研究的时间范围内，算法分配的靠桥率均高于实际的指派结果，如图2所示；算法分配的旅客步行距离均小于实际的指派结果，如图3所示。按照航班计划表中的计划进出港时间排序后的算法在靠桥率指标上提高了5.1%，步行距离指标上提高了8.3%，说明该算法比手工分配机位的方式更能提高机场的运营效益和服务质量。

表2 2012年某日10：00—12：00时段内计划航班的机位预指派结果Tab.2 Result of gate pre-assignment according to airline flight plan during 10：00-12：00 on someday in 2012

表3 预指派算法与实际指派机位的比较结果Tab.3 Comparison of gate pre-assignment between algorithm and practice

1.2 机位的再分配方案

图2 算法与实际指派结果的靠桥率比较Fig.2 Comparison of utilization ratio of near gate between algorithm and practice

图3 算法与实际指派结果的旅客步行距离比较Fig.3 Comparison of ambulation distance for passengers between algorithm and practice

停机位的再分配是指在对航班作好初始机位分配计划的基础上，根据实时航班时刻的变化，对机位分配方式进行相应调整，使得分配更加合理。一般是在确定了延误航班新的进/离港信息的情况下，对其及相关航班的停机位预分配结果进行相应微调[7]。目前，国内多数机场采用人工指派机位的原因之一就是由于延误航班较多，若完全按照预分配的方案提前将机位分配好，在实际运行中需要调整的机位也较多。因此，在机位预分配的基础上，设计一种能够自动对延误航班进行再分配的方案，不仅能减轻指挥室人员的工作负荷，也能在一定程度上提高机场的运营效率。

1.2.1 延误航班的界定

延误航班是指由于各种原因未能按计划时间进港或离港的航班，由于不同机场的运行方式不同，对延误航班的具体界定标准也不尽相同。目前，多数机场现场指挥室对延误航班的界定如下：

1）进港延误：若航班在前方机场的实际起飞时间晚于计划30 min，则将其视为延误航班；

2）出港延误：

a）与进港航班相关的延误：若未进港的航班已有预达本场时间，则预达本场时间+过站时间晚于本场计划出港时间的航班视为延误；若未进港的航班直到计划离港前30 min仍无预达本场时间，则将其视为延误航班；

b）与进港航班无关的延误：若航班按计划时间进港，但由于目的地机场、天气、航路限制、飞机故障等原因无法按计划离港时间起飞的，则视为延误。

延误航班必然会对预指派的机位产生干扰。对于进港延误航班，若不及时更换原分配机位，则会使此机位长时间被无效占用，降低了机位的利用率；而出港延误航班会使预分配方案中占用此机位的后继航班受到影响，从而打乱机位预指派方案。本文针对有预计进港时间和离港时间的延误航班，设计了相应的机位再分配算法，解决其对预指派机位的干扰问题。

1.2.2 机位再分配算法设计

当确定了延误航班后，就要采取措施对延误航班及其后继航班的机位预分配结果进行相应的调整。本文采取的策略为：针对延误航班，仍然按照预分配的方案进行机位指派，即保持原机位指派结果不变（除非是返航或备降的航班，则直接释放预分配机位）；而对于与延误航班占用相同机位的毗邻后继航班，则根据后继航班的计划进港与离港时间，选择是否对其重新分配机位。算法的计算步骤如下：

1）根据机场的延误航班界定标准，确定延误航班及其毗邻后继航班；

2）根据前方机场的实际起飞时间和计划过站时间判定延误航班的预计进港时间和离港时间；

3）若延误航班的预计离港时间早于毗邻后继航班的计划进港时间，证明虽然航班延误了，但未影响所占机位的后续航班占用，则保持预分配方案不变；

4）若延误航班的预计离港时间晚于毗邻后继航班的计划进港时间，证明延误航班影响了机位预分配的结果，需对原占用该机位的后继航班进行机位的再分配。并且，为保持其它正常航班的预指派结果不受影响，搜索后继航班在其计划进港至出港时间段内的所有可用机位。可用机位是指在该段时间内没有按预分配方案执行的被占用的机位。

5）按照机位预分配的原则，对需要进行机位再分配的后继航班，以满足近机位分配优先和旅客步行距离最小为目标，在所有可用机位中选择最佳机位进行指派；若没有满足上述条件的机位，则将其分配到符合约束条件的任一远机位。

算法的流程图如图4所示。

图4 机位再分配算法流程图Fig.4 Process of gate reassignment algorithm

1.2.3 再分配算例分析

仍以咸阳机场为例，由于咸阳机场地处中国中心位置，多条航线在此交叉汇集，执行中转飞行的航班班次较多，航班延误较为严重，使得预指派的方案不能顺利实施。如表2中的11号航班，预计进港时间相比于计划进港时间延误了50 min，因而有可能造成对其后继航班的影响。按照表2中的航班运行数据，根据机场对延误航班的界定规则，可以判定在该时段内的延误航班为第 5、7、11、13、15、18、22、34 和 36 号航班（第25号航班为取消飞行任务的航班）。算法通过查找这些航班的预分配机位，搜索该机位的毗邻后继航班的计划时刻表，并通过比较延误航班的预计离港时间和后继航班的计划进港时间来判定是否要对后继航班进行机位的再分配，结果如表4所示。由于算法限制了再分配的机位必须是在后继航班过站时间内的占用状态未发生变化的机位范围内进行选择，从而保证了再分配的机位对预分配机位的扰动性为0。在此基础上，再分配的机位也以保证靠桥率和旅客步行距离最小这两个指标为依据进行搜索选择。因此，该方案在一定程度上降低了延误航班对预分配方案的影响，同时达到了更加安全、高效和优质服务的目的。

表4 针对延误航班的机位再分配算法计算结果Tab.4 Result of gate re-assignment due to delayed flight

2 结语

合理的机位指派可以帮助航空公司减少时间延误，有利于航空公司的良好形象；同时可以减少旅客从机位到机位以及出、入口的步行时间和距离，提高机场的运营效益和服务质量。本文根据机场停机位的规划和属性特点，提出了一种简要算法，可根据航班时刻表自动对次日进离港航班进行机位的预指派，并针对实际运行中延误航班对预指派结果的干扰，设计了相应的机位再分配方案。结果表明，该算法可以提高飞机的靠桥率，在一定程度上减少了出入旅客的步行距离，同时降低了延误航班对预分配结果的干扰。但本文仅考虑了在延误航班预达本场时间确定和只针对机位毗邻后继航班再分配的情况，对于未知预达时间和大面积延误的情况，涉及的约束条件和算法更加复杂，还需进一步研究。

[1]常 钢，魏生民.停机位分配问题优化技术[J].中国民航学院学报，2006，24（2），25-29.

[2]文 军，孙 宏，徐 杰，等.基于排序算法的机场停机位分配问题的研究[J].系统工程，2004，22（7），102-105.

[3]文 军，李 冰，王清蓉，等.机场停机位分配问题的图着色模型及其算法[J].系统工程理论方法应用，2005，14（2），136-140.

[4]鞠姝妹，许 俐.基于GSAA的停机位指派优化问题的研究[J].交通运输系统工程与信息，2008，8（1），138-143.

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

[6]王 力，刘长友，涂奉生.民用机场停机位优化配置[J].南京航空航天大学学报，2006，38（4），433-437.

[7]卫东选，刘长友.机场停机位再分配问题[J].南京航空航天大学学报，2009，41（2），257-261.