飞机排序（共5篇）
飞机排序 篇1
摘要：为缓解终端区空中交通压力, 研究了人工蜂群算法在终端区飞机降落排序中的应用。建立以航班总延误时间最小为目标函数的规划模型, 运用人工蜂群算法, 对着陆飞机排序问题进行了仿真计算;并与先到先服务算法、模拟退火算法、蚁群算法进行了对比研究。仿真结果表明:在双跑道模型下, 人工蜂群算法比先到先服务算法, 延误减少了48%。与模拟退火算法和蚁群算法相比, 人工蜂群算法求解的结果最优, 且用时最少。说明应用人工蜂群算法求解终端区飞机排序问题是可行的。
关键词：航空运输,航班进场排序,人工蜂群算法
不断增大的空中交通流量和受限的空域及跑道资源将会直接导致终端区内航班起飞和着陆的延误。终端区内航班延误不仅会造成一定的经济损失, 而且还会产生较大的安全隐患。因此, 在确保安全和经济的前提下, 如何减少航班进场延误, 已成为空中交通流量管理的一个重要的研究内容。
由于空中等待成本较高, 因此合理的飞机进场顺序成为减少航班进场延误的有效手段。实际运行中, 通常采用先到先服务 (first come first serve, FCFS) 的方法解决。该方法依据飞机预计到达时间 (estimated time of arrival, ETA) 的次序作为最后进场着陆的顺序, 不涉及任何优化, 因此会产生较大的延误。在理论研究中, 将进场问题划归为经典运筹学中的多目标规划问题[1]。在对该问题模型求解的算法方面, 许多专家学者引入了不同的求解方案。2001年, 徐肖豪、黄宝军等人将模糊综合评定方法引入飞机排序[2]。2004年, 徐肖豪等人运用遗传算法解决了双跑道的飞机进场问题[3]。2006年, 李志荣等人将蚁群算法引入飞机排序问题[4]。2008年, 徐肖豪等人运用混合人工鱼群算法求解飞机排序问题[5]。这些算法在求解问题的数量上升时, 仍存在算法效率下降, 收敛速度低, 容易早熟陷入局部最优解等问题。
人工蜂群算法 (artificial bee colony algorithm, ABC) 最早由Karaboga在求解函数数值优化问题时系统的提出[6]。它是一种模仿蜜蜂采蜜行为的群智能多点并行随机搜索优化算法。针对前述求解方法, ABC算法采用多点并行搜索, 因而在问题规模上升时, 仍能保证较好的收敛速度。随机更新搜索域, 在一次循环内最优搜索解附近进行邻域搜索, 依概率接受最优搜索解, 这些方法都保证了算法在求解问题过程中可以跳出局部最优解, 获得较好的全局寻优能力, 避免算法早熟[7]。再者, 该算法不需要了解问题的先验知识, 对初值要求不高, 只对问题优劣作比较, 具有一定的鲁棒性。本文研究了人工蜂群算法在终端区飞机排序中的应用, 并给出相关仿真算例。
1 航班排序模型
对于单跑道条件下, 设有n架航班降落在终端区内, 其集合为
E (i) 为第i架飞机的预计到达时间, S (i) 为第i架飞机的实际到达时间。不考虑飞机提前到达的情况, 则第i架飞机的延误时间为
若不考虑延误的时间成本, 则求解目标即为总延误时间最小。对于单跑道而言, 目标函数为
对于双跑道而言, 目标函数为
式 (4) 中, E1 (i) 和E2 (i) 分别为第i架飞机到达第1和第2条跑道的预计到达时间。
针对前述目标函数, 相应的约束条件主要定义为两类:
出于实际问题本身的约束, 不考虑航班提前到达的情况, 故应有预计到达时间小于实际到达时间, 即
出于航班本身安全性考虑, 飞机之间应满足最小安全间隔, 本文按尾流间隔处理。
2 人工蜂群算法
2.1 基本原理
人工蜂群算法是基于蜜蜂采蜜行为而形成的群智能算法。形成采蜜的群智能行为需要3个基本要素:食物源 (food) ;被雇佣蜜蜂 (employed bee, 其中一部分可能会成为引领蜂) 及未雇佣蜜蜂[unemployed bee, 包括跟随蜂 (on-look bee) 和侦查蜂 (scout bee) ]。
其中, 食物源代表各种可能的解。食物源的价值取决于多种因素, 如食物源距离蜂巢的远近, 食物源本身的丰富程度以及食物源开采的难易程度或危险程度等。在本文中, 考虑简单性, 用量化的收益率来衡量食物源优劣。结合到飞机排序问题中, 食物源就是同一组航班的不同排列次序。
雇佣蜂发现食物源, 并将食物源的具体信息 (包括食物源距蜂巢的距离, 食物的丰富程度等) 通过摇摆舞与其他蜜蜂分享。未雇佣蜜蜂通过雇佣蜂分享的信息, 跟随雇佣蜂采集食物源。当食物源开采殆尽或附近有更好的食物源时, 未雇佣蜜蜂转为侦查开采其他更好的食物源。
基于上述两类蜜蜂, 有3种基本行为模式:搜索食物源, 被食物源招募和放弃食物源。在算法的初始, 蜜蜂的行为是搜索食物源。当有蜜蜂找到收益率高的食物源时, 其余的蜜蜂有可能跟随这只蜜蜂, 被该食物源招募。当某个食物源开采殆尽时, 蜜蜂放弃该食物源。飞机排序问题和蜜蜂采蜜行为对应关系如表1所示。
2.2 角色描述
引领蜂:引领蜂是雇佣蜂的一种, 其数量和食物源相对应。引领蜂具有记忆功能, 会将自己搜索到食物源的相关信息存储起来, 并以一定概率分享给其他蜜蜂。由于分享的概率与食物源的收益率相关。在ABC算法中, 引领蜂对所有食物源进行循环搜索, 循环次数为C (C=1, 2, …, Maxcycle) 。随后, 引领蜂对相应的食物源进行一次邻域搜索, 搜索按公式 (6) 计算:
式 (6) 中, i≠k (k为i邻域的食物源) , k的取值从1到n (n为食物源个数) , j的取值为从1到d (d为食物源的维数, 即解向量的维数) , Φij为[-1, 1]之间的随机数, 用来控制邻域的范围。如果搜索到的食物源的收益率优于从前, 则用新的食物源位置代替原有的食物源位置, 否则按原有的食物源位置不变。所有的引领蜂完成搜索之后, 把食物源的信息传递给跟随蜂。结合到航班排序问题, 每一个食物源就是一种航班序列, 食物源的收益率对应的就是该种航班序列的延误水平。引领蜂的任务就是对不同延误水平的航班序列进行循环搜索, 以期找到一定延误水平下的优选航班序列, 为下一步跟随蜂进行进一步优化做准备。
跟随蜂:跟随蜂是在蜂巢附近等待引领蜂传递食物源信息的蜜蜂。它们会以一定的概率跟随引领蜂去开采相应的食物源。选用概率按公式 (7) 计算。
式 (7) 中, fi为第i个食物源的收益率, n为食物源个数。跟随蜂在选中某一食物源后, 同样进行邻域搜索, 搜索按公式 (6) 计算。邻域搜索完成后, 保留收益率较好的食物源。在航班排序问题中, 跟随蜂是以一定概率接受引领蜂搜索出的一定延误水平的航班序列, 然后在此基础上进行领域搜索, 最后保留延误最小的航班序列作为本次循环的结果。
侦查蜂:侦查蜂是由跟随蜂在产生放弃食物源的行为的情况后由引领蜂转化而成。当某个食物源开采殆尽时, 该食物源对应的引领蜂即转化为侦查蜂, 并同时放弃该处食物源。判断是否产生放弃食物源行为是由参数limit来控制, 它用以记录某处食物源的开采次数, 也即解的更新次数。事实上某个解若经历了limit次循环后没有得到提高, 可以认为在此处陷入了局部最后, 那么这个解应该被放弃, 该处的引领蜂转为侦查蜂, 开辟新的搜索空间。开辟新搜索空间按公式 (8) 计算。
式 (8) 中, sol是更新后的搜索空间, ub为参数上限, lb为参数下限, rand (1, D) 是元素在[0, 1]之间随机取值的D维解向量。对应到航班排序问题, 即可认为某个航班序列在有限次邻域搜索后, 延误水平没有得到改进, 那么放弃该序列。由于排序问题的规模有限, 故每轮循环中认为只有一只侦查蜂。
2.3 算法流程
基于以上原理和角色描述, 可得出ABC算法的流程。
2.4 收敛性能分析
收敛性是算法的重要性能指标, 本文选择了常用的收敛准则。前后迭代点的逼近是否满足一定的精度, 即为
式 (9) 中:ε是足够小的整数。连续运行20次后, 前后迭代点的差值均小于ε, 则认为符合收敛准则, 算法结束。
3 仿真算例分析
3.1 仿真算例
某机场现为双跑道设置, 某时刻有10架飞机准备降落[5]。这十架飞机的航班代码分别为HC0、LC1、HC2、HC3、SC4、HC5、LC6、HC7、HC8、SC9。其中第一个字母代表飞机的类型。根据国际民航组织的规定, 有三种类型的飞机, 分别是重型 (H) 、大型 (L) 和小型 (S) 。相邻的不同类型的飞机之间的最小尾流间隔标准S可以用一个3×3的时间矩阵 (单位为min) 来表示。
其中, 行代表后机的类型, 列代表前机的类型, 依次分别为小型, 中型和重型。每架飞机的延误如公式 (2) 所述。
相应的飞机到达跑道的预计时间ETA由一个3×10的矩阵表示, 第一行表示到达1号跑道的时间, 第二行表示到达2号跑道的时间, 第三行表示相对应飞机的类型。
3.2 仿真结果
预计到达时间为, 1号跑道E1= (11.0, 15.0, 6.0, 6.0, 9.0, 7.0, 15.0, 6.0, 6.0, 9.0) , 2号跑道E2= (10.0, 17.0, 7.0, 7.0, 12.0, 6.0, 17.0, 7.0, 7.0, 12.0) 。从表2中可看出, 总延误时间从FCFS算法得出的12.5 min减少到ABC算法得出的6.5 min, 延误减少了48%。仿真的具体结果如表2至表5所示, 其中表2, 表3为FCFS算法的双跑道仿真结果, 表4, 表5为ABC算法的双跑道仿真结果。
另, 援引文献[6]中的算法性能仿真比较表, 并加入ABC算法进行比较, 结果如表6所示。
3.3 结果分析
从仿真结果中可以得出以下结论:
(1) ABC算法与FCFS算法相比, 在减少延误的方面有较为明显的效果, 但是需要更多的计算时间。其原因在于, FCFS算法不采用任何优化措施, 不改变航班的降落次序, 因此用时较短, 也理所当然的会产生较大的延误。ABC算法是一种优化算法, 在寻优过程中不可避免的需要耗费一些时间, 因此, 算法计算时间多于FCFS, 但延误小于FCFS。
(2) ABC算法于其他智能算法相比, 从计算延误结果和用时两方面均能取得较好结果。
(3) ABC算法虽然在计算用时上有所耗费, 但是依然在可接受的秒这一数量级, 即使算法效率有所下降, 当相比较减少的延误量而言, 这点耗费占的比重并不大。飞机在空中等待, 一方面安全性得不到保障, 另一方面也会造成一定量的经济损失。因此, 从这个角度来看, 以算法的计算用时的损耗来减少飞机的延误, 这是可取的, 说明ABC算法在减少飞机排序延误上是可行的。
4 结论
鉴于以往算法在求解飞机降落排序问题时, 存在算法效率下降, 收敛速度低, 容易早熟陷入局部最优解等问题。本文用人工蜂群算法来求解双跑道模式下飞机降落排序问题, 通过仿真实验对4种算法进行了对比分析。结果显示, 在问题规模不大的前提条件下, 用人工蜂群算法来求解双跑道下飞机排序问题, 可以得到较好的寻优结果, 且算法不易陷入局部最优解。
参考文献
[1] Beasley J E, Krishnamoorthy M, Sharaiha Y M, et al.Scheduling aircraft landings—the static case.Transportation Science, 2000;34 (2) :180—197
[2] 徐肖豪, 黄宝军.终端区飞机排序的模糊综合评定方法研究.航空学报, 2001;22 (3) :259—261
[3] 徐肖豪, 姚源.遗传算法在终端区排序中的应用.交通运输工程学报, 2004;4 (3) :121—126
[4] 李志荣, 张兆宁.基于蚁群算法的航班着陆排序.交通运输工程与信息学报, 2006;4 (2) :66—19
[5] 王飞, 徐肖豪, 张静.终端区飞机排序的混合人工鱼群算法.交通运输工程学报, 2008;8 (3) :68—72
[6] Basturk B, Karaboga D.A powerful and efficient algorithm for numeric function optimization:artificial bee colony (ABC) algorithm.Journal of Global Optimization, 2007;39 (2) :459—471
[7] 胡中华, 赵敏.基于人工蜂群算法的TSP仿真.北京理工大学学报, 2009;29 (11) :978—982
飞机排序 篇2
A算法在终端区飞机排序中的应用
讨论了终端区飞机排序问题,根据飞机尾流间隔要求,利用A算法建立了终端区航班排序的数学模型.利用A算法,对一个算例进行验证计算,找到了更合理的航班着陆队列,减小了航班的总延误成本.结果表明,航班总延误成本的优化结果是令人满意的`,A算法在终端区飞机排序问题中的应用是可行的.
作 者：李伟 王仲生 LI Wei WANG Zhong-sheng 作者单位：西北工业大学,航空学院,西安,710072 刊 名：科学技术与工程 ISTIC英文刊名：SCIENCE TECHNOLOGY AND ENGINEERING 年，卷(期)： 7(11) 分类号：V355.2 关键词：空中交通管制 终端区 飞机排序 A算法飞机排序 篇3
对流量相对较大的机场来说,对终端区飞机进行合理快速的排序是非常重要的,它可以提高机场跑道的利用率,缩短飞机序列的留空中时间,减少冲突,从而可以提高飞机序列的安全性。因此,使用快速有效的排序算法对机场终端区飞机流进行排序是非常重要和必要的。
终端区排序是空中交通流量管理的三大内容之一[1]。当前用于终端区飞机序列优化排序的算法主要有:先到先服务算法(First Come First Serve, FCFS)[2],时间提前量算法[3],约束位置交换算法[4],模糊识别算法[5],遗传算法[6,7],滑动时间窗算法[8]等,其中滑动时间窗算法以其快速有效的特点成为一种非常有效的飞机终端区排序算法[9]。文献[10]通过计算说明了滑动时间窗算法的有效性,但并未讨论参数选择对优化结果的影响,而且排序飞机的数量较少,对滑动时间窗算法有效性的证明不够充分。文献[11]对滑动时间窗算法虽然进行了较为深入的研究,但仅通过单个飞机序列讨论滑动时间窗算法,其结果是不具一般意义的。由于滑动时间窗算法中的参数较多,而且每个参数对排序结果的影响都不尽相同,合理的参数设置与组合,可以非常明显地提高算法的运算速度和优化性能;相反,不合理的参数设置与组合,会严重影响算法的性能,体现不出滑动时间窗算法的优越性。因此,对滑动时间窗算法的参数进行深入研究,找出其合理的参数设备和最佳组合,从而更好地使用滑动时间窗算法,是非常有必要,也是非常有意义的。
1问题描述
假设,有M架飞机进入机场终端区,终端区管制员需要在时间段T内安排其降落。通过每架飞机,从而可以计算出飞机序列的预计降落时间(Estimated Time of Arrival, ETA)。根据飞机序列的ETA和不同飞机对之间需要保持的尾流间隔,通过优化排序就可以找出飞机序列的安排降落时间(Scheduled Time of Arrival, STA),从而也就知道了每架飞机的降落时间和降落次序[12]。
设终端区需要安排降落的飞机组成的集合为P={Pi | i=1, 2, …, M}。
其中i为计算出飞机序列的ETA后飞机Pi在序列中所处的位置,即飞机Pi指计算出ETA后位置i上的飞机,定义ETA序列下飞机的位置为初始位置。
M架飞机的预计降落时间集合
ETA={ETAi | i=1, 2, …, M},
安排降落时间集合
STA={STAi| i=1, 2, …, M}。
由于飞机在飞行时会产生尾流,前机的尾流会影响后机的飞机安全。因此,飞机在飞行时需要与前机保持一定的距离。不同的飞机对之间的尾流间隔是不同的,国际民用航空组织(International Civil Aviation Organization, ICAO)对无风条件下不同飞机的尾流最小间隔标准做出了规定。通过此间隔的和飞机的飞行速度可以计算出不同类型飞机对之间的时间间隔,如表1所示[13]。
TRij指飞机Pi和Pj之间的最小安全间隔时间。
为了简化模型,飞机之间的最小安全间隔只考虑尾流间隔。
为了减小终端区管制员的负担,在对飞机序列进行排序和那优的过程中,要求每架飞机的安排降落位置相对于其初始位置不能有太大的位移,也就是说优化后的飞机位置必须控制在初始位置的一定范围之内,这就是飞机终端区优化排序中位置交换范围约束条件。
对待降飞机序列进行优化排序就是找到一个飞机序列,在安排降落时,使得整个序列的等待时间最小。因此目标函数可以用式(1)描述。
约束条件为式(2)、式(3)、式(4)、式(5)。
a. 预计降落时间是根据飞机进入终端区的时间、性能参数以及初始状态计算出的降落时间,是可以安排的飞机降落的最早时间,因此安排降落时间不可能早于预计降落时间
b. 前后相邻飞机之间的间隔需要满足最小尾流时间间隔约束
STAi+1-STAi≥TRi,i+1; i=1,…,M-1 (3)
c. 位置交换范围约束,每架飞机优化后的位置必须控制在初始位置的一定范围内
式(4)中:PEi,PSi分别为飞机i的初始位置与优化后在序列中的位置;Rext为位置交换的最大范围。
d 窗体大小Wsize,交换范围Rext和移动步长Lstep还要满足约束条件(5)
2算法实现
2.1算法思想
要得到终端区飞机降落时的最优序列,最直观的方法就是对飞机序列进行循环排序(Circular Permutation, CP)。假如终端区内需要降落的飞机有M架,要得到最优排序,就需要进行M!次排序,随着飞机数量的增多,采用此种算法的计算量呈阶乘次增加。图1是采用CP算法时,需要排序的飞机数与计算时间之间的关系(计算所采用的计算机主要配置为:Core 2 Duo CPU 3.16 Hz,2 GB RAM)。因此,采用一种实时性高,而且排序效果好的算法是十分必要的。滑动时间窗算法不仅可以对飞机序列进行很好的优化,同时又较好地解决了计算量急剧增长的问题。该算法的思想是:由于最佳排序可能会使飞机序列的安排降落顺序相对于计划降落顺序发生很大地改变,从而增加管制员的负担,而且与FCFS原则是相违背的,实现起来有很大的难度。因此,通过约束飞机位置交换的范围是解决这个问题一个很好的途径,约束位置交换范围指的是优化排序后飞机的位置只能处于初始位置前后一定的范围内。因此,从交换范围的限制出发,在确定新队列中某个飞机的STA时,并不需要寻找所有可能的飞机序列,只需找到满足位置交换范围约束的序列,然后再计算该序列的等待时间,从而找到优化排序结果[14]。
2.2算法设计
滑动时间窗算法首先需要在排序队列中建立一个时间窗,所谓时间窗是指包含一定数量(w)的飞机序列的窗口。在满足交换范围约束(r)的前提下,对通过对窗口的飞机进行CP排序,完成后将窗口向后移动一个步长(s)。移出窗口的飞机作为最终的飞机序列,移入的飞机和原窗口的飞机组成一个新的窗口,然后再对新窗口的飞机进行CP排序,以此类推,完成的所有飞机的排序。具体实现过程如下。
第一步:取ETA序列的前w架飞机构成初始窗体,在满足交换范围约束(r)的条件下,使用CP排序算法对窗体内的飞机序列进行优化。优化结束后,窗内的前s架飞机即为最终队列的前s飞机。
第二步,窗体沿初始队列向后移动步长s,此时窗体右边界到达初始队列的第w+s架飞机,第一步窗体中剩余的w-s架飞机加上新加入窗内的s架飞机,又构成包含w架飞机的新窗体,过程如图2所示。
第三步,使用CP算法对新窗体内的飞机排序,注意以下条件必须满足,即新窗体内第1架飞机与前面已经分离出窗体的最后一架飞机之间必须满足最小安全间隔。完成排序后,又有s架飞机分离出新窗体。
第四步,重复第二步,移动窗体,组成新窗体。
第五步,重复第三步,分离出s架飞机,加入最终队列。
以此类推,完成整个飞机序列的排序,流程如图3所示。
2.3算法复杂度分析
算法复杂度分析主要进行时间复杂度分析。
假设需要排序终端区飞机数量为M,窗内飞机数目和移动步长分别为w、s。当使用CP算法进行排序优化时,所要计算的次为:M!;运用滑动时间窗算法进行飞机终端区排序时,所要计算的次为:[(M-w)/s+1]w!,比CP算法的运算量要小得多。
2.4仿真及分析
按照排序队论的理论,机场终端区的飞机流属于典型的泊松流[15,16,17]。假设飞机降落时为单跑道情况,终端区需要排序的飞机数为30架,每降落一架飞机需要大约60 s的时间生成降落飞机流;同时,按均匀分布随机生成来流飞机的类型,飞机类型主要选取重型(H)和大型(L)两种。
使用MATLAB编程实现滑动时间窗算法[18]。通过对50批次、每批次30架飞机进行排序优化,然后再进行统计。
从前面的计算知道,当采用CP算法时,参加排序的飞机数量超过7时,计算就很难满足实时性的要求。因此,在考虑实时性的前提下,本文在仿真和计算过程中主要研究窗体大小分别为4,5,6和7时,步长与约束范围在不同组合情况下的优化性能。
首先,通过固定窗体大小Wsize,然后取步长Lstep和约束范围Rext所有可行的组合,最后计算出总的延误时间并进行对比。图4至图7分别为窗体大小从4至7情况下,步长和约束范围在不同组合情况下的计算结果。
从图4至图7分析可以得出:
(1)当Rext=1时,步长的调整对排序结果几乎没有影响,这也说明了只对飞机进行极有限的位置调整是不会减少总的延误时间的。
(2)在步长确定的情况下,当交换范围增大时,总的延误时间会明显减小。然而过小的步长会导致过多的窗体个数,从而需要进行全排序序列的个数就会增多,这样会使计算量增大。因此,在不增加总的延误时间的情况下,应尽可能取较大的步长。
(3)窗体大小为7,步长为3,交换范围约束为4时,总的延误时间可以达到最小值。因此,该组合为实时性要求下的最优组合。
从上面的计算和分析知道,当窗体大小为7,步长为3,交换范围约束为4时,参数组合为实时性约束下最优组合。在该种组全下,通过统计计算,每架飞机的延误时间如图9所示。图8是在FCFS算法下每架飞机的延误时间。
通过图8和图9的对比并计算可以得出:
从飞行员的角度来看,当采用FCFS算法总延误时间是21 424 s,平均每架飞机延误约741.1 s;采用滑动时间窗算法时(Wsize=7, Lstep=3, Rext=4)总延误为20 361 s,平均每架飞机延误687.7 s,与FCFS算法相比,平均每架飞机延误时间减少了53.4 s。
从终端区管制员的角度来看,在经过滑动时间窗算法排序之后,最后降落的大约10架飞机的延误时间得到了很大的减小,经过统计,采用FCFS算法时,后10架飞机的延误时间为10 984 s,平均每架飞机延误1 098.4 s;采用滑动时间窗算法时(Wsize=7, Lstep=3, Rext=4)后10架飞机的总延误时间为10 002 s,平均每架飞机延误1 000.2 s,与FCFS算法相比,平均每架飞机延误时间减少98.2 s。
3结论
通过算法的设计和仿真计算表明,滑动时间窗算法在飞机终端区排序中是一种非常有效的方法。但是,滑动时间窗算法并不是在所有的情况下都是有效的,在该算法中,窗体大小、步长大小、位置交换约束三个参数的取值对算法优化结果的影响是非常明显的。在当前硬件条件和实时性约束条件下,当窗体大小取7,步长取3,位置交换约束取4时,滑动时间窗算法可以达到最优的计算结果。在此种组合下,对飞机序列进行排序优化,所得的结果与FCFS算法相比,可以明显的减少飞机序列的空中等待时间,尤其是队列的后面的飞机,对其延误时间的缩短是非常明显的。
飞机排序 篇4
空中交通流量管理(简称空管,Air traffic control,ATC)是指通过利用高效可靠的管理方式,借助科学技术手段,充分合理利用空中航线资源和地面机场资源,同时保证空中的交通安全有序。
进入21世纪以来,我国的航空航天事业不管是从研发的角度,还是从航空运输的角度来看,都取得了令人瞩目的快速发展,随着空中交通流量的增加,ATC渐渐引起了空管部门的思考。最为常见的是在客流量比较大的机场,由于机场资源的限制或者资源利用不完全引起的飞机延误以及机场拥堵问题日益突出,从经济上来看,最终的结果就是给航空公司带来额外的经济开销和损失,同时安全隐患也增多了。因此在飞机降落的终端区,进行优化控制飞机降落的顺序,从而使延误达到最小化,已然是目前空管的非常重要的一个方面。
国内和国外的许多研究人员分别从不同的角度,对飞机降落的顺序安排优化问题进行了深入的研究。Xiao[1]等提出了一种新的以二进制表示为基础的遗传算法组合问题,不同于现有的遗传算法求解飞机排序问题,新的遗传算法引入了一种新型的波纹扩散模型,将以原始着陆顺序为基础的飞机排序解决方案转换成基于价值为导向的解决方案;文献[2,3]主要从互换理论方面给出一种相邻位置相互交换的动态排序算法;文献[4]增加了操作员带来的影响,主要采用了模糊综合评价法来确定飞机降落的相对顺序;文献[5]主要利用置换算法实现飞机降落排序;文献[6]采用了排序窗来解决计算量太大的问题。但是,上述这些寻优方法过程大都比较缓慢,加之计算偏复杂,导致这些方法效率不高。许军海[7]等提出了用遗传算法解决多跑道飞机调度的方法,从父种群中选出两条染色体,对其进行交叉、变异操作后产生两条子染色体,不断重复上述过程,直至P条子染色体被创建,用子种群替代父种群。曹怀春[8]等提出了一种基于层次分析方法的模糊综合评价法,选取了三种对飞机进近影响较大的因素,采用了层次分析方法确定评价因素的权重,对飞机落地进行排序,该算法对影响因素的选取主观性太强;赵嶷飞[9]等人提出了一种应用人工蜂群算法求解终端区飞机排序问题,该算法在寻优过程中不可避免的增加了时间耗费。
本文是基于遗传算法来对飞机降落排序进行研究的,假设将飞机个体作为基因,而将飞机基因组成的序列作为染色体。利用一种特别算子,改进了传统遗传算法的染色体编码方式。相对于文献[10]而言,改进后的遗传算法,引入交叉掩码,使交叉操作和变异操作后的染色体仍然具有较强父代的特性,使得生物的优良特性得以保存,进一步提高了适应度值,进而加快了收敛速度,可以快速找出延误代价最小的最优航班排序。
1 机场终端区
1.1 机场终端区环境
机场终端区是一个极其复杂的环境,飞机的起飞和降落都必须经过此区域的调度分配。其中,终端区进近飞行过程如图1所示。
在终端区,实施流量管理[11]是为了在保证所有飞行器之间的安全间隔的条件下,尽可能以高效合理的方法安排飞机之间的着陆和起飞顺序,使整个终端区安全有序的运行。
这自然就引出一个可以研究的热点:在终端区如何管制,也即怎样安排飞机的降落顺序,才可以让航班延误代价最小化。
终端区战术管制是指在终端区内空域同时存在多个航班时,通过调节下降起始高度点之前飞机的飞行速度,或采用快速、正常和慢速的不同下降方式,合理安排航班的着陆时间和顺序,既能使航班之间的间隔满足安全飞行间隔标准,避免冲突,又能使机场在较高的效率下运作。
本文给出的方法是针对终端区航班着陆的实时流量战术排序问题。
1.2 延误航班总延误代价模型
本文以多架延误航班等待降落单跑道来探讨。
设有n架延误飞机进入终端区等待降落,延误航班集合为F={F1,F2,…,Fn},E(i)为第i架飞机的预计到达时间;S(i)为第i架飞机的实际到达时间;飞机分为3类:重型(H)、中型(L)和轻型(S);第i架飞机与第i-1架飞机之间的最小时间间隔(尾流间隔)为C(i-1,i)。
根据国际民航组织的规定,各型号飞机之间的尾流时间间隔(单位:秒)如表1所示。
模型约束条件:
两个约束条件分别表示延误飞机未能提前降落,同时也必须满足尾流间隔要求。
显然,第i架飞机的实际降落时间为:
第i架飞机的延误为:
通常来说,飞机的延误代价与机型和延误时长有关,并且延误代价总是大于零,因此本文模型设置延误代价系数Kcost(i)与延误时长d(i)和机型有关,如公式(3)所示。
延误代价系数参数解释:其中α,β,γ均为大于零的正整数,α,β与飞机的机型有关,α为受不同机型控制的线性参量,β为受不同机型控制的指数函数底数,γ为延误时间基数;延误代价系数Kcost(i)含义:延误d(i)达到γ秒以后,延误代价系数Kcost(i)随不同机型控制的α和延误时间d(i)呈指数快速增加,若d(i)=0延误代价为0。
本模型将飞机队列总延误代价设为每架飞机的延误代价系数与延误时长的乘积之和,n架航班总延误代价为:
问题的求解目标是使n架延误飞机队列总延误代价最小。
2 遗传算法
2.1 概述
遗传算法(Genetic Algorithm,简称GA)是由美国Michigan大学的Holland J.教授于1975年首先提出的,它是模拟达尔文生物进化过程的计算模型,是一种具有自组织、自适应、自学习能力的智能优化算法。GA一般是根据大自然的进化规则来进行搜索计算和问题求解的。对于许多用复杂问题,用传统的数学是很难解决甚至是完全解决不了的,尤其是很多最优化的问题,GA对解决这些复杂问题来说,是一种很好的策略。遗传算法包括三个基本操作:选择、交叉和变异[12]。
2.2 遗传算法的工作流程
遗传算法的工作流程如图2所示。它尤其适用于处理传统方法难以解决的复杂和非线性问题,人们把它应用于学习、优化、自适应等问题中[13]。
第一步:首先随机产生一定数目的初始群体。
第二步:计算出每个个体的适应度值,并判断是否满足进化设置的终止条件;若满足,输出结果,该结果即为最优解,计算结束。若不满足,转向第三步。
第三步:通过选择、交叉、变异操作,生成新的个体。在新一代中,选择适应度大的个体,适应度小的个体有可能被淘汰。返回到第二步。
2.3 自适应遗传算法
本文采用自适应遗传算法来计算个体的交叉和变异概率,交叉概率Pc和变异概率Pm能随适应度值f自动进行改变,如果一个种群中每一个个体的适应度值趋近一致,也就是局部最优的时候,就增大Pc和Pm,反之亦然。自适应的Pc和Pm能提供相对某个解最优的Pc和Pm,自适应遗传算法中的Pc和Pm按如下公式计算[14]:
其中,适应度,Dcostsum表示飞机队列延误总代价;f'表示即将进行交叉运算的两条染色体中适应度值较大的个体的适应度;fmax表示适应度最大值;favg表示适应度平均值。一般Pc1,Pc2分别取0.9和0.5,Pm1,Pm2分别取0.1和0.002。
对于适应度值比较小的个体,若是其适应度小于平均适应度,则采取比较大的交叉和变异概率,将其在下一代中尽量淘汰,反之就保护。
2.4 染色体编码
传统遗传算法染色体编码方式运用于延误飞机进场算法分析:
(1)交叉操作
对于交叉操作而言,假设一共有6个航班要进行排序,编码的方式是通过在(0,1)内产生6个不同的随机数,代表时间单位,然后通过数值的大小来进行排序编码。例如通过随机方式产生的一条染色体为:
这样,它代表的排序就是A4,A6,A2,A5,A3,A1,对应的编码为4,6,2,5,3,1。也就是第一个飞机排第六,第二个飞机排第三,以此类推。
这种传统的遗传算法染色体的编码方式可以保证交叉操作和变异操作的进行,但可能会出现收敛速度过慢的问题。因为它是将一组随机数根据数值的大小映射到序列上,在进行交叉操作后,其父代和子代的相关性就很会逐渐变小,例如染色体:
与此相对应的编码为5,4,1,6,2,3和6,4,3,5,2,1。
随机设交叉点,交叉点个数设为2,
则其子代的染色体为:
对应的编码为6,5,3,4,2,1和6,3,2,5,1,4。
通过观察可知,当进行常规染色体交叉操作完成译码后,父代和子代的相关性基本没有。G3相对于父代G1来说,无航班延续的父代的特征。而G4相对于父代G2而言,只有航班6、5延续了父代的特征。这样的话,就达不到生物进化的效果,从而也失去了生物进化的作用和意义。
(2)变异操作
传统的变异算子,由上述可知,将6个航班安排在6个位置,所以对于每一个位置来说,就有6种可能性,也就是有6个基因值(1,2,3,4,5,6)。例如在第4个位置上发生变异:
父代染色体为:3,6,4,2,5,1
子代染色体为:3,6,4,1,5,1
可以看出航班1进行了两次排序,而航班2就自动消失,没有了排序。所以,传统遗传算法的这种关于染色体的编码方式,在实际操作中往往不可行。所以,为了解决这个问题,本文对染色体编码方式进行了改进,通过引入交叉掩码,提出了一种改进的遗传算法。
3 改进的遗传算法运用于飞机进场算法分析
本文通过引入交叉掩码的方式,改进了传统遗传算法的染色体编码方式。这种改进的方法,使交叉操作和变异操作后的染色体仍然具有较强父代的特性,从而使得生物的优良特性得以保存[15]。
3.1 引入交叉掩码的染色体编码
(1)交叉掩码的计算:交叉掩码的引入和父代有最高适应度的个体有关。对比前两代适应度值最高的个体对应的染色体,两条染色体基因座相同的记为1,基因座不相同则记为0,这样就可以将优秀的基因遗传下去。
交叉掩码的计算示例如下:
已知i-2,i-1代适应度值最高的染色体Gi-2,Gi-1,求i代的掩码,其中i≥3。
计算过程:
(2)本文在染色体编码的交叉操作中,引入交叉掩码,交叉掩码是对遗传算法的改进所加入的一个算子。当交叉掩码中的基因为1时,父代的基因会在子代中保留;而当交叉掩码的基因为0时,剩余的基因则按另一条父代染色体中相应基因的顺序来进行排序,如下所示:
交叉掩码为:101110
父代染色体为:2,1,5,6,3,4
6,5,2,3,4,1
子代染色体为:2,4,5,6,3,1
6,1,2,3,4,5
如上所示,对于第一条子代染色体而言,2,5,6,3相对于父代而言,其位置保持不变。而其余的基因1,4则按照父代的另一条染色体中所对应的排列顺序4,1,排列在空着的基因位置上,从而子代染色体为2,4,5,6,3,1。同理,对于第二个子代染色体而言,6,2,3,4相对于父代的基因位置不变,而5,1则按照另一个父代的相对应基因的排列1,5排列在子代当中。
传统的变异操作可能使子代发生变异不可收敛的情况,比如上文中传统的变异操作,航班1进行了两次排序,而航班2由于变异的作用没有进行排序。为了解决这个问题,本文对于基因的变异进行了改进:对同一染色体中的基因进行位置随机互换,来取代传统的基因的随机变异。例如航班序列的染色体为:
3,2,6,5,4,1
被交换的基因位置随机生成,通过适应度等限制条件,随机选中变异的基因位置为5和6,则发生变异后的染色体为:
3,2,6,5,1,4
这样就保证了子代和父代之间的稳定性,因为子代中包含了从1到6所有航班的排列次序。这样一来,就可以更好的延续生物的进化,从而使得进化作用发挥更好的效果。
3.2 改进后算法流程
第一步:随机产生10个个体作为初始种群。
第二步:模型中适应度函数为延误飞机队列总的飞机延误代价倒数,计算个体序列适应度。
第三步:选择操作采用经典的赌盘选择法对初始种群进行选择。
第四步:按照公式(5)计算交叉概率,引入交叉掩码,对两条染色体进行交叉操作。例如:
交叉掩码为:1 0 1 1 1 0
父代染色体为:2,1,5,6,3,4
6,5,2,3,4,1
子代染色体为:2,4,5,6,3,1
6,1,2,3,4,5
第五步:按照公式(6)计算变异概率,并对染色体进行变异操作。变异操作的过程就是随机选取染色体中的基因来互换位置。
如染色体为:
3,2,6,5,[4],[1]
则变异后的染色体为:
3,2,6,5,[1],[4]
第六步:返回第二步,继续循环寻优。
4 仿真结果及分析
本文应用MATLAB软件编写仿真程序,仿真条件:单跑道,飞机队列到达等待安排降落,先到先服务算法按飞机达到先后顺序队列安排降落,改进的遗传算法按照总延误代价最小,即效果最优安排飞机降落顺序。
遗传算法采用的仿真参数如下:β设为2,H型飞机,α=15,L型飞机α=10,S型飞机α=15,γ设为300,如此设置的意义是:延误时间达到5分钟以上延误代价呈指数增加,不同机型延误代价不一样,H型机延误代价3倍于S型飞机,L型飞机延误代价2倍于S型飞机;初始种群大小为10,仿真代数为100,第一和第二代的掩码全设置为1,Pc1,Pc2分别取0.9和0.5,Pm1,Pm2分别取0.1和0.002。
根据某国内大型机场的飞机预计着落时间和延误预计着落时间,对10架航班的航班号为:中型机L5、L6,重型机H2、H1,轻型机S2、S6、S3、S5、S7、S9的飞机进行入场排序。分别采用先到先服务算法和改进的遗传算法得到的排序结果表2和表3所示。
表中各项说明:将落序号表示飞机依次着陆顺序,航班编号代表不同航班,E表示航班预计着落时间,S表示航班实际着落时间,Dt表示航班延误时间,表中时间单位:秒;Dc表示延误代价;Dt对应模型的延误时间d(i),即Dt=d(i),Dc对应模型的表示每个航班的延误代价,即Dc=d(i)*Kcost(i)。
由于调整降落航班顺序以后,各航班必须仍然满足尾流间隔,所以表3的航班预计着落时间E与表2的航班预计着落时间E相比是有所调整的。
表2为FCFS排序结果,表3为改进后遗传算法的排序结果。通过比较表2和表3可得出,改进的遗传算法能有效减小航班总延误代价,总延误代价减少了7792.7933个单位,相比减少了约61.52%,效果显著。
图3为改进的遗传算法总延误代价曲线。计算总延误代价的统计平均,得到改进的遗传算法的总延误代价平均值为6496,最高延误代价为14600,最低延误代价为4874.5。可见,在前5代,收敛速度很快,10代到30代之间收敛速度变缓,在30到60代之间收敛数度进一步变缓,60代以后趋于稳定,总延误代价稳定在4874.5。整体来看,本文的优化算法具有整体收敛性,鲁棒性和快速的局部收敛性,这是由于改进后的遗传算法在进行交叉和变异操作时,父代优良的特性得以保留,而且种群的进化具有收敛性并趋于稳定。改进的遗传算法相对于文献[10]中的遗传算法而言,优化效果明显。而且,通过算法的仿真结果可知,本文所改进遗传算法的仿真结果要优于文献中的结果。
5 结束语
飞机排序 篇5
终端区排序是空中交通流量管理中的三部分内容之一[1]。平均到达率描述了终端区需要降落飞机的密集程度,可以在很大程度上表明终端区空中交通的繁忙程度。根据机场的容量,配备合理的平均达到率对减小飞机延误,提高优化结果的性能,是十分重要的[2]。对流量相对较大的机场来说,对终端区飞机进行合理快速的排序是非常重要的,它可以提高机场跑道的利用率,减少飞机序列的留空中时间,减少冲突,从而提高了飞机序列的安全性。由于终端区降落飞机的类型不同,而不同类型飞机之间的安全间隔会有较大差别,因此,飞机流结构优化排序时需要考虑的一个重要因素。所以,有必要对平均到达率和飞机流结构对优化排序结果的影响进行研究。
1 问题描述
假设,机场终端区有M架飞机,需要在时间段T内安排其降落。通过每架飞机进入终端区的时间、性能参数以及初始状态,可以计算出飞机序列的预计降落时间(Estimated Time Arrival, ETA)。根据飞机序列的ETA和当前飞机序列的排序情况,通过优化计算给出飞机序列的安排降落时间(Scheduled Time Arrival, STA),从而也就得到了飞机的降落次序[3]。
终端区飞机组成的集合P={Pi|i=1,2,…,M}。
其中i为通过ETA计算后飞机的位置,即飞机Pi指ETA计算后位置i上的飞机,定义ETA下飞机的位置为初始位置。
M架飞机的预计降落时间集合ETA={ETAi|i=1,2,…,M},安排降落时间集合STA={STAi|i=1,2,…,M}。
TRij指飞机Pi和Pj之间的最小安全间隔。
为了简化模型,飞机之间的最小安全间隔只考虑尾流间隔。由于终端区需要安排降落的飞机类型是不同的,飞机前后顺序不同,从而所需要的尾流间隔也不同,国际民用航空组织(International Civil Aviation Organization, ICAO)对无风条件下不同飞机的尾流最小间隔标准做出了规定,由此可以得到最小安全间隔时间,如表1所示[4]。
为了减小终端区管制员的负担,在对飞机序列进行排序的过程中,每架飞机的安排降落位置相对于其初始位置不能有太大的调整,也就是说优化后的飞机位置必须控制在初始位置的一定范围之内。
对飞机序列进行排序就是找到一个飞机序列,在安排降落时,使得总的等待时间最小。因此目标函数可以用式(1)描述。
约束条件为式(2)、式(3)、式(4)。
a. 安排降落时间不可能早于预计降落时间,因此
b. 相邻飞机之间的距离需要满足尾流约束
式(3)中:PEi,PSi分别为飞机i的初始位置与最终优化位置。
c 窗体大小Wsize,交换范围Rext和移动步长Lstep还要满足约束条件
2 仿真实现
当前对终端区飞机排序的方法主要有:先到先服务算法(First Come First Serve, FCFS)[5],时间提前量算法[6],约束位置交换算法[7],模糊识别算法[8],遗传算法[9,10],滑动时间窗算法[11]等。以上各种算法仅能找到次优结果。需要准确研究各个参数在不同情况下对优化效果的影响,先找到飞机队列的最优排序结果。而要找到飞机序列的最优化排序就需要进行循环排序(Circular Permutation, CP)。假如进入终端区的飞机有M架,要得到最优排序,就需要进行M!次排序。随着飞机数量的增多,采用此种算法的计算量非常大。图1是采用CP算法时,需要排序的飞机数与计算时间的关系(计算所采用的计算机主要配置为:Core 2 Duo CPU 3.16Hz,2GB RAM)。为了使研究结果更具实际和统计意义,在可以找到飞机最优序列的前下,应尽可能增加排序飞机的数量,但过多的飞机数量又会导致计算量急剧增加。在考虑以上因素的情况下,本文取终端区的飞机数量为10,通过仿真来研究平均到达率,飞机流结构对优化排序结果的影响。
仿真中使用的飞机平均到达率分别为每60、90、120 s一架飞机。对每一种到达率,分别研究以下三种飞机流结构:第一种飞机流由30%的重型飞机、40%的大型飞机、30%的小型飞机构成;第二种飞机流由30%的重型飞机、50%的大型飞机、20%的小型飞机构成;第三种飞机流由20%的重型飞机(H)、50%的大型飞机(L)、30%的小型飞机(S)构成。如表2所示。
对每一个由飞机流形成的组合,通过随机赋予飞机到达时间和类型的方法,产生100组数据,即在产生的每一组数据中,飞机的预计到达时间和类型都是随机的。
按照排序队论的理论,机场终端区的飞机流属于典型的泊松流[12,14]。从而连续到达飞机的间隔时间服从指数分布,间隔时间的平均值为飞机平均到达率的倒数。根据以上关系可以产生终端区到达飞机流的ETA,然后通过循环排序算法可以得到最优序列的STA。
仿真过程使用MATLAB编程实现[15]。
3 仿真结果及分析
通过仿真,得到表3中的数据。表3中,延误减小程序r指最优飞机序列相对于FCFS序列的延误减小程度,由式(5)给出。
依据表3对总体、重型飞机、大型飞机、小型飞机延误减小程度绘图,分别可以得到图2、图3、图4和图5。
由图分析可以得到以下结论。
(1)优化排序对飞机延误的影响
相对于FCFS排序,最优排序可以大幅缩减飞机的延误时间。当终端区有十架待降飞机时,平均延误可以减小30%左右。
(2)平均到达率对延误的影响
随着平均到达率的减小,总的延误是不断减小的,但平均到达率的减小对不同机型的延误减小程度不尽相同。平均到达率对重型飞机和大型飞机延误的影响非常明显,随着平均到达率的减小,重型飞机和大型飞机延误减小程度显著,尤其是重型飞机,在平均到达率从1架/60 s变化至1架/120 s时,平均延误缩减程度从1%增加至40%。无论是何种飞机流结构,通过优化排序后小型飞机的延误程度都可以得到明显地缩减,缩减程度平均可达40%左右。
(3)飞机流结构对延误的影响
来流飞机中,在以大型飞机为主体的情况下,随着小型飞机的减少和重型飞机的增多,总体延误时间的缩减程度不断增大,重型飞机和大型飞机延误的缩减明显,缩减程度最高可达40%左右。经过优化排序后小型飞机的延误缩减程度较大,但飞机流结构对小型飞机延误的缩减程度影响较小,无论在何种飞机流结构中,小型飞机延误的缩减程度基本维持在40%左右。
4 结论
相对于FCFS排序,最优排序可以大幅缩减飞机的延误时间,因此对终端区着陆飞机进行优化排序是十分必要的,而飞机平均到达率和飞机流结构是对终端区优化排序结果有重要影响的两个参数,通过研究可知:随着平均到达率的减小,重型飞机和大型飞机延误减小非常明显,而小型飞机延误减小有限;随着大型飞机和小型飞机所占比例的逐渐减少,重型飞机和大型飞机延误可以得到明显的缩减,而小型飞机延误的缩减程度变化较小。通过对这两个参数进行研究,可以为终端区飞机的着陆调度提供借鉴和参考,同时为进一步研究跑道容量与来流飞机的关系打下基础。
摘要：为了找出终端区平均到达率和飞机流结构与优化排序结果之间的关系,通过选取平均到达率和飞机流结构的不同组合,再使用循环排序找出最优结果。在此基础上,分别研究和分析了平均到达率和飞机流结构对飞机流总体、重型飞机、大型飞机和小型飞机优化结果的影响程度。经过大量数据仿真和统计表明:当终端区有10架待降飞机时,与先到先服务原则相比,平均可以减小延误达30%左右。重型飞机和大型飞机的延误对平均到达率的变化较为敏感,而小型飞机则非常有限。从飞机流结构变化的角度看,随着大型飞机和小型飞机所占比例的逐渐减少,重型飞机和大型飞机延误可以得到明显的缩减,而小型飞机延误的缩减程度变化较小。研究结果可以为终端区飞机的着陆调度提供借鉴和参考,同时为进一步研究跑道容量与来流飞机的关系打下基础。