进港航班排序强化学习模型研究

1、进港航班排序强化学习模型研究武喜萍，杨红雨，杨 波*（四川大学 视觉合成图形图像技术国防重点学科实验室，四川 成都 610065）摘 要中英文摘要请扩展。方法部分请多说明几句。摘要的问题：中文500字左右（至少写到400字吧）。重点突出方法、结果、结论部分，陈述得更详细一些，但勿与引言最后、结论完全相同。若需扩充研究目的，请说明清楚问题即可，勿增加太多背景介绍。具体要求请见网站左侧下载专区的中英文摘要要求。中文摘要（目的-方法-结果-结论）：A直接介绍研究目的，研究目的是否概括完全。如“针对问题”、“为了解决问题”，之后一句话“提出了什么方法”之类的概括性描述（即合并现在的第12句话）。B概述

2、方法的具体内容，怎么做的，突出创新之处。c仿真结果和结论分开说明清楚。做了哪些仿真和性能分析，结果如何？再总结结论。：为了解决进港航班排序中智能化程度不高的现实问题，提出了进港航班排序强化学习模型。首先确定了进港航班排序强化学习模型的状态、动作、智能体、环境、奖赏函数、约束条件、Q学习等，进港航班排序强化模型中的状态是各进港航班的到达时刻，动作是对航班到达时间的调整，智能体对航班的到达时刻进行调整，环境对动作做出反应，一个新的到达时间和奖赏值传给智能体。奖赏函数考虑了延误时间、经济成本、对后续航班的影响。该模型考虑了航班不能提前降落，分配的到达时间不早于计划的到达时间，进港航班流量不能超过机场

3、的到达容量值等约束条件。使用双流机场进港航班数据对该模型进行了验证。对比分析了先到先服务和强化学习模型的排序、延误时间、延误成本、后续航班延误成本和奖赏值。先到先服务算法的奖赏函数值为3164，强化学习算法的奖赏函数为2880，强化学习模型更优。模型中奖惩函数的评价指标、权重、约束条件可以根据管制工作实际情况进行设置，该模型可以为空中交通管制人员进行进港航班排序提供决策支持。关键词：智能体;空中交通;空中交通管制;机器学习;强化学习中图分类号： V355 文献标志码：AResearch on Reinforcement Learning Model of Arrival Flights Sch

4、eduling WU Xi-ping, YANG Hong-yu, YANG Bo* (National Key Laboratory of Fundamental Science on Synthetic Vision, Sichuan University, Chengdu 610065, China)Abstract:英文只哎哟请务必对应中文修改。英文摘要尽量对应中文摘要翻译，英文摘要要求是包括研究目的、研究主要方法或过程、具体的结果和结论的一篇短文。需注意英文摘要的润色以及涉及的方法、过程及结果部分一般采用一般过去时、被动语态，勿用第一人称、主动语态。英文摘要首句直接用“In orde

5、r to”句式，不然很容易在英文编辑修改中当成研究背景而被删除。可参照网站上中英文摘要写作要求。 In order to solving the problem of low intelligence of arrival flights scheduling, arrival flights scheduling reinforcement learning model was proposed. First of all, the states, actions, agent, environment, rewards, constraint and Q learning of the m

6、odel were defined. The state of arrival flights scheduling reinforcement learning was the arrival time of each arrival flight. The action of the model was the adjustment of the arrival time. The arrival time was adjusted by agent, the environment responded to the action, then a new arrival time and

7、reward value were passed to the agent. The delay times, delay cost and impact on subsequent flights were chosen as the rewards. At the same time, the model considered the flight can not advance landing, the distributed arrival time was not earlier than the schedule arrival time and the arrival flow

8、of the airport can not exceed the arrival capacity of the airport. The model was validated using of Shuangliu airport real flight data. First come first service model and reinforcement learning model were compared and analyzed from sequence, delay time, delay cost, delay cost of subsequent flights a

9、nd rewards. The rewards value of first come first service model was 3164. The rewards value of reinforcement learning model was 2880. Reinforcement learning model was superior to first come first service model. The evaluation index, weight, constraint can be adjusted according to air traffic control

10、 actual working conditions. The model provided decision-making for air traffic controller.Key Words: agent; air traffic; air traffic control; machine learning; reinforcement learning随着我国民航运输业的飞速发展，运输总周转量、旅客运输量和货邮运输量大幅增长，致使飞行流量剧增，航班延误日趋严重，尤其在繁忙机场和高密度空域延误问题更加突出。飞机排序是终端区飞行流量管理的收稿日期： 基金项目: 国家空管委科研课题“军民航

11、空管联合运行一体化模拟训练技术研究”（GKG201403004）作者简介：武喜萍（1983），女，博士生.研究方向:空中交通管理.E-mail: *通信联系人 E-mail: boyang网络出版时间: 网络出版地址: 主要措施，对进港航班排序进行研究具有重要意义。当终分段？端空域出现拥挤时，从不同方向、不同距离、不同高度、不同速度、不同航线上的多架飞机在同一时刻向同一机场的同一跑道进近，最后排成一列依次降落在跑道上，所有飞机的到港顺序及每架飞机所需的延误时间完全依靠管制员来调整，这不仅增加了管制员的工作负荷，而且根据经验很难达到最优，因此，国内外一些学者提出了一些方法。如时间提前算法、约束位

12、置交换算法、滑动窗优化算法、模糊综合评判方法1等。时间提前算法对每个飞机队列的第一架飞机实施控制，不改变整个队列的原有顺序。约束位置交换算法对所有可能的飞机排序方式进行搜寻，找到一种成本最小的排队序列。滑动窗优化算法对窗口内的航班进行优化排序，减少了计算量。模糊综合评判算法综合考虑各方面因素的作用及与人相似的管制决策过程，得到最终的航班队列。进港航班排序问题是一个典型的NP优化问题，针对这个问题很多学者提出使用遗传算法2-3、蚁群算法4、鱼群算法5-6、粒子群算法7等方法。上述研究成果虽然丰富，但仍存在以下不足：1）目前进港航班排序算法优化目标主要考虑了延误成本8-11，忽略了延误成本、后续航

13、班等因素；2）机场运行的影响考虑较少；3）传统优化算法连续决策能力不足。强化学习通过感知环境状态信息学习改进行动方案以适应环境达到预想的目的，是解决连续决策的一种有效方法。国内外一些学者研究了强化学习在空中交通领域的应用。具体内容是什么？引言请注意：引言综述这部分请务必说明不足。1）背景可以简略，针对主要背景提出研究意义。2）引言第2部分综述国内外现有的研究文献并说明其不足，综述时需要明确提出存在的不足，这些不足为后续本文方法的创新性做好铺垫。3）最后一段提出论文的创新点时，需要突出论文方法优越性（勿与摘要叙述语句上相同，可比摘要更具体，此处可不说或少说结果或结论）。Balakrishna P

14、oornima等使用马尔科夫链模拟影响航班滑出时间的机场状态，运用强化学习方法预测航班滑出时间12。Elizabeth George等运用Q学习预测一个机场航班的滑出时间，将预测的滑出时间与实际的滑出时间进行对比降低预测误差13。Leonardo L.B.V.C等研究了将强化学习方法应用于地面延误程序中14。就已知国内外文献来看，尚未发现强化学习方法在进港航班排序方面的应用。针对进港航班排序的现状和强化学习在辅助决策中的优势，作者将强化学习方法应用于进港航班排序中，提出了进港航班排序强化学习模型，使用实例进行验证，并对求解结果进行对比分析。1 强化学习机器学习分为监督学习、非监督学习和强化学习

15、。强化学习是一种重要的机器学习，它的思想来源于人类对动物学习过程的长期观察，被广泛应用于智能控制、机器人以及决策分析等领域。强化学习通过试错与环境进行交互，将环境状态映射到动作，其目标是使累加报酬最大。智能体（Agent）选择一个动作a用于环境，环境接受该动作a后状态s发生变化，同时产生一个奖赏r反馈给Agent，Agent根据奖赏r和环境新的状态再选择下一个动作，选择的原则是使受到正的奖赏的概率增大。强化学习基本模型如图1所示。图1 强化学习基本模型Fig.1 The basic model of reinforcement learning强化学习方法的研究建立在马尔可夫决策过程（Mark

16、ov Decision Processes, MDP）相关理论框架上的。在MDP中，智能体（Agent）感知其所处环境的不同状态集合S，并且可执行动作集合A。通过MDP可直接对强化学习问题进行建模。MDP由一个五元组构成：下面的变量改为，式中，可以接排。式中，为系统所有环境状态的集合，为状态的动作集合， 为在状态采用动作转移到状态的概率， 为在状态采用动作转移到状态的瞬时奖赏， 为对各状态奖赏累加后的评价函数。某个Agent的初始状态为，从中挑选一个动作执行后，Agent按照概率转移到下一个状态，然后再执行一个动作转移到状态，接下来再执行，整个过程如下， （1）奖赏之和为：（2）已经处于某个状

17、态时，以一定策略来选择下一个动作执行，然后转换到另一个状态，这个动作的选择过程称为策略。策略是状态到动作的映射，采用累计折扣奖赏值度量策略的好坏： （3）为时刻的状态，为时刻采取的行动。强化学习的任务就是找到一个最优策略，使累积折扣奖赏值期望值最大。 （4）Q学习是一种模型无关的强化学习算法。Q学习不估计环境模型，直接优化一个可迭代计算的Q函数。Q值的修正公式如下式： （5）哪些量是黑斜体？都不是黑斜体，Q(s,a)是后面公式（12）矩阵的一个元素，一般斜体表示式中为当前状态，为状态下可执行的动作，为后续状态，为状态下可执行的动作，为奖赏，为学习率，为折扣率。在已知有限离散状态和行为空间Mar

18、kov决策过程的状态集S、行为集A和目标函数的情况下，可以以表格形式存储行为值函数估计值Q（s, a）及行为选择策略。2 进港航班排序强化学习模型进港航班排序强化学习模型由状态、动作、Agent、环境、奖赏函数和Q学习组成。2.1状态和动作进港航班排序强化模型中的状态是各进港航班的到达时刻，航班的预计到达时刻为初始状态。航班所有可分配的到达时刻构成状态集。动作是对航班到达时间的调整。在满足机场到达容量和进港航班不能提前降落的限制下，动作对状态进行调整。在航班当前状态所有可行的调整构成了动作集。2.2 Agent和环境进港航班排序的主体是Agent，Agent之外，与之交互的是环境。Agent与

19、环境之间的交互是持续不断的，Agent对航班的到达时刻进行调整，环境对动作做出反应，一个新的到达时间和奖赏值传给Agent。2.3 奖赏函数进港航班排序的目标是使进港航班总延误时间最少、延误成本最小、对后续航班影响最小，基于这3个目标建立进港航班排序强化学习模型的奖赏函数。延误时间最少 （6）式中，为航班集合，为航班分配的到达时间，为航班预计到达时间，航班延误为1，否则为0。延误成本最小 （7）式中，为航班集合，为航班分配的到达时间，为航班预计到达时间，航班延误为1，否则为0，为航班延误单位成本。后续航班影响最小 （8）式中，为航班集合，航班有后续航班时为1，否则为0；为航班延误单位成本；航班

20、延误为1，否则为0；为航班分配的到达时间，为航班预计到达时间。约束条件： （9）航班不能提前降落，分配的到达时间不早于计划的到达时间。 （10）进港航班流量不能超过机场的到达容量值。根据目标函数和约束约束条件确定的奖赏函数为： （11）式中，是奖赏函数，是延误总时间，是延误总成本，是后续航班延误成本，和为权重，和为1。2.4 Q学习进港航班排序强化学习模型的状态集S、动作集A和目标函数均已知，以矩阵表示智能体所学到的知识，当矩阵达到收敛状态，满足整个学习条件，终止学习。表示状态，表示动作，是状态为动作为根据Q值修正公式得到的最大Q值。 （12）3 模型验证与分析选用成都双流机场19：00至20

21、：00之间的20架进港航班进行模型验证，如表1所示。表1中列出了进港航班的航班号、机型、尾流类型、是否有后续航班，1表示有后续航班，0表示没有；ETA表示航班的预计到达时间。表1 进港航班数据Tab.1 The data of arrival flights编号航班号机型尾流后续航班ETA13U8886A321M119:002CA1407789H119:003EU2710A320M019:054CA4506A321M119:055EU2720A320M119:1063U8964A320M019:157FM9549A330M119:158JD5136A320M119:209MF8447B737M

22、119:2510CA408A319M019:2511MU5864B737M019:25129C8664A320M119:25133U8668A320M119:3014CA4404A319M119:3015NS3209B737M119:35163U8704A321M119:35173U8734A320M119:40183U8858A320M119:40198L9606B737M019:4520EY818A330M119:45不同尾流类型的飞机的延误成本不同，重型机延误成本设置为4000元/h，中型机延误成本3000元/h，轻型机延误成本200元/h。机场的到达容量为20架/h。先到先服务算法和强

23、化学习方法的进港航班顺序如表2所示，ETA表示航班预计到达时间，CTA表示分配的到达时间。先到先服务算法和强化学习方法的进港航班的延误时间、延误成本、后续航班延误成本，总的延误时间、总的延误成本、总的后续航班延误成本如表3所示。进港航班排序强化学习模型的权重设为1/3，先到先服务算法的奖赏函数值为3164，强化学习算法的奖赏函数为2880。进港航班排序强化算法的总延误成本、后续总延误成本更低，奖赏函数值更小，实际运行效率更高。表2 进港航班排序结果Tab.2 The result of arrival flights Scheduling编号航班号ETAFCFS强化学习CTA排序CTA排序13

24、U888619:0019:00119:0322CA140719:0019:03219:0013EU271019:0519:06319:0944CA450619:0519:09419:0635EU272019:1019:12519:12563U896419:1519:15619:1877FM954919:1519:18719:1568JD513619:2019:21819:2189MF844719:2519:25919:25910CA40819:2519:271019:301111MU586419:2519:301119:3312129C866419:2519:331219:2710133U86

25、6819:3019:361319:361314CA440419:3019:391419:391415NS320919:3519:421519:4215163U870419:3519:451619:4516173U873419:4019:481719:4817183U885819:4019:511819:5118198L960619:4519:541919:572020EY81819:4519:572019:5419表3 进港航班延误时间和延误成本Tab.3 Delay times and delay cost of arrival flights编号航班号FCFS强化学习延误时间延误成本后续航

26、班延误成本延误时间延误成本后续航班延误成本13U888600031501502CA140732002000003EU27101500420004CA45064200200150505EU27202100100 210010063U8964000 315007FM95493150150 0008JD513615050 150509MF8447000 00010CA40821000 5250011MU586452500 84000129C86648400400 2100100133U86686300300 630030014CA44049450450 945045015NS32097350350

27、7350350163U870410500500 10500500173U87348400400 8400400183U885811550550 11550550198L960694500 12600020EY81812600600 9450450总和14151004250141505034504 结 论最后请补充进一步研究工作。针对进港航班排序问题，考虑了总延误时间最少、延误成本最小、对后续航班的影响最小3个目标，提出了进港航班排序强化学习模型。定义了模型的状态、动作、智能体、环境、奖赏函数、限制条件等，使用双流机场进港航班数据对该模型进行了验证。强化模型的总延误成本、后续总延误成本更低，奖赏

28、函数值更小，实际运行效率更高。模型中反映优化目标的奖惩函数的评价指标、权重可以根据实际情况进行设置，该模型具有较强的实用性。需要进一步研究的问题有：1）针对中国民航大区域机场群的发展趋势和多机场协同运行需求，研究基于强化学习的多机场进港协同排序技术，科学调度多机场的航班。2）综合考虑机场停机位、跑道构型等机场资源和空管运行限制，研究进离场航班协同排序。参考文献：1 Xu Xiaohao, Huang Baojun. Study of fuzzy integrated judge method applied to the aircraft sequencing in the terminal

29、areaJ.Acta Aeronautica Et Astronautica Sinica,2001,22(3):259-261.徐肖豪,黄宝军.终端区飞机排序的模拟综合评判方法研究J.航空学报,2001,22(3):259-261.2 Yang Qiuhui, You Zhisheng, Feng Ziliang, et al. Scheduling arrival aircrafts on multiple runways based on an improved genetic algorithm J. Journal of Sichuan University: Engineering

30、 Science Edition, 2006,38(2):141-145.杨秋辉,游智胜,冯子亮,等. 一种改进的基于遗传算法的多跑道到达飞机调度J.四川大学学报:工程科学版, 2006, 38(2):141-145.3 Li Yaohua, Qin Ruru. Study on flight string model based on mixed genetic algorithm J.Journal of Civil Aviation University of China, 2010, 28(6):31-34.李耀华,秦如如.基于混合遗传算法的航班串优化模型研究J.中国民航大学学报,20

31、10,28(6):31-34.4 Wang Shidong, Zhang Yue, Zhang Zhihai, et al. Multi-objectives optimization on flights landing sequence at busy airport J. Journal of Transportation Systems Engineering and Information Technology,2012, 12(4):135-142.王世东,张越,张智海,等.繁忙机场航班降落排序的多目标优化J.交通运输系统工程与信息,2012,12(4):135-142.5 Wan

32、g Fei, Xu Xiaohao, Zhang Jin.Mixed artificial fish school algorithm of aircraft sequencing in terminal area J. Journal of Traffic and Transportation Engineering, 2008, 8(3):68-72.王飞,徐肖豪,张静. 终端区飞机排序的混合人工鱼群算法J. 交通运输工程学报,2008, 8(3): 68-72.6 Dong Bing, Du Wen. Scheduling arrival aircrafts on multi-runwa

33、y based on an improved artificial fish swarm algorithmC/2010 International Conference on Computational and Information Sciences. Oakland:IEEE Press,2010:499-502.7 Wang Shihao, Yang Hongyu, Wu Xiping, et al. Research on optimization mathematical model of arrival flights scheduling J.Journal of Sichua

34、n University: Engineering Science Edition, 2015,47(6):113-120.王世豪，杨红雨，武喜萍，等.进港航班排序优化数学模型研究J.四川大学学报:工程科学版, 2015,47 (6):113-120.8 Ying Shenggang, Sun Fuchun, Hu Laihong, et al. Multi objective dynamic programming algorithm for aircraft arrival sequencing and runway scheduling J. Control Theory and Applications, 2010, 22(7): 827-835.应圣钢, 孙富春, 胡来红, 等.基于多目标动态规划的多跑道进港排序J.控制理论与应用,2010, 22(7): 827-835.9 Xu Xiaohao, Li Xiong. Cost analysis