基于协同决策的多航站楼停机位实时分配算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于协同决策的多航站楼停机位实时分配算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：针对多航站楼机场停机位实时指派问题，提出了基于协同决策并考虑航空公司时隙交换公平性的机位实时指派算法。该算法将多航站楼资源的可共享性考虑到指派算法中，以最小延误费用原则为约束，采用混合集合规划进行指派模型的建立与求解。该算法在保证多航站楼停机位资源有效共享的前提下，充分实现了航空公司时隙交换的公平性，并且使延误引起的多方成本最小化。算例说明：本文提出的算法可以有效解决多航站楼的机位实时分配问题。

关键词：航空运输；协同决策；多航站楼；实时指派；混合集合规划；航班波

中图分类号：U8

文献标志码：A

文章编号：1005-2615（2015）01-0071-06

随着民航运输的飞速发展，运输量的快速增长，多航站楼多区域管理已经成为民航发展的一种趋势，然而这将使得机场运行保障变的更加复杂。机位是机场的核心资源，机位分配是机场日常运行保障中的一个非常重要的工作。高效合理的机位分配方案不仅会给民航运输带来巨大的经济效益，并且在一定程度上可以提高民航运输的安全性。在机场停机位实时指派的问题上，国内外学者已经进行了很多模型与算法的相关研究。从已有研究来看，在机位实时指派算法中，仍需综合考虑多航站楼模式、航班波、协同决策、时隙交换公平性以及这4个因素的影响。

由于运输量增长，许多大型机场都通过扩容的方式来满足需求。其中.航站楼的改扩建使得一个机场多个航站楼的运行模式应运而生。在多航站楼运行中，有很多公共的资源需要共享，如机位、跑道等外场资源；旅客由于转机等原因需要在多个航站楼之间活动；飞机也可能因为调配原因而从一个航站楼转移到另外一个航站楼。因此，机场的运行调度算法必须能够满足以上种种运行上的需求。在多航站楼运行模式下进行资源分配时，必须充分考虑各种资源之间的联动关系才能做到协调运行。此时.值得注意的是应当将航站楼作为资源分配的一个基本判断依据。首先判断航班机位是否在不同航站楼之间调整，然后根据预先设定的各种规则再进行其他资源的变更，这样才能使系统的处理逻辑相对清晰和简单。

为满足日益增长的航空运输需求，航空公司纷纷考虑以航班波的方式进行排班。相应地，枢纽机场针对航班波进行各项航班保障工作，其中就包括停机位的指派。航班波是指，为实现航班有效衔接，在一个时段安排进港航班，在紧接着的另一个时段安排出港航班。当航班波不受延误影响时，机场资源可以得到高效利用，旅客的中转等待时间大大缩短。但是，如果航班波受到延误航班的影响.旅客的中转时间会大幅度上升。要使航班不受或尽量少受延误航班的影响，则需要实现机场、航空公司和空管的协同决策。然而，目前机场、空管和航空公司大多单独完成各自任务，没有达到协同决策的要求。

在实现航空公司与机场的协同决策时，需要考虑到时隙分配和机位指派的先后关系以及相互影响。当航班延误之后，航班所获得的时隙将会改变.但在航空公司不知道后续机位指派方案的前提下.无法判断延误航班获得的时隙方案所对应的最佳机位指派方案是否为所有可能的机位指派方案（时隙交换后）中延误成本最小的。因此，航空公司需要与机场进行协同决策。首先由航空公司给出不同时隙方案，机场给出不同时隙方案下机位指派的延误成本，根据最小延误成本确定最佳时隙交换方案，再将该方案告知航空公司。然而，在总的延误成本最小时还需考虑航空公司间的利益均衡，所以在进行时隙交换时，还要考虑航空公司问的利益均衡性.进行公平的时隙交换。

本文在协同决策的基础上综合多航站楼资源共享性、航班波延误最小化、时隙交换公平性等因素，建立机场停机位实时指派模型，并在混合集合规划中实现模型的求解。

l 机位实时分配模型

1.1 模型符号

2 求解方法

混合集介规划（ Mixed set programming，MSP）源自逻辑规划与约束规划，是以一阶逻辑与集合推理为算法框架的逻辑求解系统。MSP能够将集合运算、量词、布尔逻辑、逻辑函数、日期/时间推理、数值约束等集成于一个系统，实现从实数、整数等数值类型扩充到布尔值、日期/时间集合类型的混合域上的全局推理，以及约束满足问题的建模与求解。此处，集合规划的概念并非指在问题求解中对集合运算符号、集合变量及集合约束的简单使用，而是系统地将集合推理与运筹学算法相结合，以集合变量为主进行问题建模，以基于集合推理的算法为核心进行模型求解。本文采用MSP方法求解下列算法。

2.2 停机位实时分配

步骤1 读取航班的机位预分配结果，航班对应的机位预分配信息，得到每个机位的可利用时间段。从时隙分配方案中得剑航班的时隙分配结果，包括带有航班波衔接的延误航班和没仃航班波衔接的延误航班。

步骤2对于没有航班波衔接的延误航班，根据航站楼{ at1，…，atn}分n次循环。将没有航班波衔接的延误航班根据最小延误费用原则和航站楼资源共享原则进行停机位分配。

步骤3 对于有航班波衔接的航班，考虑时隙公平交换的原则，根据不同的航站楼{ at1，…，atn}分n次循环.得到每个航站楼的延误航班时隙交换集合。根据有航班波衔接的航班和有时隙交换的延误航班.得到没有时隙交换的延误航班集合。根据最小延误费用原则和航站楼资源共享原则进行停机位分配。

步骤4 将步骤2.3的结果根据不同的航站楼进行综合，得到最终的各个航站楼的停机位分配。

在求解策略的设计中，将精确算法和启发式规则有机地结合在一起，既确保解的可行性，又灵活、个性化地控制搜索过程。启发式规则为：

（1）假设延误航班计划所属航班波为ωp，则其分配时隙所属的航班波必须大于等于ωp。

（2）航空公司进行时隙互换时，延误航班所处的航班波的数值应尽量相同。

（3）航班的停机位在不同航站楼之间调整要满足以下条件：

①不能是有航班波衔接的航班；

②调整后该航班产生的油耗费用不能大于该航班所属机型的平均油耗；

③调整后该航班的到达停机位时间不能大于该航班所属机型的平均滑行时间；

④调整后各航空公司的时隙交换满足公平性原则。

将上述两个算法的求解规则，结合不同的α，β值和约束条件.同时植入深度优先搜索算法中，一体化搜索确定延误航班的时隙分配集合与停机位指派集合.从而优化延误航班的时隙分配并最终确定满足多目标的停机位指派方案。

3 实例分析

3.1 实验数据

大型机场的航站楼比较庞大，分区也较为复杂.因此本文选取两个航站楼内4个区域9：00～11：00内到达的航班及机位分配情况进行优化，其中区域1和2属于一个航站楼，区域3和4属于另一航站楼：小、中、大机型分别用l，2，3表示；国航、东航、南航、海航分别用C.E.S，D表示。最小安全时问间隔T=5 min；旅客中转等待成本：1元/ min；飞机的油耗成本：7元/kg。飞机油耗：大型飞机46 kg/min，中型28 kg，/min.小型12 kg/min。航班信息见表1，各个区域的机位信息见表

2，延误信息见表3。

3.2 实验结果及分析

执行本文算法，根据时隙交换的优先级高于滑行油耗的原则，进行多次运算后，得到α=0.55，β=0.45。在满足时隙交换公平性的条件下，得到时隙交换结果如表4所示。

在不同的限定条件下，得到机位实时指派方案如表5所示，其中，初始方案表示航班尚未延误的机位初始分配方案；优化1方案表示航班延误后，进行合理的时隙交换但航站楼之间与航站楼符各区域之间的机位资源不共享时产生的机位指派方案；优化2方案表示航班延误后，进行合理的时隙交换且航站楼之间与航站楼各区域之间的机位资源可其享时产生的机位指派方案；优化3方案表示航班延误后，不进行时隙交换但航站楼之间与航站楼各区域之间的机位资源可共享时产生的机位指派方案。

初始方案中，滑行油耗为7 324 kg，旅客中转等待时间为369 600 min，因此，总成本为420 868元。优化1方案中，滑行油耗为7 342 kg，旅客中转等待时间为414 400 min，因此总成本为465 794元。优化2方案中，滑行油耗为6 736 kg，旅客中转等待时间为414 400 min，因此总成本为461 552元。优化3方案中，滑行油耗为6 844 kg，旅客中转等待时间为478 000 min，因此总成本为525 908元。各部分成本变化情况如图1所示。

对比优化方案1与优化方案2 可知，当资源共享时，飞机的滑油成本可以大幅度减小，从而降低最终的总成本。对比优化方案2和优化方案3可知，当时隙可交换时，旅客的中转等待时间可以大幅度减小，从而控制最终总成本。结果显示，本文提出的算法在实现了资源共享的同时也实现了时隙的有效交换，达到了控制延误成本的目标。

4 结束语

本文研究了协同决策机制下，航班延误时，多航站楼的机位实时指派算法。实验证明，本文提出的机位实时指派算法是一种切实可行且运行高效的调整算法。该算法能充分考虑多航站楼资源的共享性以及航空公司的时隙互换公平性；实现多方延误费用的最小化，降低航班延误引起的滑行油耗成本和旅客中转等待成本；能够在航班波的环境下实现航空公司与机场的协同决策。