基于ISWO的机场进离场航班优化排序研究.pdf

第3 l 卷第7 期计算机仿真 2 0 1 4 年7 月 文章编号：1 0 0 6 9 3 4 8 ( 2 0 1 4 ) 0 7 0 0 6 3 0 5 基于I S W O 的机场进离场航班优化排序研究 徐肖豪，于跃，黄宝军，郭晓明 ( 中国民航大学空管基地，天津3 0 0 3 0 0 ) 摘要：为了有效提高平行跑道机场运行效率，选择合理的进离场航班排序方式成为管制工作中的关键问题。针对上述问题， 将一种新型启发式智能优化算法一吱呀轮优化算法( S q u e a k y W h e e lO p t i m i z a t i o na l g o r i t h m ，S W O ) 应用于进离场排序问题，构 造了不同运行模式下的平行跑道进离场排序模型，设计并建立了基于S W O 的机场进离场航班排序算法( S A A D A S ) 。同时 对吱呀轮算法进行了改进，引入了选择操作和变异操作。使得改进的吱呀轮算法( I S W O ) 收敛速度更快并能够得到合理的优 化结果。仿真结果表明：与遗传算法相比较，改进的S W O 算法可以在更短时间内，得到更优化的、并符合管制实用性要求的 结果。改进S W O 算法仿真的总延误时间比遗传算法仿真的总延误时间减少了近2 分钟，减少近6 优化效果明显有效。 关t 词：操作模型；平行跑道；吱呀轮优化算法；航班延误 中圈分类号：T P 2 0 2 + 7文献标识码：B R e s e a r c ho nA r r i v a la n dD e p a r t u r eS e q u e n c i n gB a s e do nI S W O X UX i a o - h a o ，Y UY u e ，H U A N GB a o - j u n ，G U OX i a o - m i n g ( S c h o o lo fA i rT r a f f i c M a n a g m e n t ，C i v i lA v i a t i o nU n i v e r s i t yo fC h i n a ，T i a n j i n3 0 0 3 0 0 ，C h i n a ) A B S T R A C T ：I no r d e rt oi m p r o v et h eo p e r a t i o ne f f e c t i v eo fp a r a l l e lr u n w a y sa i r p o r t ，t h ek e yt h i n gi nc o n t r o l l e r s 、j o bi s t oc h o o s ea na p p r o p r i a t ea r r i v a la n dd e p a r t u r es e q u e n c i n gm o d e l T ot h i sp r o b l e m ，an e wh e u r i s t i ci n t e l l i g e n ta l g o - r i t h mc a l l e dS q u e a k yw h e e lo p t i m i z a t i o na l g o r i t h mw a su s e di na r r i v a la n dd e p a r t u r es e q u e n c i n gp r o b l e m ，t oc o n s t r u c t am o d e lo fa r r i v a la n dd e p a r t u r es e q u e n c i n ga n dd e s i g nS A A D S A M e a n w h i l e ，S W Ow a si m p r o v e d T h es e l e c t i o no p e l a t i o na n dm u t a t i o no p e r a t i o nw e r ea d d e di n t ot h i sa l g o r i t h m ，i no r d e rt om a k eI S W Oc o n v e r g e n c eq u i c k l ya n dg e ta g o o dr e s u l t T h es i m u l a t i o nr e s u l ti n d i c a t e st h a tI S W O ss i m u l a t i o nv e l o c i t yi sq u i c k e ra n dt h er e s u l ti sb e t t e rt h a nG A b A n di t1 3 8 1 1 s a t i s f yc o n t r o l l e r s d e m a n dw e l l I S W O sr e s u l ti sa b o u t2m i n ss h o r t e r r e d u c i n g6 t h a nG A s K E Y W O R D S ：O p e r a t i o nm o d e l ；P a r a l l e lr u n w a y ；S q u e a k y - w h e e lo p t i m i z a t i o na l g o r i t h m ；A i r c r a f td e l a y l引言 随着我国航空运输业的快速发展，国内的机场变得越来 越拥挤，进离场航班数量也在快速增长，这导致航班的延误 数量和延误时间出现了大幅度上升。为了有效减少此类问 题的发生，从2 0 世纪6 0 年代起，美国和欧洲的专家对此进 行了大量研究，八十年代起我国也陆续开始了相关领域的研 究。 这些研究总结起来可以分为以下典型的几类算法：基 于先到先服务算法4 1 的航班调度问题；位置约束交换算 法哺。8 1 ；基于不同的启发式智能算法阻7 1 的航班调度问 题。虽然这些方法有其自身的优点，但仍具有一定的局限 性。比如所考虑的影响进离场排序因素不够全面，在运算时 基金项目：国家自然科学基金委员会与中国民用航空局联合资助项目 ( 6 1 0 3 9 0 0 1 ) ，中央高校基本科研业务费资助 ( Z X H 2 0 1 2 D 0 0 2 ) 收稿日期：2 0 1 3 1 0 2 3 的收敛速度较慢等。吱呀轮优化算法相比较这些算法，它的 迭代思想在算法运算时的收敛速度较快，加以一定的优化改 进收敛速度还可更快，并且可以在其分析器步骤中多方面的 考虑影响因素，从而能够较全面并且较快速度的得到合理的 优化结果。 本文提出了一种新型智能算法一一改进吱呀轮优化算法 来解决进离场航班排序问题，并与F C F S ( 先到先服务算法) 、 G A ( 遗传算法) 进行了比较。为了突出改进吱呀轮算法的优 势和工作效率，特此在算法中加入了选择操作和变异操作： 为了分析较为全面，在分析器处理时对几个影响进离场排序 较为重要的因素进行了分析。 2 进离场排序问题及模型建立 2 1 进离场排序 机场对进离场航班排序时，要对地面和空中两个环节的 航班进行排序，之后再将这两个环节有机的考虑到一起进行 统一的权衡。地面的航班排序实质上是对离场航班的排序， 一6 3 万方数据 需要考虑多方面的影响因素，如航班时刻表，安全尾流间隔， 相邻航班的预计飞行高度、所飞航路和航空器的离场速度， 跑道占用时间，航班优先级等因素。空中的航班排序可以看 做进场航班的排序，需要考虑安全尾流间隔，进场预计时刻， 航班的飞行速度，即将进入进近区域前使用的航路等因素。 不论是地面还是空中的航班，都要将尾流间隔作为最为重要 的考虑因素。此外，将进离场航班统一地进行排序时，要确 保跑道上同时只能最多有一架飞机在使用，并且进场航班的 优先级一般情况下要高于离场航班的优先级。当满足了这 些要求时方可进行行之有效的排序方案。 平行双跑道进离场排序要考虑的因素包括跑道构型及 其运行模式的选择，以及跑道的分配策略停机位位置对排序 的影响。平行跑道机场按跑道间距可分为近距跑道、中距跑 道和远距跑道。不同跑道构型机场运行时跑道运行模式有 着多种搭配。不同搭配可概括为以下四种：一条跑道只用于 起飞，另一条只用于降落( 近距平行跑道机场常用此运行模 式) ；两条跑道都可用来起降且互不相关( 远距平行跑道机场 常用此运行模式) ；两条跑道都可用来起降但彼此相关；一条 跑道用于起降，另一条只用于起或降。通常情况起飞跑道选 择距航站楼近的那条跑道。 2 2 数学模型 结合平行双跑道机场的不同运行模式，本节具体构造了 平行跑道的进离场排序模型。分别为近距平行跑道机场的 一起一降运行模式、远距平行跑道机场的两起两降运行模 式。 首先做如下约定，在某一时间段T 内，共有F 架等待排 序的航班，其中有F A 架进场航班 F A l ，F A 2 ，F A n ，预 计降落在各跑道时间E T A ( E s t i m a t e dT i m eo fA r r i v a l ) ；F D 架 离场航班 F D l ，F D 2 ，F D m ，预计离场飞机起飞时间为 E T D ( E s t i m a t e dT i m eo fD e p a r t u r e ) 。航班的进离场都要满足 尾流安全间隔的限制。 2 2 1 近距平行跑道机场的一起一降运行模式 为了达到进离场航班总延误最小，因此设置目标函数 为： O b j e c = ：坩( t o 一再( 地，a s + 虺，a I ) ) ( 1 ) 约束条件为： Z Y a f o 。= 1 ，V f a F A ( 2 ) y 咖，= 1 ，V f d F D ( 3 ) y ，= 1 ，V p P a ( 4 ) 心，= 1 ，V p P d ( 5 ) z ，= 1 ，V f a F A ( 6 ) 戈啪，= 1 ，V 肋 ( 7 ) o Y d f d p a a f d + 烨p a ，V p P 。+ P d ( 8 ) 6 4 如嘱y a f , o 。+ d e l f t ) + 薪嘲o 。a i d + d e k ) ， V p P a + P d( 9 ) t P t o _ l + ( y d 唧+ 蚂护1 1 ) d i j ，V p ，p 一1 P ，i j F ( 1 0 ) t P t p _ l + ( y d P + 玛扩l 一1 ) d i j ，V p ，P 一1 EP ，t , j F ( 1 1 ) t o t p _ l + ( y a j p + y 吁，p l 一1 ) d f J ，V p ，P 一1 P ，i ，EF ( 1 2 ) t p t o _ 1 + ( y a l ，p + 蚂l 一1 ) d i j ，V p ，P l P ，i , j F ( 1 3 ) 其中n ，是航班，预计进场或预计离场的时间，Y a i 。代表如果 航班，在进场队列中位于位置P 则它等于1 否则为O ，y a f , 。表 示如果航t i f f 在离场队列中位于位置p 则它等于l 。t 。指的是 处于进场或离场排序中的位置P 的航班进离场时间。其中 a a I ，e t a 。代表预计到场时间( E T A s ) 和预计离场时间( E T D s ) ， a e l I o 和d , l i d 代表进场航班工和离场航班五的占用的时间窗 大小。d “代表航班i 与其后续航班J 之间的最小安全间隔， 不同机型搭配时根据具体的间隔要求选择使用。凡，P d 代 表进场，离场各自的排序的集合。R 表示可使用的跑道数 量，r 表示具体使用的跑道。变量方面，x a i , ，并喀，表示如果航 班，选择跑道r 进行进场或离场，那么它