（计算机应用技术专业论文）航班着陆调度的智能优化方法研究.pdf

摘要 摘要 作为终端区空中交通流量管理( a i rt r a f f i cf l o wm a n a g e m e n t , a t f m ) 拘核心 内容之一，航班着陆调度( a i r c r a f tl a n d i n gs c h e d u l i n g ，a l s ) 旨在为待降落的航 班给出有效的着陆调度方案，保证每架航班能够安全地依次着陆。研究航班着 陆调度问题对确保飞行安全及提高飞行效益具有重大的意义。先来先服务是一 种最简单快速的调度方法，但在航班较密集的情况下该算法可能无法给出一个 合理的调度方案。目前解决航班着陆调度问题的优化调度算法大致可以分为两 大类：线性规划算法和计算智能算法。线性规划算法具有高效性和正确性，但 缺乏全局搜索能力，在某些情况下很难找到最优解。而计算智能算法不仅具有 强大的全局搜索能力，而且能够处理非线性的复杂约束及目标函数，因此近年 来用计算智能算法解决航班着陆调度问题成为一个研究热点。然而计算智能算 法容易产生大量的计算负担，特别是在较为繁忙的机场终端区，所以它需要结 合有效的启发式方法才能更好的解决航班着陆调度问题。 本文针对机场终端区的航班着陆调度优化问题，构建了一个航班着陆调度 模型，并在该模型基础上提出了一个基于滚动时域控制和免疫克隆选择算法的 优化算法( h y b r i da l g o r i t h mo fc l o n a ls e l e c t i o na l g o r i t h ma n dr e c e d i n gh o r i z o n c o n t r 0 1 ) ，简称c s a r h c 算法。 在c s a r h c 算法中，针对航班着陆调度问题多约束的特点，我们设计了 有效的约束处理策略。该约束处理策略包括带约束处理的编码策略和基于不可 行度的免疫算子的设计。带约束处理的编码策略可以将原问题的约束量级从 o ( n 2 ) 降低到d ( ，2 ) ，有效的减少了约束数量。在解的不可行度的基础上，我们 重新设计了针对性的免疫克隆选择算法中的克隆，变异和选择算子。本文提出 的约束处理策略取得了令人满意的优化结果，显示了该策略处理约束的能力。 在c s a r h c 算法中，为迸一步加快算法的搜索速度，我们提出了优秀基 因片段传播( e x c e l l e n tg e n es e g m e n ts p r e a d ，e g s s ) 的策略。在每一个滚动时域 内，经过c s a 算法优化后得到的某些基因片段包含很有价值的信息，我们可以 在下一个滚动时域的种群初始化时充分利用这些有用信息。这样，优秀的基因 片段可以沿整个滚动域传递下去，加快算法的搜索最优解的速度。 关键词：航班着陆调度计算智能滚动时域控制免疫克隆选择算法约束 处理策略 a b s t r a c t a so n eo ft h ec o r ec o n t e n t so fa i rt r a f f i cf l o wm a n a g e m e n t ( a t f m ) i n t e r m i n a la r e a , a i r c r a f tl a n d i n gs c h e d u l i n g ( a l s ) d e t e r m i n e sa ne f f i c i e n tl a n d i n g s c h e d u l i n gs c h e m ef o rag i v e ns e to fa i r c r a f t si no r d e rt oi n s u r et h es a f e t yo fa i r c r a f t s r e s e a r c h e sa b o u ta l sp r o b l e mh a v eg r e a ts i g n i f i c a n c ef o rf l i g h t s a f e t ya n d i m p r o v i n gf l i g h tb e n e f i t f i r s t c o m e f i r s t s e r v e dc a ns c h e d u l et h el a n d i n ga i r c r a f t s v e r ys i m p l ya n dr a p i d l y , h o w e v e ri tm a yf a i lt op r o v i d ear e a s o n a b l es c h e d u l i n g s c h e m eu n d e rd e n s ea i r c r a f t s u n t i ln o w , t h e r eh a v eb e e nt w ok i n d so fs c h e d u l i n g a l g o r i t h m sf o ra d d r e s s i n ga l sp r o b l e m ，o n ei sl i n e a rp r o g r a m m i n g ( l p ) a l g o r i t h m ， a n dt h eo t h e ri s c o m p u t a t i o n a li n t e l l i g e n c e ( c i ) a l g o r i t h m l ps h o w sh i g h e f f e c t i v e n e s sa n dc o r r e c t n e s s ，h o w e v e ri tc a nh a r d l yf i n dt h eg l o b a lo p t i m a ls o l u t i o n o w i n gt ol a c ko ft h ea b i l i t yf o rg l o b a ls e a r c h n e v e r t h e l e s sc in o to n l yh a st h e p o w e r f u la b i l i t yf o rg l o b a ls e a r c h ，b u ta l s oi sa b l et oh a n d l en o n l i n e a rc o n s t r a i n ta n d g o a lf u n c t i o n t h e r e f o r ei th a sb e c o m ea h o tt o p i ct or e s o l v ea l s u s i n gc i h o w e v e r c il i k e l yp r o d u c e sl a r g ec o m p u t a t i o n a lc o s te s p e c i a l l ya tb u s ya i r p o r t s t h e r e b yc i n e e d st oc o m b i n es o m eh e u r i s t i cm e t h o d st oa d d r e s sa l sb e t t e r i n t h i sp a p e r , w ee s t a b l i s ha na l sm o d e la n dp r o p o s e dah y b r i da l g o r i t h mo f c l o n a ls e l e c t i o na l g o r i t h ma n dr e c e d i n gh o r i z o nc o n t r o l ( c s a r h c ) b a s e do n t l l i sm o d e l b a s e do nt h em u l t i c o n s t r a i n tc h a r a c t e r i s t i co fa l sp r o b l e m ，a ne f f e c t i v e c o n s t r a i n th a n d l i n gs t r a t e g yi sp r o p o s e d ，w h i c hi n v o l v e st h ee n c o d i n gs t r a t e g yw i t h c o n s t r a i n th a n d l i n ga n di m m u n eo p e r a t o r sb a s e do ni n f e a s i b i l i t yd e g r e e t h en e w e n c o d i n gs t r a t e g y r e d u c e st h en u m b e ro fc o n s t r a i n t s e f f e c t i v e l yb e c a u s et h e c o n s t r a i n tm a g n i t u d ei sd e c r e a s e df r o mo ( n 2 ) t oo ( n ) w r er e d e s i g nt h ec l o n e ， c l o n a lm u t a t i o n ，a n dc l o n a ls e l e c t i o no p e r a t o r sb a s e do ni n f e a s i b i l i t yd e g r e e t h e p r o p o s e dc o n s t r a i n th a n d l i n gs t r a t e g yo b t a i n e db e t t e rs o l u t i o nt h a no t h e rm e t h o d s t h ec o n s t r a i n th a n d l i n ga b i l i t yo f c o n s t r a i n th a n d l i n gs t r a t e g yi se x t e n s i v e l yv e r i f i e d i no r d e rt o s p e e du ps e a r c h ，e x c e l l e n tg e n es e g m e n ts p r e a d ( e g s s ) i s d e s i g n e d d u r i n ge a c hr e c e d i n gh o r i z o n ，s o m eg e n es e g m e n t sa f t e rt h es c h e d u l i n g u s i n gc s a o b t a i nv e r yu s e f u li n f o r m a t i o n ，w h i c hc a nb em a d ef u l lu s eo fd u r i n gt h e n e x tr e c e d i n gh o r i z o n t h ee x c e l l e n tg e n es e g m e n t sc a nb es p r e a do v e rt h ee n t i r e r e c e d i n gh o r i z o n t oi m p r o v et h es p e e do f s e a r c h i n gt h eo p t i m a ls o l u t i o n i a b s t r a c t k e yw o r d s ：a i r c m f tl a n d i n gs c h e d u l i n g ，c o m p u t a t i o n a li n t e l l i g e n c e ，r e c e d i n g h o r i z o nc o n t r o l ，c l o n a is e l e c t i o na l g o r i t h m ，c o n s t r a i n th a n d l i n g s t r a t e g y i v 插图 插图 2 1a l s 模型示意图9 2 2 刀= 5 ，七= 1 的c p s 网络1 2 2 3 遗传算法流程图1 3 3 1 c s a - r h c 算法的基本框架示意图”1 7 3 2 四种优化策略的示意图1 9 3 3 基于滚动时域控制的a l s 示意图”2 0 3 4 克隆选择算法流程图2 3 3 5 盯取值对高斯分布曲线的影响3 l 3 6e g s s 策略的示意图3 3 3 7c s a r h c 算法流程图3 5 4 1 滚动时域长度对性能的影响4 l 表格 表格 2 1 刀= 5 ，k = l 时可能的航班分配1 2 3 1 免疫算法和免疫系统之间的比较一2 l 4 1 航班数据”3 7 4 2 最小时间间隔表3 8 4 3 四种调度算法的实验结果对比3 9 4 4 约束处理策略有效性的对比实验结果；一4 3 4 5 优秀基因片段传播策略有效性的对比实验结果4 5 4 6 滚动时域控制策略有效性的对比实验结果( 一) 4 7 4 7 滚动时域控制策略有效性的对比实验结果( - - ) 4 8 5 9 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作 了明确的说明。 作者签名：趔签字日期：j 竺塑掣 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 娅讼开 口保密(年) 作者签名：衄 签字日期：三驾碑柚一 导师签名： 签字目期：丝竺乞：至么 第1 章引言 1 1 研究背景 第1 章引言 近些年我国经济高速增长，为我罾民用航空事业的发展提供了良好的外部环 境。从1 9 9 4 年到2 0 0 3 年我国民航的实际航班飞行量年平均增长1 5 4 1 ，最近 几年发展势头更为迅猛，保持了1 6 以上的增长。据国际民航组织统计，2 0 0 5 年我国航空公司定期航班完成的总周转量为2 5 7 7 6 5 亿吨公里，比2 0 0 4 年增长 了1 2 ，世界排名由2 0 0 4 年第3 位上升至第2 位，超过了航空强国德国( 2 5 4 5 7 亿) ，成为仅次子美国的世界第二航空运输大国。然而随着空中交通运输量的增 加，我国原来的空中交通管制方式已经不能满足于目益增长的交通量的需要，低 效的流量管理方式导致了大量的航班延误，造成了巨大的经济损失。因此加快建 立合理有效的空中交通流量管理系统成为目前我国民航极为迫切的任务。 国外早在上个世纪7 0 年代中期就开始了流量管理系统的研究，最初是为了 缓解局部航运阻塞而设计和开发的专用系统，经过二三十年的发展，已成为空中 交通管理系统中的重要组成部分。从2 0 世纪6 0 、7 0 年代起，美国、欧洲、日本 等国根据本国、本地区的特点，都先后建立了覆盖整个国家的流量管理系统，而 目前我国的空中交通流量管理还是初步的，粗放式的、自动化程度很低的管理， 空中交通流量管理体系还没有完全建立，相关研究工作还处于起步阶段。 空中交通流量管理系统的任务是在空中交通流量接近或达到空中交通管制 可用能力时，进行适当的调整，保持空中交通量有次序地流动，使得机场和空域 的可用容量达到最有效的利用。从模式上可以把空中交通流量管理分为三类：先 期流量管理、终端区流量管理和具有寻径能力的空中流量管理( 高海军等，2 0 0 3 ) 。 其中终端区流量管理主要是指在本终端区的范围内进行飞行前流量控制和实时 交通管理，主要研究终端区航班到达流的排序规划问题，在不违反航班安全间隔 的情况下，为保证空中交通流的快速，有序地流动，合理安排飞机降落次序，根 据不同的原则给出相应的算法。机场终端区是航班从航路飞行到进离港阶段的飞 行过渡区，由于涉及机场容量、空域结构等复杂问题，它成为影响整个空管系统 效率的瓶颈。因此作为机场终端区流量管理的核心环节之一，航班着陆调度优化 算法的研究具有重大意义和价值。 在美国、欧洲以及澳大利亚，不少繁忙机场和终端区以及区域都使用了航班 进港排序辅助决策系统来配合空管员进行航班着陆调度。以澳大利亚为例，2 0 0 0 年悉尼奥运会前，悉尼终端管制中心建设了迸港排序辅助决策系统( m a e s t r o ) ， 第l 章引言 该系统与其使用的空管自动化系统( e u r o e a t ) 相结合，有效地降低了区域和进近雷 达管制员的工作压力，达到了加速进入终端区流量并降低延误的目的。排序辅助 决策系统不但使机场附近区域及终端区空中交通更加有序，提高了管制安全水平， 而且减少了燃油消耗，为航空公司节约了大量的运行成本。然而我国在机场终端 区航班着陆调度方面基本上还是处于人工管制阶段，依靠管制员的个人经验对待 着陆的航班队列进行适当的调整。相比航班进港排序辅助决策系统，人工管制不 仅效率很低，而且没有充分利用空域和地面的资源。因此建立进港排序的计算机 辅助决策系统对于我国民航事业的发展是非常必要的。随着“十一五”期间空管 信息化建设的提出，我国将着手在航班较为集中的终端区建立航班着陆调度计算 机辅助决策系统，以提高资源的利用率，减少航班延误造成的损失，并加快民航 信息化建设( 马正平等，2 0 0 3 ；赵嶷飞和王健，2 0 0 3 ) 。 1 2 研究意义 随着世界范围内空中交通流量的快速增长，特别是发达国家航运活动较为密 集区域，大量的航班延误不仅造成了巨大的经济损失，而且扰乱了飞行管制的正 常秩序，飞行安全也无法得到保障，使得许多国家的空中交通管制部门面临着前 所未有的压力。据统计，目前欧洲航空业因空中拥挤每年就损失5 0 亿美元之多， 其中超过2 0 的航班延误是由空管原因造成的。而在我国，东部地区集中了全国 9 0 以上的航空业务量，仅北京首都、上海虹桥和广州自云三大机场就集中了我 国民航约4 0 的旅客量和5 0 的货物量。正是由于这种地区流量分布的极不均 匀，增加了航班相撞和延误的概率，由此造成的经济损失是无法估量的。据民航 统计，由于航班不正常造成的损失占运行成本的2 3 ，据保守估算，我国航 空公司按每年9 0 亿元的运行成本计算，因不正常运行给航空公司造成的经济损 失高达1 8 亿元( 余江，2 0 0 5 ) 。由此可以看出在空中交通繁忙的区域如果不采用 有效的空中交通管制，就无法减少由于航班延误造成的巨大的经济损失，并确保 安全飞行。因此实施先进的空中交通流量管理对我国民航事业的发展是非常必要 的。 在空中交通流量管理中，由于空域容量、机场跑道容量等因素，机场终端区 是最容易造成飞行事故的区域，而我国目前的终端区交通管制缺乏科学有效的指 导，仍然是管制员凭经验对航班进行调整。人工调度效率很低，而且处理能力有 限，机场资源利用不足。因此研究机场终端区的流量管理对解决我国空中交通拥 挤的状况具有极大的现实意义。作为终端区交通流量管理的核心内容之一，航班 着陆调度研究旨在为终端区待降落的航班给出合理的着陆调度，保证每架航班能 2 第1 章引言 够安全地依次着陆，并尽可能减少航班延误给运营部门带来的经济损失。所以研 究终端区航班着陆调度对确保飞行安全及提高飞行效益具有重大的意义。 1 3 研究现状 航班着陆调度问题在最近的3 0 多年里得到了世界各国学者的广泛研究。先 来先服务算法( f i r s tc o m ef i r s ts e r v e d ，f c f s ) 是最简单快速的调度策略。这种调 度方法也是目前人工调度环境中管制员使用的方法。它是根据航班的预计到达时 间( e s t i m a t e dt i m eo f a r r i v a l ，e t a ) 的先后顺序来决定航班的实际着陆顺序，在保 证满足航班之间最小安全间隔的前提下使得各个航班在更靠近e t a 的时间点降 落。在终端区较为空闲时，采用先来先服务方法可以给出很好的调度方案。但是 在终端区较为繁忙，待着陆航班较为密集时，采用先来先服务方法无法给出最优 的调度方案，最坏的情况下甚至无法给出一个满足约束的调度方案。 n e u m a na n de r z b e r g e r ( 19 9 0 ) 提出的时间提前算法( t i m ea d v a n c e ) 只是对每 个航班队列的第一架航班进行加速，使之先于正常的预计到达时间着陆，这样该 队列后面的所有航班都可以减少相同时间的延误。因为该算法不改变整个航班队 列的原有顺序，所以它可以看成是对先来先服务算法的一种改进。 g r e g o r ye ta 1 ( 1 9 9 9 , 2 0 0 0 ) 基于公平原则提出了延误交换算法( d e l a y e x c h a n g e ) 。在等待着陆的航班面临延误时，航空公司会慎重考虑乘客的连续性、 重要航班的往返时间、准点要求、油料情况等因素，然后决定对等待队列中的某 架航班实施提前着陆，同时对该队列中的另一架航班实施延误处理。 以上三种航班着陆调度算法其实并不包含优化思想，当问题规模变大，这些 算法无法很好地解决航班着陆问题。所以体现优化思想的航班着陆优化调度算法 才是真正需要重点研究的，现有的航班着陆优化调度算法大致可以分为两类：一 类是线性规划算法，类是计算智能算法。 b e a s l e ye ta 1 ( 2 0 0 0 ) 为静态航班着陆优化调度问题给出了一个经典模型，该 模型的优化目标是最小化航班由于提前或延迟到达所造成的额外开销，认为航班 的额外开销与其提前或延迟的时间量成线性关系，而该模型的约束条件也是线性 的，因此这是一个线性目标函数在线性约束条件下的优化问题。我们可以采用线 性规划方法对航班着陆调度问题进行求解。b e a s l e ye ta 1 在给出航班着陆调度模 型的同时，也提出了上种基于树搜索的混合整数线性规划方法来解决静态航班调 度问题。在航班着陆的动态调度情况下，队列中每增加一架航班都需要对原来的 调度方案做出调整，这个调整会带来附加的开销。因此b e a s l e ye ta 1 ( 2 0 0 4 ) 设计 了一个移位罚值函数来评估这个开销，然后采用线性规划算法进行了充分的实验 第1 章引言 证明。d e a r ( 1 9 7 6 ) 首次提出了受限的位置偏移思想( c o n s t r a i n e dp o s i t i o ns h i f t i n g ， c p s ) ，意思是调度过程中航班的位置不是可以随意改变的，某个航班的初始位置 是它在f c f s 序列中的位置，那么该航班在排序过程中的位置只能位于以它的初 始位置为圆心，以某个值为半径的范围内。这个值被称为最大位置偏移( m a x i m u m p o s i t i o ns h i f t ，m p s ) ，一般可取1 或2 甚至更大。受限位置偏移思想可以大大缩 小搜索空间，加快了搜索速度。b a l a k r i s h n a na n dc h a n d r a n ( 2 0 0 6 ) 采用了动态规划 和c p s 相结合的方法，并用d e n v e r 国际机场的实际数据做了仿真实验取得了很 好的效果。 线性规划算法缺乏全局搜索的能力，在某些情况下很难找到最优解。而计算 智能算法作为另一类解决航班着陆优化调度问题的主流方法，却拥有强大的并行 和全局搜索的能力。此外计算智能方法可以处理非线性的复杂约束，并对非线性 的目标函数进行优化。目前使用最多的计算智能方法是遗传算法( g e n e t i c a l g o d t h m ，g a ) 。遗传算法是一种通过模拟自然进化过程搜索最优解的方法，与 传统的优化算法相比，它具有很强的鲁棒性和优秀的全局搜索能力，因此被广泛 应用于解决各种复杂优化问题。c i e s i e l s k ia n ds c e r r i ( 1 9 9 8 ) 使用了两种遗传算法： 标准遗传算法和带滑动窗口的遗传算法用于动态航班着陆调度。b e a s l e ye ta 1 ( 2 0 0 1 ) 提出了一种群体启发式算法来优化一个非线性的目标函数，其中设计了 一个群体移位策略来处理不可行解。更多采用g a 的研究见c h e n g ，h u 和z h a n g 等人的工作( c h e n ge ta 1 ，1 9 9 9 ；h ua n dd ip a o l o , 2 0 0 8 ；z h a n g e te 1 ，2 0 0 7 ) 。计算智 能也可以和线性规划相结合，e r n s te ta 1 ( 1 9 9 9 ) 提出了一个基于线性规划的单纯 算法和一个问题空间搜索启发式算法，并将两者结合，采用标准测试问题来进行 验证。计算智能算法尽管具有很强的全局搜索能力，但是它会产生大量的计算负 担，特别是在较为繁忙的机场终端区。这给在一个雷达信息更新时间内完成优化 调度带来了很大的挑战。 尽管如此，计算智能的方法仍是解决航班着陆调度问题的主流方法，它需要 结合有效的启发式方法才能更好的解决航班着陆调度问题。h ua n dc h e n ( 2 0 0 5 ) 将在工程领域被广泛应用的滚动时域控制引入到航班着陆调度问题中，并结合遗 传算法和线性规划用于多跑道的航班着陆调度。然而两种方法的简单结合并不能 在搜索过程中充分利用隐含的信息，因此有效的组合方法是值得研究的。本文正 是提出了一种计算智能和启发式方法有效结合的算法，并进行了深入的研究和讨 论。 1 4 本文的主要工作和内容安排 4 第l 章引言 本文重点研究了机场终端区航班着陆调度的优化算法。在一个合理的航班调 度模型的基础上，设计了启发式方法结合计算智能的优化调度算法：实验表明相 比其他算法，该算法能够有效减少约束条件，快速找到最优解，具有更强的全局 优化能力，并能够给出一个最合理的航班调度序列，使航班延误总成本最小。 本文的主要工作和特色有： 提出了一种滚动时域控制结合免疫克隆选择算法的航班着陆调度优化算法。 滚动时域是一种广泛应用在工程领域的在线优化策略，它的主要思想是分段 优化。免疫克隆选择算法是一类借鉴生物免疫系统原理的新型计算智能的方 法。首先我们在当前滚动时域区间内应用免疫克隆选择算法对相应的待降落 航班进行调度，然后滚动时域控制策略重复该优化过程，直到所有的航班都 已经着陆。实验证明滚动时域控制结合免疫克隆选择算法能够快速有效地找 到最优的着陆次序和着陆时间。 设计了一种针对航班着陆调度问题的约束处理机制。因为对于航班着陆调度 而言，约束是普遍存在的。每架航班都有时间窗约束，每两架航班之间都要 满足最小时间间隔约束，大量约束条件会严重影响优化算法的求解能力，因 此我们设计了具有针对性的约束处理机制，包括带约束处理的编码策略和解 的不可行度( i n f e a s i b i l i t yd e g r e e ，i f d ) 的定义。在解的不可行度的基础上，我 们将重新设计免疫克隆选择算法中的克隆，变异和选择算子。实验证明我们 提出的约束处理机制能够有效地减少约束，为找到最优解提供了保障。 针对滚动时域的特殊性，提出了优秀基因片段传播的策略。在上一个滚动时 域操作区间和当前滚动时域操作区间之间实施优秀基因片段传播策略，这样 可以在整个滚动时域上将有用的信息传递下去，加快全局搜索最优解的速度。 本文共分为五章，各章节内容安排如下： 第一章，引言。介绍了空中交通流量管理及机场终端区航班着陆调度的背景 知识，分析了研究终端区航班着陆调度的意义，并阐述了航班着陆调度研究的现 状。 第二章，机场终端区航班着陆调度a l s 的基本方法。首先详细阐述了航班 着陆调度问题及其特点，并给出了航班着陆调度的模型描述，然后回顾了航班着 陆调度领域的三种典型方法，最后对现有方法进行了全面的分析比较。 第三章，基于滚动时域控制和免疫克隆选择的a l s 算法。本章主要详细描 述了滚动时域控制结合免疫克隆选择算法的调度算法，首先给出了整个算法的基 本框架，接着设计了滚动时域优化策略和带约束处理的免疫克隆选择算法，为了 加快收敛速度还设计了优秀基因片段传播策略，最后对算法的特点进行了具体分 6 第1 章引言 析。 第四章，实验及结果分析。本章通过四个对比实验充分证明了我们的算法的 有效性。这四个对比实验分别是与现有工作的对比实验，约束处理策略有效性的 对比实验，优秀基因片段传播策略有效性的对比实验和滚动时域有效性的对比实 验。 第五章，总结与展望。对全文工作进行了总结，并讨论了进一步的研究工作。 第2 章机场终端区航班着陆调度a l s 的基本方法 第2 章机场终端区航班着陆调度a l s 的基本方法 本章首先给出航班着陆调度问题的定义及其特点，并详细描述航班着陆调度 的模型，然后介绍航班着陆调度研究的几种典型方法，对先来先服务算法、线性 规划算法和计算智能算法分别进行重点介绍。最后对现有的算法进行比较分析。 2 1 航班着陆调度问题 航班着陆调度的目的是在确保各航班着陆的安全性的基础上最小化由于航 班延迟等原因导致的额外成本。本节我们将详细阐述什么是航班着陆调度问题及 航班着陆调度的特点，并给出航班着陆调度的模型描述。 2 1 1 什么是航班着陆调度 机场终端区的进场航班通过空中等待或延迟来调整着陆次序时，往往要付出 很大的代价，造成严重的经济损失。因此如何对进场航班进行合理的排序和管理， 使航班安全有序的着陆，并保证航班的延误成本最小成为了航班着陆调度的研究 重点。 航班着陆调度问题是终端区交通流量管理的核心内容之一，它指的是针对给 定的待降落航班队列，在满足各种约束条件的情况下对其中的航班进行排序调度 并给出一个合理的调度方案，其中包括航班的着陆序列与具体的着陆时间。这里 的约束条件包括航班的时间窗限制和航班之间的最小安全间隔的限制。 首先每架航班的降落时间必须落在一个特定的时间窗内，该时间窗由一个最 早降落时间和一个最迟降落时间决定，不同航班的最早和最迟降落时间是不同的。 最早降落时间是指航班如果以它的最大飞行速度飞行的降落时间，最迟降落时间 主要是考虑到航班携带的燃料量。 其次出于空气动力学的考虑，任意两架航班之间都应该满足最小安全间隔约 束。比如某架航班飞行过程中会产生大的尾流，如果它后面的一架航班离的太近 的话就会失去飞行平衡，从而造成飞行事故。航班的机型不同，航班所产生的尾 流强度和承受尾流的能力也不同。国际民航组织( i c a o ) 依据允许最大起飞重量将 飞机分为重型机、中型机、轻型机，并规定了无风条件下不同类型飞机之间尾流 间隔的最低标准。大型机比如波音7 4 7 自身能够产生很强的尾流，同时也能够承 受很强的尾流而不至于失控。安全间隔不仅和两架航班的机型相关，还和两架航 班的相对位置有关。如果前机是大型机，后机是轻型机，则这两架航班之间的最 7 第2 章机场终端区航班着陆调度a l s 的基本方法 小时间间隔一定大于前机是轻型机，后机是大型机的情况( 郭圆平，2 0 0 8 ) 。 d e a r ( 1 9 7 6 ) 对航班着陆调度问题做了研究，指出航班调度可以分为静态航班 调度和动态航班调度两种。静态航班调度是指待调度的航班队列是固定不变的， 算法只需要给出最优的调度方案即可，并没有考虑航班到达加入队列以及航班降 落离开队列的情况；动态航班调度中，待调度的航班队列是随时间的改变而改变 的，每当待调度的航班队列发生变化时，模型需要在原来调度结果的的基础上进 行重新优化，并给出新的调度结果。 关于动态优化更新时机的选择，我们可以归纳为事件驱动型，时间驱动型以 及事件、时间混合驱动型。对于事件驱动型，当有新航班到达时，需要对新的队 列进行优化。因为航班到达时间具有随机性，当多架航班同时或连续小时间间隔 从不同航路进入终端区，将导致优化过程短时间连续启动，对优化算法实时性的 设计是一个极大的挑战；对于时间驱动型，以雷达扫描周期6 s ( 或倍数) 为单 位，当雷达信息更新时，启动优化算法，对队列进行优化。相比事件驱动型，时 间驱动型以雷达周期为优化间隔，更加符合管制实际，同时避免了短时间频繁更 新。但有可能雷达信息更新时刻，无新的到达事件发生，这时并没有必要进行优 化操作，反而增加了系统开销；对于事件、时间混合驱动型，以时间驱动型为基 础，在雷达信息更新时，探测是否有新的航班到达事件，如没有，则不进行优化； 反之，则对新的队列进行优化。 2 1 2 航班着陆调度的模型描述 本节我们将给出一个航班着陆优化调度的模型，该模型参考了b e a s l e ye ta 1 ( 2 0 0 0 ) 提出的经典单跑道模型。 下面我们将给出航班着陆调度模型的相关参数和定义： u 表示航班数量 z 表示航班f 的预计降落时间 巨表示航班i 的最早降落时间 厶表示航班i 的最迟降落时间 墨，表示航班z 和航班歹之间的最小时间间隔，航班i 在航班之前 吕表示航班i 先于预计降落时间互降落的单位成本系数 绣表示航班i 后于预计降落时间r 降落的单位成本系数 以下为该模型的约束示意图： 8 第2 章机场终端区航班着陆调度a l s 的基本方法 t i m ew i n d o w 喁亍 r 东一 s e p a r a t i o nt i m e 图2 1a l s 模型示意图 航班f 对应的时间窗是【e ，厶】，那么它的预计降落时间z 位于最早降落时间 和最迟降落时间之间，即e z 厶。假设航班珀勺实际降落时间是为，那么下 面的时间窗约束条件必须满足： e 而o = 1 ，) ( 2 1 ) 考虑一对航班( ，) ，如果航班f 在航班之前降落，则它们之间必须满足时 间间隔约束： 一薯岛( f = l ，u ；= 1 ，u ；i 歹) ( 2 2 ) 时间间隔约束是为了避免后面的航班不至于受到前面航班产生的尾流影响而造 成交通事故。从以上公式中我们可以看出不仅是顺序上相邻的航班间需要满足该 约束条件，那些顺序不相邻的也应该满足。 我们的目标是最小化由于航班早于或迟于预计降落时间而造成的额外成本。 在本文中我们认为额外成本与航班的预计降落时间和实际降落时间差的平方是 成正比的。因此航班f 的额外成本可以定义为： 9 第2 章机场终端区航班着陆调度a l s 的基本方法 那么我们的目标函数可以表示为： 弋1 u y = 乙硝乃 2 1 3 航班着陆调度问题的特点 ( 2 3 ) ( 2 4 ) 航班着陆调度是一个典型的n p h a r d 优化难题。首先对于航班较繁忙的机场 或是航线较密集的某段时间，需要调度的航班数可能非常多，那么问题的规模将 会增大。其次一个合理的调度方案首先要满足各个约束条件，否则被认为是不可 行的方案。这些约束条件包括：每个航班的实际着陆时间必须落在一个给定的着 陆时间窗内；任意两个航班之间必须满足最小安全间隔限制。正是由于航班着陆 调度问题的大规模多约束的特点，解决这类问题将会面临两个难点：一个是很难 找到最优解，另一个是优化过程中会产生较高的计算复杂度。此外航班着陆是一 个动态随机的过程，对调度算法的实时性要求特别高，例如要求在一个雷达扫描 周期( 6 秒) 内给出最新的调度方案。 由此可以看出，航班着陆调度自身的特点给优化调度算法的设计带来了很大 的挑战，我们必须进行具有针对性的设计并给出高效实时的调度方案。 2 2 航班着陆调度的典型方法 本节我们重点介绍以下三种航班着陆调度的典型方法，基于先来先服务的方 法，基于c p s 的线性规划方法和基于计算智能的方法。最后对这三种方法进行 深入的分析。 2 2 1 基于先来先服务的方法 先来先服务是一种最简单快速的航班着陆调度方法，也是人工调度环境中管 制员常采用的方法。假设有u 架航班序列( 4 ，匀) ，根据它们的预计降落时间 的先后来决定它们的实际降落顺序，那么u 架航班对应的降落顺序是一个 ( 1 ，u ) 的全排列，定义为( 6 l ，) 。重新排序后的u 架航班序列为( 厶，如) 。 我们设定第一架航班的实际降落时间等于它的预计降落时间，即= 五，那么第 1 0 葺而 一 1 ) ( 2 6 ) = + ) ，气) ( = 1 ，一， 1 ) 、7 2 2 2 基于c p s 的线性规划方法 采用受限位置偏移策略是另一类解决航班着陆调度问题的常用方法。由于篇 幅所限，本小节将重点介绍c p s 思想，线性规划方法可以参考b e a s l e ye ta 1 ( 2 0 0 0 ) 中的0 ，l 混合整数线性规划。假设航班数为，| ，最大位置偏移值为k ，那么每 一个k c p s 序列可以表示为定向图的一条路径，该定向图的大小又参数r 和k 决 定。c p s 网络包含丹段 l ，刀) ，每段对应着航班在最终序列中的位置。网络中的 第g 段的一个结点表示航班的一个子序列，该子序列的长度是m i n 2 k + l ，p 。当 刀= 5 ，k = 1 ，由表2 1 可以清楚地看出每个位置上可能的航班分配情况。比如 在位置2 ，可能分配的航班是l ，2 ，3 ：在位置5 ，可能分配的航班为4 ，5 。c p s 网络图如图2 2 所示，第3 段到第5 段中的结点表示终止于当前段的长度为 2 k + l = 3 的所有可能的序列。第2 段中的每一个结点都对应一个终止于该段的长 度为2 的航班序列。同理第l 段中的每一个结点都对应一个开始于该段的长度为 1 的航班序列。 对于c p s 网络中任意段的某个结点，我们都可以画若干条弧线连接到后一 段中合适的结点上。比如第2 段中的序列( 2 1 ) 可以被第三段中的序列( 2 一l 一3 ) 与序列( 2 1 4 ) 连接。因此在网络中我们可以得到从第一段中的一个结点到第以 段中的一个结点的一条路径，这条路径就是一个可能的航班序列，比如给定这样 一条路径( 1 ) 寸( 1 3 ) 专( 1 3 2 ) o ( 3 2 5 ) j ( 2 5 4 ) ，那么我们可以得到对 应的航班序列1 3 2 5 4 。当然网络中有些结点并不包含在一条完整的路径当 中，比如第四段中的结点( 3 4 5 ) ，除去这些结点可以进一步简化网络。 第2 章机场终端区航班着陆调度a l s 的基本方法 表2 1 刀= 5 ，k = 1 时可能的航班分配 位置 l 23 45 l123 4 223 45 可能的航 班分配 345 图2 2n = 5 ，k = 1 的c p s 网络 2 2 3 基于计算智能的方法 遗传算法是目前解决航班着陆调度优化问题常采用的一类计算智能算法，该 算法借鉴了生物遗传学的观点，通过自然选择，遗传，变异等作用机制优化种群， 具有很强的全局优化能力。本小节将重点介绍对航班序列编码的遗传算法。 1 2 第2 章机场终端区航班着陆调度a l s 的基本方法 首先介绍编码方法。对于航班着陆的次序我们采用整数编码，比如对6 架航 班给定一条染色体2 ，3 ，l ，4 ，5 ，6 ，意味着第二架航班优先降落，然后依次是第3 、l 、 4 、5 、6 架航班。整数编码简单直观，类似于旅行商问题中的编码。 然后是选择算子，交叉算子和变异算子的设计。选择算子采用轮盘赌方法， 适应度高的个体被复制到下一代的几率大。交叉算子采用一种改进的两点交叉方 法，即由d a v i s ( 1 9 8 5 ) 提出的o x 算子，通过从一个父代中挑选一个子序列并保 存 图2 3 遗传算法流程图 另一个父代的航班相对次序来构造后代。例如两个父代a ，岛： 第2 章机场终端区航班着陆调度a l s 的基本方法 p l = ( 1234 5l6 ) p 2 = ( 32 l4165 ) 首先我们将两点之间的片段复制到后代中： a l = ( xxi345i ) a 2 = ( x l416i ) 从p 2 中去掉a 。中的3 、4 、5 后得到序列2 、l 、6 ，并将其填入a ，中，即可得到 一个后代： q = ( 2l l3 45 l6 ) 同理另一个后代为： 口= ( 23 1 4l6 1 5 ) 变异算子采用两点交换，在染色体上随机选择两个点并交换顺序。 遗传算法对航班队列的次序进行优化后，可以采用线性规划或是先来先服务 来得到具体的降落时间。遗传算法的流程图如图2 3 所示。 2 2 4 航班着陆调度典型方法的分析 分析以上三种典型的航班着陆调度方法，先来先服务是一种简单公平的方法， 适合于终端区不太拥挤的时候，但当终端区拥挤程度较高时，航班之间存在非常 严重的时间冲突，先来先服务无法很好的利用各种资源，忽略了很多有用信息， 可能造成大量的航班延误。 基于c p s 的线性规划方法主要是针对线性目标函数和线性约束条件进行优 化，它的