基于突发事件的机场进离场时隙分配研究

田　勇，吴东晖，万莉莉，王　湛

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



基于突发事件的机场进离场时隙分配研究

田勇，吴东晖，万莉莉，王湛

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

摘要：针对机场发生突发事件导致机场容量急剧下降而难以满足航班时隙需求的情况，建立进离场时隙分配模型，为受影响的航班重新分配时隙。以进离场航班的总延误损失为目标函数，将旅客平均延误时间作为时隙分配公平性指标，首次引入生物地理学优化算法对时隙分配模型求解。计算首都机场282个进离场航班重新分配时隙耗时为320 s，所求得的解与RBS算法相比，总延误损失减少了32.8%，旅客平均延误时间降低了27.8%。该模型和算法表现出高效、快速的时隙分配能力，可为决策者的应急决策提供有力保证。

关键词：突发事件；地面等待策略；进离场；时隙分配；生物地理学优化算法

近几年来，急剧增长的航班数量与有限的机场容量矛盾越来越突出，由此引起航班延误问题日益严峻，机场已经成为空中交通管制的瓶颈[1]。特别是协调机场遇到突发事件引发的容量下降，导致原已接近饱和的机场时隙资源变得更加紧张。虽然航班延误不可避免，但对进离场航班重新分配时隙，将有助于减少延误损失、提高飞行的安全性。ODONI首次提出使用地面等待策略，为进场航班重新安排起飞时隙[2]；BALL提出RBS算法和Comprehension算法[3]；PULUGURTHAL等首次将遗传算法引入到时隙分配问题中，大大加速了求解速度[4]；张洪海等提出以公平性、功效性作为目标，以有效性作为约束，通过使用遗传算法求解多目标时隙分配模型[5]；严峻等采用模拟退火算法解决协同决策机制下时隙二次分配模型[6]；田勇等将市场机制引入到地面等待时隙分配中，采用分支定界法求解模型[7]；COROLLI等考虑机场网络和航空公司偏好的情况下，对不确定性条件下的时隙进行分配[8]。

早期的研究只对受影响的进场航班分配时隙，但是实际运行中，进场和离场是相互联系、相互制约的。近几年的研究同时考虑了进场与离场容量之间的关系(如图1所示)，主要是针对可预测容量变化，在预战术阶段对航班时隙进行重新分配。笔者以机场正常运行时遭遇突发事件导致机场容量迅速下降，不能满足航班进离场时隙需求为背景，以航班安全飞行为前提，以总延误损失最小为功效性原则，以旅客平均延误时间最小为公平性原则，在满足安全性、有效性的前提下，尽可能地减少总延误损失，并使旅客承担的延误时间相对均衡。引入并改进生物地理学优化算法，使其适用于求解所建立的时隙分配模型，从而提高求解速度，满足处理突发事件的时效性需求。最后，将所求的解与RBS算法在功效性、公平性方面进行对比。

图1　机场进场与离场容量之间的关系

1机场进离场时隙分配模型

将引起机场容量下降因素分为可预测事件和突发事件，根据其特点不同，处理的方式也不一样。可预测事件引起的容量下降具有可预见特点，比如根据历史数据和目前天气状况预测天气变化、机场跑道和设备定期维护维修等，有充足的时间提前做好航班调整预案，避免空中延误，降低延误损失；突发事件引发的容量下降具有不可预知、发展速度快的特点，比如：天气骤变或者机场设备突发故障等造成的机场容量下降，需要迅速反应，并在短时间内得出安全、经济、公平的空中交通管理方案。

建立模型的基本思路：首先，将进场航班分为已起飞和未起飞两类航班，由于空中等待存在风险而且等待成本昂贵，将已起飞航班的延误损失系数设定为其地面延误损失系数的β倍。其次，将时间按15 min划分为一个时间片，根据每个时间片内进、离场容量包线关系，以进离场航班总延误损失最小作为功效性原则，以平均旅客时间最小作为公平性原则，在满足有效性的基础上，为每架航班安排合理的地面或者空中延误。

针对模型的建立作出如下假设：①将研究的机场作为唯一受限元，不考虑航路、扇区等容量变化情况；②假设所有航班从起飞机场到目的机场的飞行时间是固定的，不存在航班提前到达、返航、备降或者取消的情况。

决策变量如下所示：

目标函数为：

(1)

(2)

约束条件为：

(3)

(4)

(5)

(6)

(7)

(8)

式(1)表示总延误损失等于离场延误损失、进场航班的地面延误和空中延误损失的总和；式(2)表示旅客平均延误时间；式(3)表示一个离场航班只能分配一个进场时隙；式(4)和式(5)表示一个进场航班只能分配一个进场时隙；式(6)和式(7)分别表示机场进场与离场的容量限制；式(8)表示在时间片k时进场与离场容量的关系。

2生物地理学优化算法

2.1生物地理学

生物地理学是一门研究生物栖息地的分布、物种迁移和灭绝规律的科学。如图2所示，生物生活在不同的栖息地A～H上；根据每个栖息地的适宜度指数(habitat suitability index，HIS)生物自发地迁入和迁出，或为适应栖息地的剧烈变化，生物自身突变、进化或者消亡；栖息地的降雨量、温度、湿度、地貌特征、植被多样性等因素称为栖息地适宜度向量(suitable index vectors，SIV)。

图2　栖息地迁入迁出示意图

2.2生物地理学算法

2008年，SIMON教授受到生物地理学规律的启发，提出生物地理学优化算法(biogeographybased optimization，BBO)[9]，BBO算法依据生物物种在地理上分布的特点，设计了基于概率的栖息地个体迁移算子和突变算子，通过迁入、迁出操作实现个体间的信息共享，通过变异操作提高个体的多样性，并采用衡量栖息地适宜度的方式完成寻优过程。BBO算法是一种新的解决工程问题的全局优化算法，具有结构简单、易于实现、收敛速度快、对当前群体信息有效利用能力强且稳定性好等诸多优点。目前BBO算法已在飞机传感器监测、图像识别、心脏疾病诊断、生产调度、阵列天线综合等领域获得了较为成功的应用。

3基于BBO的进离场航班时隙分配

航班进离场时隙分配模型中的决策变量为二进制变量，属于0-1整数规划模型，BBO算法属于整数规划智能算法，因此可以将该算法应用于求解时隙分配模型。由于机场进离场延误时，往往需要为几百架航班配置好几个小时的时隙，所以变量也较多，传统的0-1整数规划算法已经不能满足求解需求，并且突发事件往往无法预知，对时隙分配的时效性要求较高，一般智能算法的求解速度和求解精度也不能满足要求，通过与其他算法对比发现，BBO算法能够快速地求解时隙分配模型，因此采用BBO算法求解。以BBO算法构建的时隙分配模型，有以下特点：

(1)栖息地表示候选解集，其适宜度特征向量SIV表示优化问题解的特征，与遗传算法中的“基因”相似，对应于该模型中给每个航班安排时隙的编码；

(2)栖息地的适宜度指数(HSI)是对适宜度向量SIV优劣的度量值，类似于遗传算法中的适应度函数，而在该模型中对应的是总延误损失值，是评价这个解集好坏的标准；

(3)栖息地的迁入和迁出机制提供了解集之间信息交互机制。高HSI的解以一定的迁出率将信息共享给低HSI的解，从而提高低HSI解的质量和物种的多样性；

(4)BBO算法能够根据栖息地HIS的不同，计算相应的突变率，对栖息地进行突变操作，从而增加物种的多样性。

对BBO算法进行部分改进，加快收敛速度，从而实现在较少的迭代次数获得相对优良的求解结果。首先BBO算法是随机产生的初始解，往往增加迭代的次数，不利于快速收敛。引入轮盘赌的方式，采用概率方式相对均衡地得到初始解。其次，无论是初始解还是经过迁移和变异的解，都可能存在完全相同解向量的情况，这减弱了算法的搜索能力，陷入局部最优解，对此采用随机生成一个初始解代替其中一个重复的解。BBO算法的进离场时隙分配流程图如图3所示，时隙分配计算过程如下：

图3　BBO算法的进离场时隙分配流程图

(1)初始化BBO算法参数，设定初始航班分配时隙的解集数量为n，栖息地物种最大容量为Smax，迁入率最大值为I，迁出率最大值为E，最大变异率为mmax，迁移率为Pmod，精英个体留存数为Z；

(2)读取延误时间段内的进场航班数据，计算每架进离场航班的延误损失系数；

(3)采用轮盘赌选择方式得出n个符合限制条件的初始时隙分配解集；

(4)排查操作。采用逐一对比的方法检查是否存在完全相同的解，当出现向量Xi=Xj时，采用随机生成新向量Xk取代Xj；

(5)计算每个解集的延误损失，按照延误损失从小到大进行排序；

(6)取前Z个精英解，判断最优解是否满足结束条件，若是则输出结果，计算过程结束，否则继续步骤(7)；

(7)根据式(9)计算栖息地i对应的物种数量Si、迁入率λ(Si)以及迁出率μ(Si)，然后进行迁移操作；

(9)

(8)更新每个栖息地的物种数量概率P(Si)，并根据式(10)计算每个栖息地的突变率MS，然后跳转到步骤(4)。

(10)

4算例分析

选取北京首都机场某日9—11点的航班计划数据，其中143个进场航班和139个离场航班。北京首都机场一共有3条跑道，假设其运行模式是一起一降一混合。当天8点50分，其中一条跑道设备突发故障停止运行，剩下两条跑道以混合起降的模式运行。

据文献[10]对地面等待延误成本的分析，将飞机按照尾流类型分为轻、中、重3类，延误损失分别设为208元/h、2 916元/h和4 167元/h，航班上每位旅客的平均票价为750元，平均净利润率为2.2%,平均飞行时间设为2 h，国内、国际航班旅客的平均延误成本分别设为50元/(h·人)、100元/(h·人)。

由于存在某个时刻航班时隙需求小于机场此时的容量，出现时隙空余，某个时隙没有航班进离场，因此时隙与航班不再是一一对应的关系，不能使用0-1整数规划。为了避免这种情况，安排虚拟航班进驻空闲时隙，保证航班数量大于或等于时隙的数量。为不影响计算结果，将虚拟航班的延误损失系数和乘客数设为0。根据航班的实际情况，引入28架虚拟航班，设定初始栖息地的数量n=310；栖息地种群最大容量Smax=310；空中等待延误损失系数β=3[11]；设定最大值迁入率I=1、最大迁出率E=1、最大变异率mmax=0.015、迁移率Pmod=1和精英个体留存数Z=6。采用C++软件编程，在Windows7系统、2G运行内存下运行，其平均计算时间为320 s。图4和图5分别表示突发事件前后进、离场航班数量与机场进离场容量包线的关系。图6所示为北京首都机场遇到突发事件前后每个时间片内分配的进离场航班数量。

图4　计划进离场航班需求与容量之间的关系

图5　调整后进离场航班需求与容量之间的关系

图4中的散点表示该日北京首都机场9点—11点之间的所有计划航班按照每15 min为一个时间片，得出的进场和离场的航班时隙需求数量，图中的虚线表示机场原来的进、离场容量包线，图4中实线表示一条跑道停止运行后机场的进、离场容量包线。从图4可以看出，原计划航班的时隙需求满足机场进离场容量包线限制；发生一条跑道停运后，大多数时间片内的航班时隙需求已经不满足新的机场进离场容量包线。为了保障航班安全，减小延误损失，应对进场和离场时隙进行调整使其与进离场容量协调匹配。图5是根据机场进离场容量包线限制，通过所采用的时隙分配模型，应用BBO算法求得的进离场航班分配进场和离场时隙方案，其中的散点为每个时间片内进场和离场航班的数量，并且满足新的进离场容量包线。

将笔者模型所求得解与RBS算法在总延误时间、总延误损失和平均旅客延误时间3个方面进行对比，如表1所示，结果表明该模型与RBS算法相比在进离场总延误时间不变的情况下，进离场延误损失减少了32.8%，旅客平均延误时间降低了27.8%。

图6　北京首都机场航班优化前后每个时间片的航班数量对比

模型总延误时间/min总延误损失/元平均旅客延误时间/min笔者模型1970306656.84.5RBS算法1970456320.16.2优化差值0149663.31.7优化比例/%032.827.8

5结论

针对突发事件导致的机场容量下降不能满足航班时隙需求，需为受影响的航班重新分配进离场时隙。笔者考虑突发事件发生时，部分进场航班已经起飞的实际情况，以进、离场航班的总延误损失最小为目标函数，旅客平均延误时间为公平性约束，建立进、离场时隙分配模型，并采用BBO算法对模型进行求解，结果表明所提出的时隙分配模型切实可行，与RBS算法相比更加高效、公平，并且BBO算法能够快速求得全局最优解，为决策者进行决策提供了有力的保障。未来研究可将该模型和算法嵌入到ATM管理系统中，当机场遇到突发事件容量不能满足时隙需求时，触发ATM管理系统自动读取该机场受影响的所有航班计划，通过该模型和算法重新对受影响的航班进行分配时隙，并将分配结果通过ATM系统发送到所有受影响航空公司和机场，提升处理突发事件的效率。

参考文献：

[1]胡明华,钱爱东,苏兰根.基于地面等待策略的航班时刻规划方法[J].航空学报,2001,22(3):262-264.

[2]ODONI A R.The flow management problem in air traffic control[M].Berlin:Springer-Verlag,1987:269-288.

[3]BALL M.Collaborative decision making in air traffic flow management[R].Berkeley:UC Berkeley,1999.

[4]PULUGURTHAL S S,NAMBISAN S S.Using genetic algorithms to evaluate aircraft ground holding policy under static conditions [J].Journal of Transportation Engineering,2001,127(5):433-441.

[5]张洪海,胡明华.CDM GDP飞机着陆时隙多目标优化分配[J].系统管理学报,2009,18(3):302-308.

[6]严俊,吴桐水,高强,等.协同决策机制下的时隙二次指派[J].南京航空航天大学学报,2013,45(1):140-146.

[7]田勇,李永庆,万莉莉,等.基于市场机制的地面等待时隙分配方法[J].系统工程理论与实践,2014,34(6):1614-1619.

[8]COROLLI L,LULLI G,NTAIMO L.The time slot allocation problem under uncertain capacity[J].Transportation Research Part C Emerging Technologies,2014,46(46):16-29.

[9]SIMON D.Biogeography-based optimization[J].IEEE Transactions on Evolutionary Computation,2008,12(6):702-713.

[10]徐肖豪,李雄.航班地面等待模型中的延误成本分析与仿真[J].南京航空航天大学学报,2006,38(1):115-120.

[11]DANIEL D,OUSSEDIK S,STEPHANE P.Airspace congestion smoothing by multi-objective genetic algorithm[C]∥Proceedings of the 2005 ACM symposium on Applied computing.[S.l.]:ACM,2005:907-912.

TIAN Yong:Assoc.Prof.;College of Civil Aviation,Nanjing University of Aeronautics & Astronautics,Nanjing 210016,China.

[编辑：王志全]

文章编号：2095-3852(2016)01-0028-05

文献标志码:A

收稿日期：2015-08-16.

作者简介：田勇(1976-)，男，湖北洪湖人，南京航空航天大学民航学院副教授.

基金项目：中央高校基本科研业务费专项资金资助项目(NJ20140017)；江苏省自然科学基金资助项目(BK20130821).

中图分类号：X928;U8

DOI：10.3963/j.issn.2095-3852.2016.01.006

Slot Allocation of Airport Arrival and Departure Based on the Emergence

TIAN Yong，WU Donghui，WAN Lili，WANG Zhan

Abstract：According to the airport capacity declines sharply by the emergence,which cannot meet the demand of slots,and establish the model of slot reallocation for the affected flights.The total delay loss as the objective function,and the average delay of passengers as fairness index.The model is for the first time being solved by the biogeography-based optimization.It takes 320s for 282 flights to reallocation slot.The result compares with RBS the total delay loss is reduced by 32.8%,and the average delay of the passengers is reduced by 27.8%.The model and the algorithm are efficient for the slot allocation,and provide enough time and efficiency guarantee for decision makers in dealing with the emergence.

Key words：emergent events ;ground holding policy；arrival and departure; slot allocation; biogeography-based optimization