繁忙机场机位分配的混合集合规划方法

王岩华，朱金福，朱 博，唐小卫

(南京航空航天大学 民航学院，江苏 南京211106)

随着航班数量快速增长，停机位资源不足将严重制约我国民航运输的发展。对机位资源进行优化分配，可以提高机位利用率，在一定程度上缓解繁忙机场机位资源的紧张状况。因此，对停机位优化分配的研究具有重要理论意义和实用价值。

停机位分配问题(gate assignment problem，GAP)是近年来学术界研究的热点。GAP 问题具有NP -Hard 特性，对于大规模问题在有限时间内较难得到最优解［1］。目前对停机位分配的研究主要有3 类方法：①数学规划方法。2001 年，XU 等将该问题描述为一个混合二次0 -1 整数规划问题［2］。2013 年，杨双双等以停机位保障能力和客户满意度为目标建立优化模型［3］。2014年，曾琳燕等以旅客步行距离最小为优化目标建立停机位指派优化模型［4-5］。②系统仿真方法。2010 年，尹嘉男等建立多跑道机位分配仿真模型，寻求滑行时间最短的分配方案［6］。2012 年，冯程等利用计算机仿真进行算法设计［7］。③人工智能方法。2002 年，LAM 等建立了与人工智能相结合的机位分配专家系统［8］。

尽管对机位分配的研究已取得一定成果，但在实际分配中业务规则较复杂，已有的整数规划方法需对业务规则进行较多抽象和简化才能建立模型。虽然机位分配的最本质约束能够得到正确描述，但是重要业务规则仍然无法表达，限制了这些研究成果在实际问题中的应用。混合集合规划(mixed set programming，MSP)特别适用于求解集合覆盖/划分、任务分配等问题。为解决上述问题，笔者采用MSP 方法对繁忙机场机位分配问题建模并求解。

1 繁忙机场机位分配问题描述

停机位分配问题是在给定的作业时间窗内，将进出港航班分配到有限的机位停靠，进行地面保障作业的运行决策问题。解决繁忙机场机位分配问题，存在以下困难：

(1)繁忙机场航班流量大。以首都机场为例，据统计，其停机位多达350 个，日平均航班起降架次已超过1 500 架次。因此，繁忙机场机位分配问题属于大规模的整数规划问题。

(2)繁忙机场机位分配的业务规则复杂。除了机型与机位匹配约束之外，繁忙机场机位分配还有许多复杂的业务规则，包括航班分为纯出港、纯进港和过站航班3 类，现有研究一般不进行区分，实际问题必须区分;为缓解机位资源不足，某些组合机位可根据需要进行合并或拆分;为提高近机位利用率，对过站时间较长的飞机进行拖曳，离港前再拖至近机位上客。

(3)实时性要求较高。机场运行指挥中心在汇集各航空公司第二天航班计划后，要求在短时间内快速准确地进行机位分配，以便空管和地面保障部门进行保障工作，这就要求模型和算法能够快速解决该问题。

由此可见，繁忙机场机位分配是一个复杂的离散系统决策优化问题，采用传统数学规划模型难以解决。混合集合规划擅长对业务问题进行描述性建模，笔者以此为出发点进行研究。

2 繁忙机场机位分配的MSP 模型

2.1 混合集合规划方法

混合集合规划是以一阶逻辑与集合推理为算法框架的逻辑求解系统［9-10］。与数学规划不同，混合集合规划方法建模的步骤为：数据建模→逻辑建模→求解规则设计。混合集合规划首先通过约束推理切割解空间，之后查询关键变量对解空间进行完备搜索，使得关键变量从模糊变为确定。笔者基于MSP 方法对繁忙机场机位分配提出新的建模方向，并采用自然约束语言(natural constraint language，NCL)进行编程。

2.2 数据建模

在混合集合规划模型中存在3 类变量：原始数据变量、中间变量和决策变量。原始数据变量直接从数据库中读取;中间变量由原始数据变量通过建模计算得到;决策变量则通过逻辑建模求解得到。数据类采用全英文大写命名，如FLIGHT;类中的各属性命名则为属性加类，如id-Flighti;集合为首字母大写，如ArrivalFlight。

MSP 数据建模涉及的原始数据类有航班、机位和机型。NCL 采用面向对象的方法得出以下3个原始数据类：

(1)FLIGHT(id，name，outIn，aircraft，id-TypeAircraf，first，t，gateYday，mct，Property)。id-Flighti为航班i唯一标识;nameFlighti为航班i的航班号;outInFlighti为航班i进离港标识;id-TypeAircraftFlighti为执飞航班i的机型标识;first-Flighti为航班i的始发标识;tFlighti为航班起降时刻;gateYdayFlighti为始发航班i前一天停场机位;mctFlighti为航班i最小过站时间;Property-Flighti为航班i性质。

(2)GATE(id，name，IdGateForbidden，charac-ter，IdTypeAircraft，Property)。idGatei为机位i唯一标识;nameGatei为机位i的名称;IdGateForbiddenGatei为机位i被占用时，其不可用组合机位集合;characterGatei为机位i远/近机位性质;Id-TypeAircraftGatei为机位i可停靠机型集合;PropertyGatei为机位i国际/国内性质。

(3)TYPEAIRCRAFT(id，name)。idTypeAircrafti为机型i唯一标识;nameTypeAircrafti为机型i型号。

MSP 模型的已知参数有航班保障时间time-Support，同机位前后航班安全时间间隔gapSecurity和最大过站时间maxmct。

根据以上原始数据变量，通过建模计算得到MSP 模型的中间变量，如表1 所示。

表1 中间变量表

笔者将待分配的航班分为3 类：纯进港、纯出港和过站航班。不同类型的航班，其占用机位的时间区间不同，如表2 所示。需特别指出，参考繁忙机场实际运营情况，对于过站航班，若过站时间不超过一定值，则到达航班和出发航班停靠同一个机位，占用机位时间为总时间的1/2;若过站时间过长，则进行拖曳，分别将到达航班和出发航班看成一个纯进港航班和一个纯出港航班，下客完毕后拖至远机位停靠。

MSP 模型中的决策变量为gateFlighti和FlightGatej。其中，gateFlighti为航班i分配的机位;FlightGatej为机位j上停靠的所有航班集合。gateFlighti为关键决策变量，确定gateFlighti后可以确定其他决策变量。

表2 航班类型及其占用机位时间区间

2.3 逻辑建模

2.3.1 基本约束

停机位分配的基本约束包括机型与机位匹配约束、独占性约束、最小过站时间约束、安全时间间隔约束和航班集合覆盖约束，如式(1)～式(5)所示。

其中，式(1)表示机型与机位相互匹配约束，执飞航班j的机型在机位i可停靠的机型集合中。式(2)表示同一时刻同一机位最多能停靠一个航班。式(3)表示最小过站时间约束。式(4)表示同机位安全间隔时间约束，即同一机位上一航班离港时间与紧邻的下一航班进港时间间隔必须大于机场规定的安全间隔时间。式(5)表示航班集合覆盖约束。

2.3.2 业务规则约束

业务规则是机场进行机位分配必须遵守的运行规定，有些是行业内共同遵守，有些是各机场专门制定。在现有机位分配研究中，一般只考虑基本约束，对业务规则约束研究较少。笔者的MSP模型中考虑的业务规则约束包括组合机位约束、始发航班约束、飞机拖曳约束和国际国内航班约束。其中，组合机位约束、飞机拖曳约束是提高繁忙机场近机位利用率需满足的必然要求。这些业务规则可用式(6)～式(13)表示。

式(6)和式(7)表示组合机位约束，当小机位被占用时，组合大机位不能停靠飞机。式(8)表示航班停靠近机位等同于航班分配的机位为近机位。式(9)和式(10)分别表示对于始发航班，若其前一天停靠近机位，第二天的始发航班安排在同一近机位;若其前一天停靠远机位，第二天的始发航班尽量安排在近机位。式(11)表示对于过站时间过长的过站航班，考虑飞机拖曳，分别将到达航班和出发航班看成一个纯进港航班和一个纯出港航班。式(12)和式(13)分别表示国际航班停靠国际机位，国内航班停靠国内机位。

2.3.3 优化目标

繁忙机场机位分配实际运行中考虑的优化目标有靠桥率最大和飞机滑行距离最短等，其中最大化航班靠桥率为繁忙机场评价机位分配方案的核心，因此笔者以此为优化目标。航班靠桥率即停靠近机位的航班数量与航班总数的比值。

式(14)表示以最大化靠桥率为优化目标。式中：bridgegateFlighti为停靠近机位的航班数量，其计算如式(8)所示;#FLIGHT为航班总数。

2.4 求解策略

设计求解策略是MSP 模型的关键，设计合适的求解策略能对建立的停机位分配MSP 模型进行高效求解。混合集合规划的求解策略有最小松弛度、最大松弛度、最小遗憾度、顺序性和贪婪性等原则。根据机位分配问题的特点，采用最小松弛度和贪婪性原则进行求解。

式(15)为关键变量gateFlighti的选择规则，即基于最小松弛度原则，在FLIGHT中选择使gateFlighti变量值域元素个数尽可能少的航班。松弛度越小，则非确定性越小，产生回溯的可能性也越小。式(16)表示分配停机位时在gateFlighti域中按照贪婪性原则，首先选择近机位，即最有利于目标函数的方向。执行式(17)的查询，检查式(15)和式(16)航班停靠的机位是否为近机位j。

3 国内繁忙机场实例分析

以国内某繁忙机场2014 年4 月22 日停靠T1 航站楼的航班为例，时间窗为24 h，包含164个国内航班，共9 种机型，分配至4 个机坪的45个机位(近机位13 个，远机位32 个)。其中，N1、W1、W2 为远机位机坪。该繁忙机场各机位均给出可停靠机型集合，如表3 所示。具体航班时刻如表4 所示。该例中，根据机场实际情况设定国内航班保障时间为40 min，安全间隔为5 min，对过站时间超过180 min 的航班进行拖曳。

表3 各机位相关属性

表4 国内某繁忙机场部分航班时刻表及分配结果对比

MSP 模型能够满足遵守该繁忙机场实际机位分配中业务规则的要求。机场在实际运营中不需要求得最优解，只需在较短时间内得到较优的满意解，因此设定求解时间为1 min，时间结束时程序停止运行，计算结果如表4 所示。由分配结果可以看出，采用MSP 方法前，该机场人工分配时，111 个航班停靠近机位，靠桥率为67.7%。采用混合集合规划对该问题进行分配时，145 个航班停靠近机位，靠桥率为88.4%，比人工分配提升了20.7%。表4 中，对于过站航班HU7110 和HU7111，MSP 模型识别出其过站时间未超过180 min，则将其分配在同一机位上下客。采用MSP方法求解时，分配至远机位的19 个航班均停靠在离T1 航站楼较近的W1 坪和W2 坪，MSP 方法对远机位的分配也比人工分配更合理。

4 结论

笔者采用混合集合规划方法，针对繁忙机场停机位分配问题的特点，建立了包含飞机拖曳、组合机位等规则的约束规划模型，并设计了简洁高效的求解策略。对国内繁忙机场实例进行求解分析，取得了较好的效果。

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

［2］ XU J F，BAILEY G.The airport gate assignment problem：mathematical model and a tabu search algorithm［C］//System Sciences，Proceedings of the 34th Annual Hawaii International Conference. ［S. l.］：IEEE，2001：102 -111.

［3］ 杨双双，田勇，万莉莉，等.基于客户评价体系的停机位分配优化研究［J］.武汉理工大学学报(交通科学与工程版)，2013，37(1)：167 -174.

［4］ 曾琳燕，姜雨，罗宇骁.基于旅客步行距离的停机位均衡优化指派建模［J］.武汉理工大学学报(交通科学与工程版)，2014，38(4)：895 -899.

［5］ 杨越，王犇，刘杨. 机场机位分配的一种实用方法［J］.中国民航大学学报，2014，32(2)：27 -32.

［6］ 尹嘉男，胡明华，赵征.多跑道机场停机位分配仿真模型及算法［J］. 交通运输工程学报，2010，10(5)：71 -76.

［7］ 冯程，胡明华，赵征.一种新的停机位分配优化模型［J］.交通运输系统工程与信息，2011，12(1)：131-138.

［8］ LAM S H，CAO J，FAN H. Development of an intelligent agent for airport gate assignment［J］. Journal of Air Transportation，2002，7(2)：103 -114.

［9］ ZHOU J Y.The NCL natural constraint language［M］.［S.l.］：Science Press，2012：131 -140.

［10］ ZHOU J.Introduction to the constraint language NCL［J］. The Journal of Logic Programming，2000，45(1)：71 -103.