基于容流匹配的进离场航班调度优化模型和算法.pdf

第4 7 卷第6 期 2 0 1 5 年1 2 月 南 J o u r n a lo f 京航 N a n j i n g D O I ：1 0 1 6 3 5 6 j 1 0 0 5 2 6 1 5 2 0 1 5 0 6 0 0 6 空航天大学学报 U n i v e r s i t yo fA e r o n a u t i c s & A s t r o n a u t i c s V 0 1 4 7N o 6 D e c 2 0 1 5 基于容流匹配的进离场航班调度优化模型和算法 王莉莉胡畔 ( 中国民航大学空中交通管理学院，天津，3 0 0 3 0 0 ) 摘要：综合考虑机场的空中等待航班数量、空域容量、场面容量以及机场起飞需求等约束条件，以可变的优先级为 调配手段，以总延误时问最短为目标函数，建立了一个新的基于客流匹配的进离场航班调度优化模型。引入合作 型协同进化遗传算法，设计了用一对代表个体形成合作团体的新选择方式，有效解决了传统遗传算法种群多样性 低、易早熟等问题。仿真结果表明，该模型能够在满足机场容量限制的同时，有效降低航班的总延误时间。 关键词：空中交通流量管理；合作型协同进化遗传算法；进离场航班序列优化；容流匹配；代表个体 中图分类号：V 3 5 5文献标志码：A文章编号：1 0 0 5 2 6 1 5 ( 2 0 1 5 ) 0 60 8 2 7 0 6 A r r i v a la n dD e p a r t u r eS c h e d u l i n gO p t i m i z a t i o nM o d e la n dA l g o r i t h m B a s e do nM a t c h i n go fT r a f f i cF l o ww i t hC a p a c i t y W a n gL i l i ，H uP a n ( C o l l e g eo fA i rT r a f f i cM a n a g e 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 n ，3 0 0 3 0 0 ，C h i n a ) A b s t r a c t ：T h r o u g ha l l o c a t e dm e t h o d so fv a r i a b l ep r i o r i t y ，an e wa r r i v a la n dd e p a r t u r es c h e d u l i n go p t i m i z a t i o nm o d e lb a s e do nt h em a t c h i n go ft h et r a f f i cf l o ww i t ht h ec a p a c i t yi se s t a b l i s h e dw i t ha no b j e c t i v e o fm i n i m u mt o t a ld e l a yt i m es u b j e c tt oc o n s t r a i n t s ，i e ，t h en u m b e ro ff l i g h t sw a i t i n gi nt h ea i r p o r t ， t h ea i r s p a c ec a p a c i t y ，t h es u r f a c ec a p a c i t ya n dt h ed e p a r t u r ed e m a n do ft h ea i r p o r t An e ws e l e c t i o n m e t h o db a s e do nt h ec o o p e r a t i v eC O e v o l u t i o n a r yg e n e t i ca l g o r i t h mi se s t a b l i s h e du s i n gap a i ro fr e p r e s e n t st of o r mac o o p e r a t i v eg r o u p ，w h i c hc a ne f f e c t i v e l ys o l v et h el o wp o p u l a t i o nd i v e r s i t ya n dp r e m a t u r eo ft r a d i t i o n a lg e n e t i ca l g o r i t h m T h es i m u l a t i o nr e s u l t si n d i c a t et h a tt h em o d e lc a ne f f e c t i v e l yr e d u c et h et o t a ld e l a yt i m eo ft h ef l i g h t sa n dm e e tt h ec a p a c i t yl i m i tr e q u i r e m e n to ft h ea i r p o r t K e yw o r d s ：a i rt r a f f i cf l o wm a n a g e m e n t ；c o o p e r a t i v eC O e v o l u t i o n a r yg e n e t i ca l g o r i t h m ；s c h e d u l i n go p t i m i z a t i o nf o ra r r i v a la n dd e p a r t u r ef l i g h t s ；m a t c h i n go fc a p a c i t yw i t hf l o w ；r e p r e s e n t s 近年来，繁忙机场的拥堵现状致使航班正点率 一直不高。出现拥堵问题的根源在于机场容量与 流量需求之问不匹配。在对我国实际运行的流量 管理系统的调研中发现，目前着重于通过限制起飞 来缓解空中压力，未能很好地从空中地面容量流量 协调考虑，没有最大程度利用机场和空域的资源。 基金项目 资助项目 收稿日期 作者简介 通信作者 如何全面考虑空中、地面的容量和流量需求，动态 优化调度航班的起降，在满足各约束条件的情况 下，最大化地利用空域和机场资源是本文研究的 重点。 学者对于跑道容量优化以及针对跑道的进离 场航班排序优化方面的问题展开了诸多研究， 国家自然科学基金委与中国民用航空局联合( 6 1 1 7 9 0 4 2 ) 资助项目；中央高校基本科研经费( Z X H 2 0 1 2 L 0 0 5 ) ：2 0 1 5 0 8 1 5 ；修订日期：2 0 1 5 1 0 1 5 ：王莉莉，女，博士，教授。主要研究方向：空域规划，空中交通优比理论。 ：王莉莉，E m a i l ：l l w a n g c a r t e e d u c n 。 万方数据 8 2 8南京航空航天大学学报 第4 7 卷 D e a r 】3 于2 0 世纪7 0 年代提出将位置约束法 ( C R S ) 应用于航班的优化排序问题。B a l a k r i s h n a n 等 2 在D e a r 研究基础 1 1 上建立了网络图。除此之 外，滑动窗策略 3 、分支定界法 4 J 、模糊规划方 法口书3 等优化方案也被应用至解决此类问题中。随 后，智能算法 7 。10 被引入航班进离场优化中。王莉 莉等 1 考虑尾流间隔、位置约束等限制条件给出了 平行跑道进场航班优化序列以及遗传算法仿真。 C i e s i e l s k i d 等 8 。9 3 分别采用传统遗传算法、结合滑 动时间窗策略的遗传算法优化航班进离场序列。 张勰等口叩对传统的协同进化遗传算法进行改进， 通过确定组合优化问题中，多约束条件所占总优化 过程的影响大小而获得最优排序。在上述研究中， 仅单独考虑进场、离场或是单跑道情况，未综合考 虑航班延误时的机场空域容量及场面运行容量的 限制。 李习凤口通过以时刻表为依据，以优先级为 手段提出了航班的地面等待策略。陈仲恒等口2 根 据航班类型和载客数量计算航班的优先级，以经济 损失和人员延误损失为目标，建立了优化模型。在 上述研究中，航班优先级是静态的，未从容流匹配 的角度确定优先级。 针对上述研究中存在的问题，本文提出了一种 新的基于容流匹配的进离场航班调度优化模型，容 流匹配是指综合考虑机场空中降落和地面起飞需 求、空域和机场场面容量限制，合理安排航班的起 降，使机场效益最大化。本文所提模型综合考虑进 离场多跑道体况下提出，考虑了机场空域容量及场 面运行容量的限制，从容流匹配的角度设计了动态 优先级。在算法上，采用合作型协同进化遗传算法 ( C o o p e r a t i v ec o e v o l u t i o n a r yg e n e t i ca l g o r i t h m ， c c G A ) ，相比传统的遗传算法，加入了竞争环境对 进化的影响，设计了一对代表个体形成合作团体的 优化方式，很大程度上弥补了传统遗传算法种群多 样性低的缺点。 1 容流匹配模型 1 1 模型原理 实时动态提取机场上空需降落的航班数量及 场面需起飞的航班数量，当二者均未超过容量限制 时，按照尾流间隔、降落时间窗等对其采用遗传算 法迭代优化排序；当需进场的航班数量超过其容 量，且场面容量未达到饱和时，为先到达的部分需 进场航班分配较大的优先级，保证进场航班更多地 被分配到时隙，能够尽快降落；当场面航班数量超 过其容量时，停止增加新的需起飞航班，且为最早 等待的部分需起飞航班分配较大的优先级，保证离 场航班能更多地被分配到时隙，尽快起飞；当机场 的总流量超过其总容量时，停止新增需进场航班和 需离场航班，保证机场已运行的航班有序运行。 1 2 模型假设 假设1 ：假设机场为多跑道机场，且相邻跑道 间的运行模式为独立平行仪表进近。 假设2 ：每个航班的预计起飞时间或预计降落 时间已知。 假设3 ：引入“时基”概念，整个计算过程中，统 一以时间为标准，将管制规则中的距离问隔转换为 时间间隔。 1 3 目标函数 以总延误时间最小为目标，目标函数为 z r a i n ( S T 。一E T 。) ( 1 ) 式中：z 为总延误时间；S T 。为第m 个航班的计划 进场离场时间；E T 。为第m 个航班的预计进场 离场时间；N 为航班的总架数。 1 4 决策变量 根据模型所需约束条件，设计决策变量z ， y 。，2 P ，K 。，K ，K 。其中式( 2 4 ) 的设计为满 足跑道约束和间隔约束的需要；式( 5 ) 用于比较任 意两个航班的优先级，其中多。( 仇 p m ( 5 ) 【0p 。( ) P 。( ) f 1R ( ) C ，( ) K o 一幅肌) c 一 万方数据 第6 期王莉莉，等：基于容流匹配的进离场航班调度优化模型和算法 8 2 9 f 1A ( f ) C 。( f ) K I 一坛舭) 乏夏 ，f 1 R ( 一1 ) + A ( 一1 ) C 。( ) + C 。( ) 【0R ( t 一1 ) + A ( 一1 ) C 。( ) + C 。( f ) ( 8 ) 1 5 约束条件 1 5 1 跑道约束 在为进离场航班分配跑道时，只能为进场或者 离场的航班分配某一条固定跑道。令r 为机场跑 道数，N 。为进场航班数，i 代表该航班为进场航 班，J 代表该航班为离航班。则式( 9 ，1 0 ) 分别表示 了对于所有进场和离场的航班都被分配了一条跑 道，且只能分配一条跑道。 R I i r 一1 i 一1 ，2 ，N 。；r 一1 ，2 ，R ( 9 )