基于CDM机制下不同航空公司的时隙分配研究

张虹 熊静 黄晓丹 徐露 李洋 高佩

摘 要：研究了航空公司基于CDM机制下对时隙进行二次指派的问题。首先运用RBS算法对航班进行初次分配，之后结合Compression算法和固定优先权TTC算法提出了一种新的算法对时隙进行二次分配，并利用此算法和遗传算法同时对模型进行求解。最后应用国内某机场的实际数据进行仿真验证，结果表明，所提算法在对时隙的分配中相比RBS算法和遗传算法不仅可以使得延误成本减少，而且可以均衡不同航空公司的平均延误成本。

关键词：航空运输;Compression算法;固定优先权TTC算法;时隙交换;CDM

中图分类号：U8      文献标志码：A      文章编号：1673-291X（2019）02-0184-03

引言

如今，随着人们生活水平的日益提高，人们出行对于舒适度和快速度的需求日益增长，以至于在伴随着民航运输业快速发展的同时，空域机场容量供给并不足以充分提供。尤其在发生恶劣天气的情况下，机场容量大幅度下降，时隙资源紧张，多数航班不能按时降落，只能在空中盘旋等待，不仅增加了危险性还消耗了巨大成本。如今解决这一问题的主要方法是利用地面等待程序（GDP）[1]让没有起飞的航班在机场等待，因为地面等待成本远低于空中等待，而且采取地面等待代替空中等待这一策略在减少成本的同时还降低危险系数。通过地面等待策略改变飞机的起飞时间，从而避开拥堵的时间段，这关系到时隙的分配问题。时隙的分配通常由空管部门决定，这实际上忽视了航空公司的实际决策目标。本文主要研究基于CDM（协同决策机制）下航空公司根据各自的决策目标和空管局共同决策时隙的二次分配问题，从而提高时隙的利用率。

基于CDM机制下时隙研究的国内外文献主要有，T Vossen等[2]主要研究了航空公司自主支配时隙资源和与别的航空公司相互交换时隙资源，将时隙交换看做易货流程，并且将优化问题与当前交换时隙资源程序进行比较，讨论航空公司提高决策能力的可能性。TWM Vossen等[3]研究了FAA与航空公司之间的数据交换策略，允许航空公司之间的交换航班时刻，并开发了一套整数规划模型，有助于优化其内部成本函数。张荣等[4]研究了CDM GDP机场资源的公平分配问题，提出了基于延误成本公平分配的新的协同地面等待优化模型，并利用遗传算法对模型进行求解并与RBS算法作了对比。JW Bono 等[5]研究了GDP期间分配到的时隙的可能性，利用预测博弈论进行分析，对个航空公司的空余时隙进行拍卖。

综上可知，如今基于CDM机制下对时隙的研究主要集中在两方面，一方面是对时隙交换的研究，另一方面是对时隙拍卖的研究。但是在时隙交换的研究上少有对不同航空公司时隙交换所带来的公平性进行研究。本文主要研究基于CDM机制下对时隙进行二次分配，并提出新的算法对模型求解降低延误成本的同时均衡各航空公司航班的公平性。

一、算法介绍

（一）RBS算法

RBS算法用于初次分配机场进场的时隙资源，主要流程如下：

（1）首先按免除航班、执行过地面等待程序的航班、其他航班分为三类;

（2）对每一类航班按最初的时刻表顺序排序;

（3）将所有的可用时隙进行升序排列，然后依次排给航班队列中的每一个航班。

（二）Compression算法+TTC算法

本文所提出的算法主要是针对各航空公司具有相同目的且不需要取消航班，从而也可达到延误成本公平化目标所设计的。本文提出的算法借用了TTC算法中的根据决策目标确定时隙优先级的思想，并且借用了Compression算法某航空公司取消航班后该航空公司其余航班具有优先级的思想，并且考虑到多个航空公司的延误成本（决策目标而定）相对公平。本文采用轮换优先级使得多个航空公司公司轮换进行选择时隙，从而可以达到选择时隙的公平性。

具体算法步骤如下所示：

（1）首先将所有的航班按照目标时隙的升序排列得到了p，将a航空公司的航班排序记为p、将b航空公司的航班排序记为p，假设航空公司多的话以此类推。

（2）将时隙航班表初次排列记为S。

（3）首先从RBS算法对航班进行的初次分配中给第一个航班赋予最高优先级，让第一个航班自由选择一个期望的时隙。

（4）判断第一个航班是属于哪个航空公司的，假如是属于a航空公司的，则在升序排列的p中找到排列在后面且机型是轻机型的飞机，若没有轻机型的飞机则选择中机型的飞机;依此类推，若有好几个相似的机型则根据升序排列的p中那几个相似机型中选择排列最后面的航班，让这个航班去执行时隙航班表S中最后的一个时隙。

（5）a航空公司執行完之后，轮换到b航空公司执行。在p中首先寻找机型是H的航班首先执行，其次执行机型是M的航班最后执行机型是L的航班，若有好几班相似的机型则选择p中排序相对最上的一个航班。首先让其选择一个期望时隙，紧接着在p中选择相对排列在后且是轻机型的飞机，若没有轻机型则选择中机型;依此类推，若有好几个相似的机型则根据升序排列的p中相似机型中排列最后的航班，让这个航班选择S时隙中倒数第二个时隙。依此类推，重复执行步骤（4）和步骤（5）直至所有航空公司的航班都安排了时隙。

二、建立数学模型

（一）变量定义

根据上诉算法和下述模型相关参数解释如下：

（二）数学模型

本文基于CDM机制下航空公司自由指派时隙，最终使得各个航空公司的每个航班延误成本均衡，由此可以提高航空公司的积极性。

目标函数为每个航空公司的每个航班的平均延误成本与所有航空公司每个航班的平均延误成本之差的绝对值：

三、算例验证

（一）假设条件

首先根据模型做出如下假设：

（1）空管部门提供的时隙都是已知的;

（2）所有航空公司都可以自由分配时隙;

（3）旅客延误时间为计划进出场时间与初始进出场时间的差值。

（二）实例分析

根据文献[4]中对广州机场2008年某日4点到5点的实际数据，利用遗传算法进行处理的结果，本文在此基础上对该实际数据运用本文算法进行处理，结果表明，本文算法相比遗传算法可以得出更优化的平均延误成本。

首先该实际数据中涉及到10架飞机，有5架飞机属于CAG航空公司，另外5架属于CES航空公司，这10架飞机参与了当天下午的地面等待程序（GDP），地面等待程序的时间由下午4：00到5：48。两个航空公司在CDM机制基础下对时隙进行二次分配。由于不同航空器的运营成本不同，航班进行时隙选择时首先要考虑运营成本较高的航班，各类飞机延误运营成本见表1。在对航班时刻表分别利用RBS算法进行初次指派和利用本文算法和遗传算法进行二次指派结果，如表2所示。

结语

本文研究了在机场时隙资源短缺情况下航空公司结合自身决策目标参与对时隙进行的二次分配问题。由于目前少有对航空公司公平性进行研究，本文首先结合compression算法和固定优先权TTC算法总结出一种新的算法，其次利用该算法对航空公司不取消航班情况下建立的模型进行求解。最终分配结果显示，相比RBS算法和遗传算法对模型的求解结果来看，本文算法不仅能降低航空公司总延误成本，同时更能均衡航空公司平均延误成本。然而，本文主要只考虑了航班延误的显性成本，下一步可以将航班延误成本中的隐形成本考虑进来。

参考文献：

[1]  胡明华，徐肖豪.空中交通流量控制的地面保持策略[J].南京航空航天大学学报，1994，（S1）：26-30.

[2]  Vossen T W M，Ball M O.Slot Trading Opportunities in Collaborative Ground Delay Programs[J].Transportation Science，2006，40（1）：29-43.

[3]  Vossen T，Ball M.Optimization and mediated bartering models for ground delay programs[J].Naval Research Logistics，2010，53（1）：75-90.

[4]  張荣，周小数.CDM时隙初始分配公平性研究[J].指挥信息系统与技术，2010，1（2）：51-55.

[5]  Bono J W，Wolpert D，Xie D，et al.Decision-Theoretic Prediction and Policy Design of GDP Slot Auctions[J].Ssrn Electronic Journal，2011，3（1）：232-235.