Top-k停机位推荐问题研究

吴彬林，梁磊，缪杨帆，李川（.国家金属制品质检中心，郑州　450000；.中国石化润滑油有限公司郑州分公司，郑州　450000；.四川大学计算机学院，四川　60065）

Top-k停机位推荐问题研究

吴彬林1，梁磊2，缪杨帆3，李川3
（1.国家金属制品质检中心，郑州450000；2.中国石化润滑油有限公司郑州分公司，郑州450000；3.四川大学计算机学院，四川610065）

0　引言

停机位是机场运营的重要资源，是飞机在地面活动的中心，合理高效地分配停机位是机场管理的重要内容［1］。停机位分配是指给未来一段时间内进离港航班的飞机分配一个停机位，以保证旅客正常有序的上下飞机。合理高效的停机位分配方案能很大程度上提高机场资源的利用率，提高旅客对机场和航空公司的满意程度。机场停机位分配问题是机场地面作业中的一项核心任务。如何分配好停机位，是一个很复杂的问题，需要考虑很多因素。文献［2］提出停机位物理特性，航班飞行时长，机场经营管理的商务约束，航班优先级，飞机停场时长，远停机位与靠桥停机位的选择等因素，这些因素都对停机位的分配起着至关重要的作用。

目前，研究人员对停机位分配问题进行了深入的研究，提出了大量的停机位分配模型，这些模型都在一定程度上提高了机场的运营管理效率。文献［4］将这些模型主要分为两类：一类是专家系统，基于分配原则建立知识库系统，考虑较多的非量化准则，文献［5］由知识的组成出发，给出基于关系型数据库的通用知识库结构设计，同时用拆分规则的形式化方法表示知识，来完善地表达事实规则体系知识，使推理过程简单、高效；另一类是基于数学规划的方法，建立目标函数，进行优化求解。文献［6］、［7］、［8］考虑的主要目标函数实质是一致的，都是使旅客满意度最优化。文献［3］、［9］、［10］则通过机场运营角度来考虑优化停机位分配问题，具有较好的鲁棒性，减少航班延误带来的影响。但随着问题影响因素维度的增加，解空间将呈爆炸式增长，随机算法难以得到全局最优解。基于专家系统的方法往往受制于搜索范围，忽视关键因素而导致分配结果不理想；后一方法受目标函数的影响很大，优化的维度很多时，将导致计算量的指数级增长，并且会经常出现将较多的航班分配给较少的有吸引力的停机位的情况。

文献［11］指出基于统计分析的方法在自然语言处理、语音识别、多媒体及推荐系统等领域中，都有很广泛的应用，且已取得较好的效果。因此，本研究采用统计分析的思想来进行停机位分配。首先，停机位分配的历史数据中已经潜藏着大量的知识信息；其次，这些知识是不能穷尽列举出来，如曾采用过多种优化方法进行停机位分配，则对历史停机位分配数据的统计分析就能得到更均衡的分配方案。再次，停机位分配不得不需要业务员的参与，新业务员往往缺乏经验，而对历史数据进行分析，然后推荐分配停机位，能让新业务员对停机位分配有据可依。

1　基于统计分析的停机位分配推荐模型

停机位分配需满足固定强规则（商务规则、停机位与飞机规格约束和固定停机位等）和适当弱规则（航班优先级相关规则，如，停场时间、旅客数量等）。经过规则的过滤得到初步的候选停机位，然后利用训练出的停机位分配模型推荐Top-k个停机位。

对每个航班赋予一个优先级P，x是需要考虑的弱规则，而β是各规则对应的权重，根据不同阶段实际的需求可以调整各个规则的权重，达到按需优先的目的。也可以拟合数据得到适当的权重参数。

推荐停机位概率：

xi为弱规则，k为航班，y为停机位。对训练数据进行统计分析，运用贝叶斯方法，可算出弱规则集X下，分配停机位y概率。按概率进行排序后，得到Top-k个推荐停机位。

例如，现有航班3U8555和8Y9034机型分别为320和738，降落时间同为早上八点十分，利用弱规则算出这两个航班的优先级，假设算出的优先级3U8555高于8Y9034，则在航班优先级队列中3U8555位于队首，8Y9034位于其后，从优先级队列中取出优先级最高的航班3U8555，用强规则 （航空公司3U机型320等）过滤出可用停机位列表，再利用航班信息和可用停机位列表应用推荐模型得到分配概率最大的k个停机位。该例只是简要的介绍模型功能，实际中的优先级计算和强规则过滤是比较复杂的过程。

模型执行流程如图1所示。

2　数据说明

实验数据采用了某机场2012年5月1日至2013 年4月10日的产生的航班信息，里面包括了航班号、机型、起降时间、延误信息、载客数等。还包括各航空公司信息数据以及该机场的停机位-机型约束数据，停机位基础信息数据，停机位-任务数据和停机位优先规则数据。

图1　基于统计分析的停机位分配推荐系统流程图

筛选出的航班属性如下：

航班编号，飞机型号，航线，停机位，降落时间，起飞时间，进港人数，离港人数。

经过预处理后提取出的数据用JSON格式表示如下：

各字段如表1所示：

表1　停机位信息表

对历史数据的训练结果trainResults.json

因为不同时段，停机位分配的策略有很大差异，比如：早上、中午和下午到达的过夜飞机倾向于远停机位停靠，而晚间飞机更多靠桥停靠。为了利用这些知识，可将航班按时间段划分为四个区间，如表2所示：

表2　时间段标识码表

训练结果中的key值中包含了时段的信息，value值代表了A航空公司B机型C时段停在Dk停机位的频数，表示为S（Dk|A，B，C），那么A航空公司B机型C时段停在Dk停机位的条件概率为：

3　Top-k停机位推荐KGatesRec算法

该KGatesRec算法伪代码如下：

航班的选取策略：如果flights队首航班为出港航班，则直接选取该航班并返回；如果flights队首航班为入港航班，则在冲突时间范围（10分钟）内的进港航班中选取权重最高的航班。

●allocateAGate（flight）：为一个航班获取推荐停机位。具体步骤如下：

●根据bitMapOfGates获取机场空闲停机位集合totalGates。

（1）根据GatesInfo选出航班满足停机位-航空公司和停机位-机型约束的停机位集合companyAndType-Gates。

（2）对totalGates和companyAndTypeGates求交集得到可用停机位集合emptyGates。

（3）对emptyGates中的停机位，结合航班信息查询trainResults中的数据，按照频次进行排序，选前k个停机位，得到Top-k推荐停机位列表recGates，并返回。

半柔性路面作为一种新型路面结构，是将一定级配的水泥砂浆灌入到大空隙母体沥青混凝土中，具有高于水泥混凝土柔性和沥青混凝土刚性的特点。半柔性路面在国外已进行了大量的研究和应用，实际工程中表现出良好的高温性能、水稳定性等使用性能，且具有较小的线收缩系数。但国内对半柔性路面的研究仍处于起步阶段，对原材料指标、级配和施工工艺没有统一的技术标准。本文针对高性能半柔性路面，结合实际工程的应用，提出一套系统的施工工艺和质量控制标准，为以后半柔性路面技术的应用奠定基础。

●updateBitMapOfGates（flight，flights）：更新停机位位图表。

因为是从实际的历史数据出发，并不能真正得到某时刻完全正确的停机位状态。本研究假设机场在执行若干天航班后，停机位的占用状态接近真实的状态，这样就得到了某一时刻接近真实的停机位状态。晚间飞机通常会分配在靠桥停机位，然后依据该飞机第二天计划航班情况可能会被调整到远停机位，而数据当中缺少停机位调整的相关信息，这样必定会造成一定的误差。可以依照第二天实际安排航班情况来确定停靠在该靠桥停机位的飞机是否调整到远停机位过夜。具体策略如下：

（1）如果该飞机今天不过夜，则飞机进港停机位分配后，对停机位加锁，并更新对应离场航班的停机位，飞机离港后对停机位解锁。

（2）如果是过夜飞机，离港时如果停机位为空，则说明对该飞机的停靠停机位进行过调整，需要在未加锁的停机位中找出同航空公司同机型的飞机，并将该停机位占用状态置空。

4　实验

实验的训练数据是采用某机场自2012年5月1日至2013年4月10日产生的航班数据。用2012年8 月21日数据来估算停机位占用状态，测试数据为2012 年8月22日的航班，其中进港航班334次，出港航班335次。

航班的优先级计算选取了停场时间和进出港人数这两个特征，权重分别设定为1和1/200，Top-k中k值取10，即每次推荐十个停机位。

4.1实验环境

操作系统：Microsoft Windows 7旗舰版（64位）

处理器：Intel Core i5-2450M CPU@2.50GHz

内存：4.00 GB（1333 MHz）

运行平台：Python 2.7［12］［13］［14］

4.2实验结果

表3列出了2012年8月22日航班数据的部分测试情况，各字段意义如下：

序号：航班的执行顺序。航班号：规定的航班号。航线：飞机飞行的路线。

航班类型：O-说明执行的航班为出港航班；I-说明执行的航班为进港航班。

进离港时间：航班类型为O，为进港时间，航班类型为I，为出港时间。

另外，本研究还对实验的结果进行了统计，图2～图6显示了一天中各个时段和全天的推荐命中情况，其中推荐命中指的是与历史数据中业务员的分配结果一致。X轴表示命中时命中的停机位在推荐列表中的位置，Y轴表示命中次数。

表3　2012年8月22日部分航班执行情况表

例如，图2中X=1，Y=21表示推荐列表的第一个结果命中的次数为21次，而X=0，Y=13表示实际的分配结果不在推荐列表中次数为13。

图7显示的是各时段top-10总体命中情况，命中率均在60%～80%之间。图8显示的是不同k值对推荐精度的影响。

图2　早上推荐命中情况

图3　中午推荐命中情况

图4　下午推荐命中情况

图5　晚上推荐命中情况

图6　全天推荐命中情况

图7　各时段总体命中情况

4.3实验分析

本研究在实验过程中发现，推荐列表没有命中的时候，绝大多数是因为该时段该航空公司的该机型数量很少（或许属于非固定航班），从而导致推荐列表中推荐列表中大部分停机位频数都为1，表现出对该时段该航空公司该机型停机位分配的随机性。

图8　不同top-k命中情况

推荐命中的精度也与时段有关，在图7中可以发现，早上和晚上的推荐精度比中午和下午的推荐精度要高，早上推荐精度较高是因为出港的航班较多（进港52，出港68）；中午进出港航班数几乎持平（进港102，出港100）命中率略微下降；下午的进港航班数（68）大于出港航班数（54），导致机场拥堵情况加剧，从而命中率降低；而晚上进出港航班数几乎持平（进港112，出港111），命中率较下午要高。

对于不同k的取值，推荐命中精度也有很大的不同。推荐命中精度随着k值的增大而增大，当k增大到6之后增速会明显减缓，而且k取值越大，推荐的价值就越小，因此选取合适的k值也是影响推荐精度的一个重要方面，实验结果表明k取值3～6较为合适。

5　结语

停机位分配是机场运营管理的关键环节。合理高效的停机位分配方案，能提高机场的运营效率，使机场和航空公司达到双赢。本研究采用基于统计分析的全新方法，来解决停机位分配问题。通过挖掘历史运营数据中潜藏的大量知识信息，构建了一个停机位分配推荐模型，并提出了对停机位分配进行Top-k推荐的KGatesRec算法。

本研究在真实的数据集上进行实验，实验结果证明了该模型的有效性，本研究也从多个方面对实验结果进行了分析，合理解释了算法的有效性。

未来的工作，主要包括对停机位进行聚类分析［17］，视同一类的停机位等效，再进行推荐；考虑更多的航班信息来计算优先级，例如航班延误率、航班任务类型和离港时间等。

［1］高菁，杨旭东.基于规则的机位分配问题研究［J］.计算机科学，2012，39（z1）.

［2］伍岭.机位分配背后的学问［J］.中国民用航空，2007，07:51-52.

［3］刘兆明，葛宏伟，钱锋.基于遗传算法的机场调度优化算法［J］.华东理工大学学报（自然科学版），2008，03:392-398.

［4］杨守剑，白存儒.机场停机位优化分配研究［J］.航空工程进展，2010，03:301-305.

［5］周至，孟波.机场机位自动分配系统知识库的研究与设计［J］.计算机工程，2004，06:145-147+161.

［6］Xu J.，Huo C.The Airport Gate Assignment Problem:Mathematical Model and a Tabu Search Algorithm［C］.Proceedings of the 34th Hawaii International Conference on System Sciences，Hawaii，2001：102-111.

［7］Ding H.，Lim.A.，Rodrigues B.，Zhu Y.Aircraft and Gate Scheduling Optimization at Aitports［C］.Proceedings of the 37th Hawaii International Conference on System Sciences，Hawaii，2004：74-81.

［8］王力，刘长有，涂奉生.民用机场停机位优化配置［J］.南京航空航天大学学报，2006，38（4）：433-437.

［9］Bolat A.Models and a Genetic Algorithm for Static Aircraft-Gate Assignment Problem［J］.Journal of the Operational Research Society 2001，52：1107-1120.

［10］Lim A.，Wang F.Robust Airport Gate Assignment［C］.Proceedings of 17th International Conference on Tools with Artificial Intelligence，Hong Kong，November 14-16，2005.

［11］吴军.数学之美［M］.第1版.北京：人民邮电出版社，2012.

［12］Punch W F，Enbody R.The Practice of Computing Using Python［M］.Addison-Wesley Publishing Company，2010.

［13］Chun W J.Core Python Programming［M］.Prentice Hall PTR，2006.

［14］Hetland M L.Beginning Python:from Novice to Professional［M］.Dreamtech Press，2008.

［15］Ross S M.Introduction to Probability Models［M］.Academic press，2006.

［16］盛骤，谢式千，潘承毅.概率论与数理统计［J］.北京:高等教育出板社，2006.

Aircraft Parking Location Allocation；Top-k

Research on the Aircraft Parking Position Recommended Using Top-k Optimization

WU Bin-lin1，LIANG Lei2，MIU Yang-fan3，LI Chuan3
（1.National Metal Products Quality Inspection Center，Zhengzhou 450000；2.Sinopec Lubricating Oil Co.，Ltd.Zhengzhou Branch，Zhengzhou 450000；3.School of Computer Science，Sichuan University，Sichuan 610065）

1007-1423（2016）18-0003-06

10.3969/j.issn.1007-1423.2016.18.001

吴彬林（1969-），男，工程师，研究方向为数据库及应用

梁磊（1973-），男，工程师，研究方向为数据库及应用

缪杨帆（1994-），女，在读研究生，研究方向为数据挖掘

李川（1977-），男，副教授，博士，研究方向为数据库、数据挖掘，Email:lcharles@scu.edu.cn

2016-05-17

2016-06-05

停机位分配是机场运营管理的关键技术环节，合理高效的停机位分配策略能在很大程度上提高机场的运营效率，使航空公司和机场达到双赢。基于统计分析的思想，对往期停机位分配数据进行统计，得到停机位分配策略模型，再结合推荐系统的模式，为业务员提供Top-k个分配停机位推荐服务。这种利用历史数据经过训练得到的模型，使得新手业务员能借鉴资深业务员的分配经验进行停机位分配，从而提高机场运营效率，也能避免由业务员疏忽大意而造成的损失。实验表明基于统计分析的Top-k停机位推荐方法，具有较好的推荐覆盖率和准确率。

停机位分配；Top-k

Aircraft parking location allocation is the key technology of airport operation management，reasonable and efficient aircraft parking location allocation strategy can largely improve the operational efficiency of the airport，make the airlines and airports to achieve a win-win situation.Based on the statistical analysis of the previous allocation of aircraft parking position data and statistics，obtains the position assignment policy model，combined with the recommender system model Top-k were allocated parking location for sales referral service. Uses historical data，with training the model，makes newbie salesman to benefit from the allocation of senior sales experience in the allocation of parking bays，so as to improve the operational efficiency，it can avoid by sales losses due to negligence.Experiments show that stands at Top-k recommendation method based on statistical analysis，and recommended better coverage and accuracy.