航空航天港

 找回密码
 注册会员

QQ登录

只需一步,快速开始

航空航天港 首页 民航 空管技术 查看内容

航班离场调度规划算法研究

2014-10-13 17:22| 发布者: 潜艇4809| 查看: 2107| 评论: 0|原作者: 周毅|来自: 民航资源网

摘要:   近年来,随着我国民航运输业的快速发展,民用航空器的数量持续高速增长,飞行流量不断加大,与此同时也带动了航空运输量的持续高速增长,这种客观趋势也对如今的民航建设和管理提出了更高的要求。

  近年来,随着我国民航运输业的快速发展,民用航空器的数量持续高速增长,飞行流量不断加大,与此同时也带动了航空运输量的持续高速增长,这种客观趋势也对如今的民航建设和管理提出了更高的要求。通过空中交通管制设施的改善(如机场的扩建,通信和导航设备的升级)已经不能为提高空中交通管制容量带来更为有力的帮助,需要我们从空中交通管制的方式找到突破口,其中完成对离场航班的优化调度作为解决问题的一个有力手段。

  针对离场调度中的两个核心问题,即单跑道运行机场的离场航班排序和多跑道运行机场的跑道分配问题,Gautam[1]等建立了一个混合整数线性规划模型用于机场离场的规划,具有一定的通用性,但仅限于单跑道机场或多跑道运行模式下仅用于起飞的跑道,且解算不能满足实时性要求。Ioannis[2]等建立了一个机场离场过程分析动态排队模型,将跑道配置,气象条件,停机坪位置和起飞队列长度作为模型的输入,相应得到场面的拥塞水平及航空器预计滑出时间。该模型仅能给出单一的统计计算结果,并未考虑进离场航班流的相互影响。Shumsky[3]提出了一个机场容量和滑行迟滞的模型用于预测离场航班时间。对于多跑道多目标问题,现有的算法大多针对多跑道单目标或单跑道多目标[4-9],鉴于目前很多大型机场都有多条跑道,一些只有单跑道的机场也正在准备增加跑道,因此本文讨论着重分析了多跑道情况下航班进离港的跑道分配和排序问题。

  本文将离场调度分为两个阶段(排队阶段和跑道分配阶段)进行研究,分别对两阶段的研究进行总结分析,找出了各种算法潜在的不足,结合各种调度方法的优势,提出针对不同跑道运行方式和配置下的可行的运行方案和下一步研究中需要解决的问题。

  1 离场调度问题描述:

  在空中交通管理中,机场的航班调度是其中至关重要的一环,其又分为到场调度和离场调度,航班到场调度的研究比较多,故本文研究航班的离场调度问题。离场飞机的序列优化问题与进场飞机有所不同,目前实际运行中大多数离场飞机的调度策略是优先安排进场飞机占用跑道,然后利用跑道的空闲时隙安排离场飞机适时起飞。因此,在考虑离场队列排序和跑道调度问题时需要对跑道的占用情况进行考虑。

  所谓的离场过程就是指航班从停机位推出一直到加入航线飞行的整个过程[10]。本文则主要针对其中的地面运行部分,包括起飞前的推出阶段和滑行阶段。当机场非常繁忙的时候,由于同一阶段推出的航空器数量较多,导致在滑行道头出现拥挤,需要对这些航班进行队列排序和跑道分配。因此,航班离场调度的实质就是对一定时段内的离场航班进行优化排序,使得跑道被充分利用并能够有效减少航班在机场上空的滞留。

图1 离场过程流程图[11-12]

  2 离场队列排序方法分析

  离场排序就是对飞机的起飞次序位置按照某种标准进行重新排列,使得由于交通拥挤造成飞机延误所带来的影响最小[13]。对于离场队列排序问题,研究人员提出了许多排序算法和建模仿真方法,主要可归为以下几类:

  2.1 整数线性及其他规划方法

  该类方法[1-3]涉及不同的方案,他们分别通过对排队区域的不同处理以应用到不同的场景中(见图2),比如分别可以将离场排队区域看作是先进先出队列或者一个简单的停泊区(其中任何航空器均可提前起飞而无需考虑队列中与其他航空器的相对位置)。同时该方法明确考虑了连续离场航班之间以及不同重量类型的航空器之间的离场间隔标准问题(见表一),包括在同一定位点离场的情形,并采用一个时间窗将一个可选优先级方案纳入其中。

图2 滑行道航班排序队列三种分类图

  1.各个队列保持先进先出的结构的多个队列情形。任何离场航空器可以被指派到任一队列,且航空器在分配之后不得更改队列。

  2.由滑行道决定所选离场队列的多个队列情形。换句话讲,队列的分配对某一航空器是一个输入约束。队列依旧遵循先进先出结构,且不得改变所选队列。

  3.先进先出没有队列的情形;任一航空器可以在任意时刻使用跑道。比如说,接入区域有三个排队通道组成,这可以通过调整航空器在靠外的两个通道行驶而空出中间的一个通道来实现。任一取得离场许可的航空器可以转移到中间的通道上而不用考虑它在外侧通道上的位置。

表一 计算中使用的航班尾流间隔标准/min

前机     后机

重型H

大型L

中型M

轻型S

重型H

1.2

2.0

3.0

5.0

大型L

1.0

1.0

1.2

1.5

中型M

0.8

0.8

1.0

1.2

轻型S

0.5

0.5

0.8

1.0

  由于不同的利益攸关方对待离场计划问题有不同的侧重点,对此可以设置多个目标函数进行优化,对应效率,可以设吞吐量、系统延迟为目标函数;针对调度公平性,可以设置航班最大单个延迟或者建立联系各个航班间的基尼系数为优化目标。由此显示出模型构造的高灵活性,且具有一定的通用性,易于实现,能很好的对航班进行队列分配和离场时间进行控制,但是由于其边界约束条件较为复杂,由混合整数规划求得其整数解的解算周期较长,不能很好地用于实时管理中,相比较而言其在模拟离场航班流预测能够发挥很好的效用。

  2.2 基于滑动排序窗算法

  在对航空器排序优化时,真正意义上的优化算法需要对等待排序的航空器进行全排列,分别计算成本并从中选出最优解。但在多数情况下,随着飞机数量的增加,其所需要循环计算的量级会呈指数性的扩大,由此带来严重的运算问题。与其他方法不同,采用滑动排序窗算法(见图3)可以不用对队列中全部航空器可能排序进行搜索,而只需要对某些特定位置相关所产生的可能排序进行搜索,依次移动窗体即可完成全部排序。

图3 基于滑动窗的优化过程示意图

  该类方法[13-14]最突出的优点是解决了航空器队列过长引起循环计算量以及多架飞机参与排序时编码空间不足的问题,同时能够兼顾计算机的可行性,比较适用于航空器长队列情形。此外,使用该方法可以避免队列次序出现较大波动,具有一定的公平性,可行性较高,能够有效减轻管制员的工作负荷,且对于单条跑道多条滑行道等待队列以及多条跑道具有通用性。然而该类方法不能很好兼顾航空器的优先级限制,对于优先级别较高的航空器无法实现其尽快放行。

  2.3 极大代数航班离场规划

  此类方法的主线是将航班离场过程视为一个离散事件过程,采用极大代数方法建立相应模型,将离场系统的非线性转化为极大代数意义下的线性,并通过多步输出反馈对不同机型配比的离场航空器进行优化调度,得到具有多步状态延迟的闭环离散事件系统模型,并能通过采集的航班数据进行算例实现与仿真。

  在该类研究中[15-16],可以引进摄动分析和鲁棒性分析对系统的优化指标进行论证,并验证最后的仿真结果是否为最优解。此外,该方法可以模拟不同配比的进离场航班流,很好的分析进离场之间的相互作用。缺点是对于较为繁忙的大型枢纽机场,机型和航班数量较大,其闭环系统的矩阵束复杂性进一步增加,解算难度也相应增大。

  2.4 PQ调度与轮询调度

  PQ(Priority Queuing,优先级)调度有两种:静态优先级调度和动态优先级调度[17-19] 。

  PQ调度的原理是为每一个离场航班提供一个与之相应的优先级,然后分配到相应优先级的离场队列中,只有当优先级较高的队列空了之后才允许下一个优先级的队列调度,而在每一个队列内部遵循先到先服务原则。其优点是时间复杂度较低,稳定性较高,易于用计算机实现,但是其调度的公平性较差,不能兼顾不同航空公司的利益,适用于一些航空公司的基地机场航班调度。

  轮询调度以及由此发展而来的加权轮询调度均是在PQ调度的基础上演变而来,其原理(见图4)是对每个离场队列进行轮流循环调度,根据不同的加权值,一次放行相应架次的航空器离场。其优点是可以为每个航班提供最小权值率保证,但是由此产生的延迟较大,成本较高。

图4轮询调度原理图

  2.5 遗传算法

  遗传算法用于解决离场排序问题[10,20,21]具有一定的优势,它通过采用恰当的编码方法,交叉和变异算子,选取合适的适应度函数,交叉和变异概率,遵循最优个体保留策略,经过计算机仿真实现得到一个离场总队的优化排序结果,且能分别同随机排序情形进行对比。遗传算法的另一个优点是在考虑多种重量类型航空器的基础上,其生成的优化结果并不唯一,即在总离场耗时相同的情形下航班的离场顺序不同,提高了队列排序的优化空间和可行性。但是需要指出的是,对于多跑道多目标优化需要使用多条染色体进行分析,复杂程度较高,不易于实现。

  3 跑道调度问题

  跑道调度计划(runway operation planning,ROP)是指在给定的时间段内,针对多条跑道上飞机起飞、着陆和穿越等飞行活动,将机场跑道资源进行优化分配和调度,生成关于这些飞行活动的调度计划[22] 。无论是处于地面等待的航空器还是空中进近的航空器,机场跑道作为航空器转换飞行状态的结合点,其使用效率和分配状况制约着整个飞行系统的容量。我国很多枢纽机场已经扩建了两条甚至多条跑道,实现了多跑道运行,从而有效地增加了机场容量,只要跑道间的距离足够大,即可认为几条跑道可以独立运行而不会产生干扰,理论上讲新增一条跑道可以增加100%的运能,但在实际中往往并不能达到,这与航班的跑道分配有很密切的关系。如何有效地利用多跑道的运能就是跑道调度的一个重要课题。其中,跑道调度包括跑道调度模式与跑道穿越两个需要解决的核心环节。

  3.1 跑道调度模式

  多跑道机场管制单位给航班安排跑道的方法分为联合协作方式和分列独立方式[23] 。其中前者是所有起飞和降落的航班按照时间顺序排成一个队列,某条跑道空闲便使用该跑道;后者则是安排航班只能按照预先的计划使用跑道进行排序,然后顺序起降,进入相应的使用跑道队列后不得更改所使用的跑道。研究表明,采用单独起降的方式已经无法满足机场容量的要求,而采用联合起降的模式可以有效发挥跑道资源,发挥多跑道的潜在优势。以往的研究中均是通过建立协同调度多目标优化模型[24]或者是航班排序模型[25] ,采用遗传算法或者蚁群算法进行求解。相比较先到先服务有了一个较大的改进,且能满足实时性的要求。

  3.2 跑道穿越

  在实施多跑道运行的机场,影响管制安全的因素更为复杂,防止跑道入侵对保证飞行安全变得尤为重要。穿越跑道能大大减小航空器地面滑行时间和节约油耗。但与此同时,国内并无较为成熟的运行实施办法和相关规定,而且跑道穿越会加大管制员的工作负荷,尚需进一步研究。

  4 结论

  本文通过对离场航班调度算法的研究,对解决离场规划中两个核心问题的相关模型和算法分别进行了分析和研究,并对不同的跑道配置的机场提出了相应的离场规划方法,采用相应的方法能够给离场航班分配一个合理的分配队列以及跑道。但是,在管制员工作负荷以及多跑道多目标复杂性研究方面仍有许多潜力可挖,是下一步研究中需要重点解决的问题。

  参考文献

  [1] Gautam Gupta, Waqar Malik. A Mixed Integer Linear Program for Airport Departure Scheduling[C].9th AIAA Aviation Technology, Integration, and Operation Conference (ATIO).AIAA 2009-6933

  [2] Alexander Ioanis Simaiakis, Nikolas Pyrgiotis. An Analytical Queuing Model of Airport Departure Process for Taxi Out Time Prediction[C]. 10th AIAA Aviation Technology Integration, and Operation (ATIO) Conference. AIAA 2010-9148

  [3]SHUMSKY R A. Real-time forecasts of aircraft departure queues[J]. Air Traffic Control Quarterly Journal, 1997,5 (4):281-308

  [4] 徐肖豪姚源遗传算法在终端区飞机排序中的应用[J].交通运输工程学报. 2004, 4(3): 121~126.

(XU Xiaohao, YAO Yuan. Application of genetic algorithm to aircraft sequencing in terminal area [J].Journal of Traffic and Transportation Engineering, 2004, 4(3): 121 – 126.)

  [5] HU X, PAOLO E D. An efficient genetic algorithm with uniform crossover for air traffic control [J]. Computers and Operations Re-search, 2009, 36(1): 245 – 259.

  [6] GUO Y, CAO X, ZHANG J. Multi-objective evolutionary algorithm with constraint handling for aircraft landing scheduling[C] //Proceedings of 2008 IEEE Congress on Evolutionary Computation. Hong Kong: IEEE, 2008: 3657 – 3662.

  [7] ZHANG X, ZHANG X J, ZHANG J, et al. Optimization of sequencing for aircraft arrival based on approach routes[C] //Proceedings of the 10th International IEEE Conference on Intelligent Transportation Systems. Seattle: IEEE, 2007: 592 – 596.

  [8] ZHANG Z, WANG L. Sequencing to multi-runway approach landing flights based on ACS[C] /Proceedings of the 7th World Congress on Intelligent Control and Automation. Chongqing: IEEE, 2008: 3920 –3924.

  [9] TANG K, WANG Z, CAO X, et al. A multi-objective evolutionary approach to aircraft landing scheduling problems[C]// Proceedings of 2008 IEEE Congress on Evolutionary Computation. Hong Kong: IEEE, 2008: 3650 – 3656.

  [10]李珍,张军,张学军基于遗传算法的航班离港调度建模及仿真[J]. 交通与计算机, 2008.0626

  [11]刘龙泉飞行组织与实施[M]. 天津:中国民航学院, 1995.

  [12]陈文德,张迪生.极大代数方法在轧钢厂DEDS中的运用[J]. 自动化学报,1995211):99~102

  [13]张兆宁,王莉莉.基于流量和滑动窗的空中交通管理动态排序算法[J]. 交通运输工程与信息学, 2004.09 No.3 Vol.2

  [14]曹嵩,孙富春,胡来红,刘华平,张学军基于分布估计算法的离港航班排序优化[J]. 清华大学学报(自然科学版)2012Vol.52166-71

  [15]刘长有,赵拥军基于极大代数的航班离场过程分析[J].中国民航大学学报. 2009.02. Vol.27 No.1

  [16]华克强,蔡毓峰,高峥基于极大代数的离港航班优化调度[J]. 中国民航学院学报. 2005.06 Vol.23 No.3

  [17]刘飞基于静态优先级的调度[J]. 航空电子技术,2007,383):15--19

  [18]伍微一种静态优先级保序饱和分配算法[J]. 计算机科学,2009,3612):41-45.

  [19]宾雪莲一种有限优先级的静态优先级分配算法[J]. 软件学报,2004 156):815-822.

  [20]


精品文章

内容充实

不敢苟同

保留意见

文笔太差

最新评论

QQ|申请友链|旗下论坛|小黑屋|手机版|航空航天港 ( 豫ICP备12024513号 )

GMT+8, 2017-11-21 08:52 , Processed in 3.151832 second(s), 19 queries , Gzip On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

返回顶部