CDM机制下的机场停机位一体化实时分配算法

刘君强，张马兰，陈鹏超，谢吉伟，左洪福

（南京航空航天大学民航学院，南京 210016）

CDM机制下的机场停机位一体化实时分配算法

刘君强，张马兰，陈鹏超，谢吉伟，左洪福

（南京航空航天大学民航学院，南京 210016）

停机位是机场的核心资源，停机位实时分配算法是研究的热点。本研究在协同决策（collaborative decision making，CDM）机制下，建立了多主体（机场、航空公司和旅客）最小延误费用原则，研究了航班发生小规模延误时的停机位实时分配模型，并借助混合集合规划（mixed set programming，MSP）进行建模与求解。该模型能够最小化航空公司滑行油耗成本和延误旅客的中转等待成本；实现各航空公司滑行油耗成本均衡化；以及在不影响航空公司利益的情况下有效保障延误航班的航班波衔接。数据分析表明：该机位实时指派方法能够有效实现机场与航空公司的协同决策，并能在节省算法运行时间的同时降低延误产生的机位实时指派成本，对机场与航空公司的实际运行具有指导意义。

航班延误；机位实时分配；航班波；协同决策；混合集合规划

据2011年统计数据[1]，中国现有运输机场175个，同时，许多大型机场正在改扩建，使得中国机场资源管理越来越复杂。针对机位实时指派问题，已有学者从机场、航空公司、旅客中的一方或两方利益，基于航班特征值、机位特征值等建立模型，采用网络仿真、规则库、混合优化等方法实现机位实时指派[2-6]。但综合机场、航空公司和旅客多主体利益的机位实时分配仍有待深入研究。针对旅客利益，以往研究并未考虑枢纽机场航班波[7]延误会大大影响旅客中转等待时间。航班波是在一个时段安排进港航班，在紧接着的另一个时段安排出港航班，从而实现航班的有效衔接。合理的航班波要求机场、航空公司和空管协同决策（collab-orative decision making，CDM）[8]。而目前各种资源调度（如停机位指派和航班排班等）均由机场、航空公司和空管单独完成，没有达到CDM的要求。

传统的机位实时分配中，航班延误的信息是固定的[9]。由于航空公司与机场不协同，机场在基于给定延误信息分配机位时可能产生机位分配困难和航班波衔接受影响等问题。本文所指的CDM机制下[10]：当延误产生时，空管在获得航班延误信息后将为延误航班提供新的时隙；航空公司在获得时隙之后将时隙指派给延误航班，此时的时隙指派方案并不是最终确定的方案，而是航空公司可选择的时隙指派方案，简言之，是时隙与延误航班所有可能的组合；机场在获得航空公司的可选时隙指派结果后进行实时机位分配，并比较各种可选时隙指派方案下对应机位分配方案的经济性，将经济性最佳的机位分配方案所对应的时隙指派方案反馈给航空公司；航空公司在得到机场反馈信息后再决定最终时隙指派方案。可见，航空公司与机场间的有效协同可让机场在基本不影响航空公司利益的情况下，更合理地安排停机位。

在协同过程中需解决时隙指派和机位分配两大问题。传统的方法是进行分阶段处理，先进行时隙指派，再进行机位分配。该方法需反复进行，十分耗时，而一体化的混合集合规划方法可将时隙指派和机位分配统筹到一个算法当中，从而大大节省运算时间，提高算法性能。

因此，本文在协同决策机制下综合考虑多主体利益，建立了以滑行油耗成本以及旅客中转等待成本最小为目标、均衡各航空公司延误油耗成本、并能保障延误航班的航班波有效衔接的一体化机位实时分配模型。模型的建立与求解将借助混合集合规划方法实现。

1 机位实时分配模型

1.1 符号定义

1）J为机位集合，j∈J；I为航班集合，i∈I；DI为延误航班集合表示有航班波衔接的延误航班，表示没有航班波衔接的延误航班表示并未产生延误但是受到停机位分配影响的航班（根据文献[8]确定调整范围在50 min之内的航班），DI⊂I，0＜J＜I；W为航班波集合，w∈W；M为机型集合，m∈M；N为航空公司集合，n∈N，NUM{N}，表示航空公司的个数；

2）Pmn为n公司m型飞机油耗增加占所有公司m型飞机油耗增加的百分比；ΔCOmn为n公司m型飞机由于延误增加的油耗；

3）COi为航班i每分钟的耗油量；

4）CTi、CTi＇分别为调整前后航班i滑行到其所停靠机位所消耗的时间；

5）Y为每单位质量航油的价格；C为每位旅客单位时间内的中转等待成本；

6）Pi为航班i的乘客数量；

7）Rij为航班i到达机位j的时刻；Lij为航班i离开机位j的时刻；

8）Gj表示机位j允许停放的最大机型，用相应数字代表机位大小，数字越大，机位越大；

9）Qi表示航班机型大小，用相应数字代表机型大小，数字越大，机型越大；Ω为一任意大的正数；

10）ΔT表示同一机位2架航班的最小间隔；Tidle表示所有机位空闲时间段集合

11）Xij的意义为：若航班i分配到机位j，则Xij为1，否则Xij为0；

12）K1j为机位j的空闲开始时间；K2j为机位j的空闲结束时间；

13）Zdw的意义为：若延误航班id处于航班波w中，则Zidw为1，否则Zidw为0；

14）TPid为中转旅客的人数，按照8%的中转比例计算，一般平均中转等待时间为90 min；

15）wp为延误航班计划所属航班波；wa为延误航班实际所属航班波，wa≥wp；Ew为航班波w的波长，航班波一般波长为40 min。

1.2 目标函数分析

1）延误产生的总成本最低：总成本包括滑行油耗成本和旅客中转等待成本，即

其中：（CTi＇-CTi）表示航班i增加的滑行时间为延误航班id中转旅客等待的航班波数量。

2）最小化滑行时间为

3）最小化旅客中转等待时间为

4）延误油耗均衡为

1.3 综合模型

算法综合模型为

式（5）为目标函数，表示总成本最小；式（6）表示每个航班只指派一个机位；式（7）表示一个航班只属于一个航班波；式（8）表示航班与航班波的对应性；式（9）表示航班与被指派机位的唯一对应性；式（10）要求机位与机型相匹配；式（11）要求机位的空闲时间大于最低安全间隔时间；式（12）要求机位空闲开始时间早于航班到港时间，并且机位空闲结束时间晚于航班离港时间；式（13）为有效性约束。

多目标不能同时达到最优，因此对多目标进行了以下优先次序的设定：为强调服务旅客的理念，旅客中转等待时间最小化的优先级最高；燃油成本是航空公司最直接的运行成本，故将滑行时间作为次优先级目标；燃油均衡体现的是航空公司的公平性，应是燃油成本最小化前提下的均衡，因此优先级次于燃油成本；总成本最小化是对旅客中转等待成本与航空公司油耗成本的综合，因此优先级放在最后。

2 算法

混合集合规划[10-11]（mixed set programming，MSP）是以一阶逻辑与集合推理为算法框架的逻辑求解系统，能系统地将集合推理与运筹学算法相结合，以集合变量为主进行问题建模，以基于集合推理的算法为核心进行模型求解。使用混合集合规划能够支持时隙分配与机位指派一体化的优化策略，从而支持协同决策的目标。混合集合规划主要算法介绍如下。

2.1 延误航班的时隙分配

步骤1 将所有航班波按照计划到达时刻的升序排序得到W（t）={w1，w2，…，wk}。

步骤2 定义uk=航班波wk包含的延误航班数量/从t时刻（当前时刻）开始到完成航班波wk需要的时间；定义最大uk值对应的航班波结束时刻为t1；定义t2为在t时刻未结束而在t2时刻结束的下一个航班波结束时刻，t2＞t；有τ=min（t1，t2）。

步骤3 将最大uk值对应航班波wk内的延误航班id按可交换时隙的方式指派到τ时刻之前的时隙中。若延误航班个数为r，则该步骤得到的时隙分配方式理论上应有r!种，但航空公司在进行时隙交换时，有一定限制（如交换时隙的延误航班所属航班波应尽量一致，交换时隙的延误航班实际到达时刻应晚于该延误航班的计划到达时刻，可进行时隙交换的航空公司限制等），因此实际需要计算的时隙分配方案远远小于r!种。

步骤4 将指派完成的航班波从集合W（t）中去除，重新进行航班波排序，重复步骤1、2、3，最终可输出所有延误航班的时隙分配方案。

2.2 停机位实时分配

步骤1 读取集合I中所有航班的机位预分配结果，根据每个航班对应的机位预分配信息，得到每个机位的可利用时间段

步骤2 分a）、b）两种情况对延误航班进行停机位分配：

步骤3 对于没有航班延误，但影响停机位分配的航班和步骤2中的b）部分得到的航班根据延误费用原则以及机型Qi与机位Gj相匹配的原则进行停机位分配。

步骤4 综合步骤2和步骤3，可以得到停机位分配结果。

在求解策略中，将算法和启发式规则有机结合，使得约束条件得到严格满足，确保解的可行性；并确保在求解过程中利用求解规则灵活控制搜索过程。启发式规则包括：

1）假设原计划航班所处的航班波是wk，则延误航班分配时隙所属的航班波必须≥wk。

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

将上述两个算法的求解规则同时植入深度优先搜索算法中，一体化搜索时隙分配集合与机位指派集合，从而优化延误航班的时隙分配并确定满足多目标的机位指派方案。

3 实验结果及分析

采用某大型机场的42个航班数据，如表1所示。使用POEM软件[9]建模与求解。

表1 航班计划信息表Tab.1 Scheduled flight information

表1中，航班到达时间范围为09：20—11：00，涉及国航、东航和南航，分别用C、E、S表示（算法中用1、2、3表示）；小、中、大机型分别用C、D、E表示（算法中用1、2、3表示）。7号和37号航班为特殊航班，调整前后的机位应保持不变。该机场某一航站楼共有35个机位，空闲时间为[09：00，12：00]。机位信息如表2所示。

表2 机位信息表Tab.2 Airport gate information

延误信息：13号航班10：05到达；17号航班11：00到达；37号航班11：00到达。根据文献[8]选取09：50—10：50作为调整的时间段。机位预分配如表3所示，实时机位调整如表4所示。

表3 初始机位分配结果Tab.3 Original gate assignment

表4 机位实时分配结果Tab.4 Real-time gate assignment

为方便计算，设定各类机型油耗为：大型46kg/min，中型28 kg/min，小型12 kg/min。中转等待的成本为1元/min。各种成本的计算结果如下。

1）旅客中转等待成本：航班执行前的原计划指派方案为62 640元，发生航班延误后的实时再指派方案为63 280元，增幅为1.02%。

航班延误时，空管为3个延误航班提供3个时隙，如表5所示。

表5 时隙信息表Tab.5 Slot information

13号、17号和37号航班分别属于南航、东航和国航，这3个航空公司的时隙均可交换。结合启发式规则，航空公司的可选时隙分配方案如表6所示，机场则根据表6做机位实时分配，不同的时隙分配将产生不同的成本。

表6 延误航班的时隙分配Tab.6 Slot assignment for delayed flights

表6中，因为时隙1属于航班波2，而37号、17号航班的预计到达时间是航班波3，延误航班不能提前到预计时间以前，因此，方案3到方案6对应的时隙分配是不可行的。

传统模式下，航空公司可能随机选择方案1，但这种时隙分配方式下的机位指派方案并非最优。时隙分配方案1和方案2对应的旅客中转等待成本增量分别为1 600元和960元，可见，根据机位指派结果，时隙分配方案2优于方案1。所以，采用方案2进行时隙分配将有助于控制机场与航空公司的运行成本并使旅客满意度最大化，同时也是CDM的体现。

2）油耗变化：航班执行前的原计划指派方案为9 758 kg，发生航班延误后的实时再指派方案为9 980 kg，增幅为2.28%。油耗均衡性如图1所示。

图1 调整后各航空公司各类型飞机的滑行油耗Fig.1 Balanced fuel consumption

图2表明，算法基本实现了各航空公司各类机型的油耗均衡。

3）总成本：航班执行前的原计划指派方案为130 946元；发生航班延误后的实时再指派方案为133 469元，增加了2 514元，即1.92%。各部分成本变化如图2所示。

图2 延误产生后机位实时分配方案下的各成本增量Fig.2 Increases of each cost in real-time gate assignment after delay

图1中，油耗成本从68 306元增长为69 860元，增加了1 554元，涨幅为2.28%；旅客中转等待成本从62 640元增长为63 600元，增加了960元，涨幅为1.53%。两种方案的比较如表7所示。

表7 方法比较Tab.7 Comparison of traditional method and proposed method

表7说明，本文提出的方法一方面具备较好的经济性，因为其实现了航空公司与机场的协同决策；另一方面其运算速度更快，一体化的方法可借助启发式规则实现快速目标筛选。可见，一体化优化策略的采用使得机场与航空公司间的协同决策（CDM）得以实现。传统的分阶段优化策略先进行时隙分配且缺少相关机位指派信息，所以比较费时，且总成本得不到有效控制；而一体化策略综合考虑了机位指派对时隙分配的影响，采取了最佳机位指派方案对应的时隙分配策略，从而能够从全局层面同时协调时隙分配与机位指派，更好地实现航空公司间以及机场与航空公司间的协同决策。

4 结语

本文建立了基于CDM的一体化机位实时分配模型，使用混合集合规划方法进行建模与求解。实验分析证明，该机位实时分配方法实现了时隙指派与机位分配的一体化优化以及机场与航空公司的协同决策；降低了航班延误引起的航班延误油耗成本、机位空闲成本和延误航班旅客中转等待成本；均衡了各航空公司的延误油耗成本；保障了延误航班的航班波衔接。因此，本文提出的方法在实际运行中是切实可行的。下阶段将研究机场群条件下基于空管、机场、航空公司CDM机制的一体化机位分配问题。

[1]中国民用航空总局规划发展司.从统计看民航2011[M].北京：中国民航出版社，2011.

[2]GILL C O，BADONI M，CHENG Y.A knowledge-based airport gate assignment system integrated with mathematical programming[J].Computers and Industrial Engineering，1997，32（4）：837-852.

[3]CHENG Y.A rule-based reactive model for the simulation of aircraft on airport gates[J].Knowledge-Based Systems，1998，10：225-236.

[4]WANG L.Optimized Assignment of Civil Airport Gate[C]//2010 International Conference on Intelligent SystemDesign and Engineering Application，2011：33-38.

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

[6]李 雯.枢纽机场航班波构建方法研究[D].南京：南京航空航天大学，2010.

[7]高 强，严 峻，朱金福.CDM机制下航空公司时隙分配优化决策[J].交通运输系统工程与信息，2010，11（5）：94-98.

[8]朱 博，朱金福，高 强.飞机和机组一体化恢复的约束规划模型[J].交通运输工程学报，2013，13（1）：77-83.

[9]ZHOU JY.A NoteonMixed Set Programming[C]//IEEE：the7thInternational Symposium on Operations Research and Its Applications.IEEE，2008：131-140.

[10]ZHOU J Y.Introduction to the constraint language NCL[J].The Journal of Logic Programming，2000，45（1/2/3）：71-103.

（责任编辑：党亚茹）

Integrative real-time airport gate assignment algorithm based on CDM

LIU Jun-qiang，ZHANG Ma-lan，CHEN Peng-chao，XIE Ji-wei，ZUO Hong-fu
（College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China）

Airport gate is one of the most primary resources of an airport，and real-time gate assignment has been paid more and more attention.To achieve appropriate real-time gate assignment under small-scale flight delays，a principle of minimum delay cost for multi-agent（airlines，airports and passengers）is established and an integrative real-time gate assignment model based on collaborative decision making（CDM）between airport and airlines is proposed.With mixed set programming（MSP）for modeling and optimization，not only the costs of ground taxiing of aircraft and the waiting of transfer passengers can be minimized，but also the increased fuel cost for the aircraft of the same type belonging to each airline can be balanced.Meanwhile，the flight banks of delayed flights can be connected effectively without adverse impacts on the interests of airlines.The illustrative example testifies that the collaboration between airport and airlines can be implemented，and the slot assignment as well as the gate assignment can be implemented through the integration of these algorithms in MSP，therefore both the operation cost and the computation time generated in the algorithm can be decreased.Analyses show that the proposed approach is qualified to serve as a guideline for practical operation of airport and airlines in air transportation.

flight delay；real-time gate assignment；flight bank；CDM；MSP

U8；V351

：A

：1674-5590（2014）06-0013-06

2014-04-22；

：2014-06-29

国家自然科学基金项目（61232002；60939003）；中国博士后面上基金项目（2012M521081）；中国博士后基金特别资助（2013T60537）；中央高校基本科研业务费专项（NS2014066）；江苏省博士后基金项目（1301107C）

刘君强（1978—），男，山东威海人，讲师，博士，研究方向为交通信息管理.