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

摘要 摘要 航班着陆调度( 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 ) 是机场终端区空中流量管理 ( a i rt r a 蕊cf l o wm a n a g e m e n t ，a t f m ) 的核心。它旨在为待着陆的航班给出有效的 着陆调度方案，保证这些航班能够安全且经济地着陆。研究终端区航班调度问题 对确保飞行安全和提高飞行效益具有重大的意义。 航班着陆调度是一个典型的组合优化问题，其存在的多约束等复杂性使得这 一问题成为公认的一个难解问题；同时，应用时的调度实时性要求进一步增加了 这一问题的求解难度。目前，业内实际采用的先来先服务调度方案简单快速，但 它无法进一步提高飞行效率，特别是在航班较密集的情况下可能无法给出合理的 调度方案。研究界提出的线性规划算法具有高效性和正确性，但缺乏全局搜索能 力，在很多情况下很难得到最优解或近似最优解。计算智能算法是近年来解决航 班着陆调度问题的一个研究热点，但计算代价过大，特别是在较为繁忙的机场终 端区，需要结合有效的启发式方法才能更好地解决航班着陆调度问题。 本文提出了一种新型的优化调度方法来解决航班着陆调度问题。与以往侧重 于寻找最优解的方法不同，本文兼顾调度的实时性与最优性要求，并将重点放在 达到航班着陆调度的实时性要求上。本文提出的是一种基于元胞自动机的航班着 陆优化调度方法( c e l l u l a ra u t o m a t ab a s e do p t i m i z a t i o n ，c a o ) 。它由三个部分组 成：首先，引入元胞自动机( c e l l u l a ra u t o m a t a ，c a ) 用于模拟航班着陆过程，在 满足约束条件的基础上快速得到一个相对较好的航班着陆序列；接着，设计一个 本地优化方法，来进一步优化航班着陆时间；最后，通过对比设计，给出一个深 度优先搜索算法来进一步优化航班着陆顺序。 在标准数据集o r - l i b r a r y 上的对比实验证实，本文提出的航班着陆调度方法 较其他方法具有更高效快速的优点，可以满足实际航班着陆调度的性能要求。 关键词：航班着陆调度元胞自动机实时深度优先搜索遗传算法 a b s t r a c t 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 nt e r m i n a l a 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 gs c h e d u l i n g s 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 s a 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 ts a f e t ya n di m p r o v i n gf l i g h t b e n e f i t a l si sat y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m , t h ee x i s t e n c eo fs u c h c o m p l e xm u l t i - c o n s t r a i n tm a k e st h i sp r o b l e m a l li n t r a c t a b l e p r o b l e m ；a n dt h e r e a l - t i m er e q u i r e m e n ti n c r e a s e st h ed i f f i c u l t yo ft h es o l v i n gt h i sp r o b l e m w h e nt h e r e a r et o om a n yp l a n e sw a i t i n gf o rl a n d i n g ，f c f sm a yn o tp r o v i d eaf e a s i b l es o l u t i o n 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 ga l g o r i t h m sf o ra d d r e s s i n ga l s p 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 sc o m p u t a t i o n a l i 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 he 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 t c 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 no w i i 增t ol a c ko ft h ea b i l i t yf o rg l o b a l s 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 ep 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 s a 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 dg 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 eah o t t o p i ct or e s o l v ea l su s i n gc i h o w e v e rc 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 t e 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 in 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 o a d d r e s sa l sb e t t e r i nt h i sp a p e r , w ep r o p o s ean o v e la p p r o a c ht oa d d r e s st h ea l sp r o b l e m c o m p a r e dt op r e v i o u ss t u d i e s ，w ep u tm o r ee m p h a s i si nm e e t i n gt h er e q u i r e m e n to f r e a l t i m es c h e d u l i n gr a t h e rt h a ns e c u r i n gag l o b a lo p t i m a ls o l u t i o n o u ra p p r o a c h ， n a m e dc e l l u l a r a u t o m a t a - b a s e do p t i m i z a t i o n ( c a o ) c o n s i s t so ft h r e em a i ns t e p s a t f i r s t ，w ea i mt os e e kac o n s i d e r a b l yg o o da i r c r a f tl a n d i n gs e q u e n c ev i aac e l l u l a r a u t o m a t a ( c a ) m o d e l t h e nt h el a n d i n gs e q u e n c eo b t a i n e db yt h ec am o d e li s f u r t h e rf i n e - t u n e db yas i m p l ey e te f f e c t i v el o c a ls e a r c hp r o c e d u r e a tl a s td e p t hf i r s t s e a r c h i n gi sa p p l i e dt og e n e r a t eb e t t e rs c h e d u l eb a s e do nr e s u l t so fc a e x p e r i m e n t a ls t u d yo nt h es t a n d a r dd a t a b a s ew a sc o n d u c t e dt oc o m p a r et h e c a om e t h o da n ds e v e r a lp o p u l a ra p p r o a c h e si nt h el i t e r a t u r e i tw a so b s e r v e dt h a tt h e c a om e t h o dn o to n l ym a n a g e dt oa t t a i ns o l u t i o n so fh i g h e rq u a l i t y , b u ta l s ow a s m u c hf a s t e r ( i nc p ut i m e ) t h a nt h ec o m p a r e dm e t h o d s t 地m a k e si tp o s s i b l et o a p p l yo u rm e t h o di nr e a l t i m ea i r c r a f tl a n d i n gs c h e d u l i n g k e yw o r d s ：a i r c r a f tl a n d i n gs c h e d u l i n g ，c e l l u l a r - a u t o m a t a ，r e a lt i m e ，g a ，d f s 1 1 1 插图 插图 2 1a l s 模型示意图9 2 2 额外开销和着陆时刻的关系1 0 2 3 先来先服务算法流程图1 2 2 4 改进的先来先服务算法流程图1 3 2 5n = 5 ，k = l 的c p s 网络示意图1 4 2 6 门= 5 ，k = l 的c p s 网络剪枝后示意图1 5 2 7 遗传算法流程示意图1 7 2 8 禁忌表搜索算法流程和生态进化算法流程1 8 3 1 基于元胞自动机的航班着陆调度方法流程图一2 1 3 2 元胞自动机模型应用于航班着陆模型的形式2 3 3 3 元胞自动机中航班的位置以及元胞中包含的航班信息一2 4 3 4 元胞自动机中航班的速度示意图2 5 3 5 元胞自动机中航班的邻居关系示意图2 6 3 6 两种简单规则调度结果示意图3 0 3 7 优化规则对数据组l 、2 、3 的调度结果示意图3 4 3 8 子序列示意图3 5 3 9 本地启发式搜索( 遗传算法) 个体示意图一3 8 3 1 0 交叉操作示意图一3 8 4 1 不同的口和值造成的c a o 结果目标函数值和约束违反数的对比图4 6 4 2 元胞自动机模型在不同下的结果4 7 4 3 第l o 组数据g a 解和d f s 解分布情况5 0 4 4 第1 1 组数据g a 解和d f s 解分布情况5 0 6 5 表格 表格 2 1 以= 5 ，k = l 时可能的航班分配1 4 3 1 加入遗传算法的航班着陆优化算法伪代码4 0 3 2 加入深度优先搜索算法的航班着陆优化算法伪代码4 3 4 1 几种规则结果比较4 8 4 2g a 和d f s 对比实验统计结果一5 1 4 3c a o 方法和以往算法在小样本数据集上的结果对比5 3 4 4 在较大规模数据集上，c a o 方法和s s ，b a 的结果对比5 5 4 6 在限时条件下c a o 方法和以往方法的结果对比5 6 4 7c a o 方法三个阶段的结果自对比5 7 6 7 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作了明确 的说明。 作者签名：么耷彗盘鱼签字日期：渔! 里挈s 生兰皇旦 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 日呸开口保密( 年) 作者签名：么立垒蝈 签字日期：兰l ! 复皇坦兰! 身 导师签名： 签字日期： 俘伏夕 第1 章引言 1 1 研究背景 第1 章引言 随着世界经济的发展，对航空运输的需求也不断增长，这导致飞机数量和飞 行流量急剧增加，空中交通拥堵已成为亟待解决的一个难题。每年因空中交通拥 挤造成的经济损失已经达到了上百亿美元，更重要的是空中交通拥挤严重影响了 空中飞行的安全。空中交通流量管理的研究也受到了国内外广大学者的广泛注 意。在我国，随着国民经济的高速增长，我国民航事业的发展得到了良好的外部 环境。从1 9 9 4 年至今，我国民航的实际航班飞行量年均增长1 6 据国际民航 组织统计，2 0 0 5 年我国航空公司定期航班完成的总周转量达到2 5 7 7 6 5 亿吨公 里，相比2 0 0 4 年增长了1 2 世界排名也由第三上升到仅次于美国、而成为超 过航空强国德国的第二大航空运输大国。随着空中交通运输量的增加，我国原来 的空中交通流量管理方法已经不能满足于日益增长的交通量的需求。 空中交通流量管理源于航空发达国家，其英文为a i rt r a 伍cf l o w m a n a g e m e n t ，简称a t f m 。早在2 0 世纪7 0 年代，由于多种因素致使某一空域 中的空中管制能力无法应付管制局面，在探讨其解决方法的过程中提出了“空中 交通流量控制”( a i rt r a f f i cf l o wc o n t r o l ，a t c ) 的概念。本质上说，a t f m 的目的 是为了安全而有效地使用现有的空域、a t c 的服务和机场能力，并且提供飞机 运作者及时、精确的信息以规划和实施一种经济的空中运输，以尽可能准确地预 报飞行情况而减少延误。从2 0 世纪6 0 、7 0 年代开始，美国、欧洲、日本等国根 据当地特点都建立了覆盖整个区域的空中交通流量管理系统。与之相比，我国目 前的空中交通流量管理还是初步的，粗放的，自动化程度很低；我国的空中交通 流量管理体系还没有完全建立，相关研究工作正处在逐步展开的阶段。 空中交通流量管理可以分为先期流量管理、终端区交通流量管理以及具有寻 径能力的空中流量管理。先期流量管理是在宏观上对交通流量进行管理和调度， 主要研究地面等待策略问题；终端区交通流量管理主要是指在本终端区的范围内 进行飞行前流量控制和实时交通管理，主要研究终端区飞机的着陆排序问题；具 有寻径能力的空中流量管理主要根据各个机场、区域以及航线容量的实时情况和 信息及时动态调整各个航班的起飞时间、航路变化和着陆的时间。 本文研究的航班着陆调度方法属于终端区交通流量管理范畴。终端区交通流 量管理旨在：在确保安全前提下，使到场飞机充分发挥各自的飞行性能，尽量减 少飞机之间的相互影响和飞行延误，提高飞机的正点到达率。目前，处理终端区 第1 章引言 域流量管理的主要措施是对该区域内的飞机进行排序，这样可以高效地为到达的 飞机合理安排着陆顺序。机场终端区是航班从航线飞行到着陆的过渡区，因为涉 及机场容量、空域结构等复杂特性，它成为影响整个空管系统运行效率的一个瓶 颈。因此，作为机场终端区流量管理的核心环节，航班着陆调度优化方法的研究 具有重大意义，能产生很大的应用价值。 在美国、欧洲以及澳大利亚，不少繁忙机场和终端区都使用了航班进港排序 辅助决策系统来配合空管员进行航班着陆调度。以澳大利亚为例，2 0 0 0 年悉尼 奥运会前，悉尼终端管制中心建设了进港排序辅助决策系统( m a e s t r o ) ，该系 统与其使用的空管自动化系统( e u r o e a t ) 相结合，有效地降低了区域和进近雷达管 制员的工作压力，达到了加速进入终端区并降低延误的目的。排序辅助决策系统 不仅使机场附近区域及终端区的空中交通更加有序，提高了管制安全水平，而且 减少了燃油消耗，为航空公司节约了大量的运行成本。然而，我国在机场终端区 航班着陆调度方面基本上还处于人工管制阶段，依靠管制员的个人经验来对待着 陆的航班队列进行适当的调整；相比国外的航班进港排序辅助决策系统，人工管 制不仅效率很低，而且没有充分利用空域和地面的资源。因此，研究航班着陆调 度方法，设计高效的优化调度算法，建立航班进港排序的计算机辅助决策系统对 于我国民航事业的发展是非常必要的( 马正平等，2 0 0 3 ；赵嶷飞和王健，2 0 0 3 ) 。 1 2研究意义 随着世界范围内空中交通流量的快速增长，特别是发达地区的航运活动密度 的急剧增大，不当的航班调度不仅造成了巨大的经济损失，而且会由于航班问的 影响导致不良的连锁反应，使局部甚至全区域的飞行管制陷入混乱。这时，飞行 安全无从保障，航运效益也会受到巨大的损失。这使得很多国家、地区的空管部 门都面临巨大的挑战和压力。据统计，目前欧美航空业因空中拥挤每年损失百亿 美元之多，其中超过2 0 的航班延误损失是由于不当的空管调度造成的。在我国， 由于人口经济区域分布的原因，局部发达地区聚集了大部分的空运流量，如东部 地区的航空业务量超过了全国的9 0 ，仅北京首都机场、上海虹桥机场和广州白 云机场三大机场就集中了我国民航空运量中4 0 的旅客量和5 0 的货物量。正 是由于这种地区分布的不均匀性，导致了航空流量的拥挤以及大量的航班延误和 航线冲突，带来了无法估量的经济损失。保守地估算，我国航空公司每年需要 9 0 亿元的运行成本，而因不正常航班运行导致的年经济损失高达1 8 亿元f 余江， 2 0 0 5 ) 。由此可以看出，如果采用合理的空管方案来调度空中流量，就可以挽回 大量的不必要的损失；并且，有效的空中交通管制可以确保飞行安全。因此采用 2 第1 章引言 先进的交通流量管理方法对我国民航事业的成功发展是必要的。 在空中交通流量管理中，由于机场跑道、空域容量等因素，机场终端区是最 可能造成飞行事故的区域，而我国目前的终端区交通管制缺乏程序化的科学方法 的指导，还是依靠管制员的经验来指导航班的调度。众所周知，人工效率很低， 且处理问题容易受主观因素影响，无法充分利用机场资源。因此，研究机场终端 区的流量管理，形成科学有效的方法体系以指导终端区的流量调度，对解决我国 空中交通管理无法满足需求的状况具有极大的现实意义。而作为终端区交通流量 管理的核心内容之一，航班着陆调度旨在为终端区待着陆的航班给出合理的着陆 顺序和时刻表，在保证飞行安全的同时最小化航班延误损失。总之，对航班着陆 调度方法的研究对整个空中交通流量管理具有重要的意义。 1 3 研究现状 近二十年来，航班着陆调度问题得到了各国学者的关注，相关研究也纷纷开 展起来。目前应用最广泛、最简单的是先来先服务算法( f i r s tc o m ef i r s ts e r v e d f c f s ) 。这种调度方法是目前人工调度环境中管制员使用的方法，它根据各航班 到达终端区的先后顺序来决定航班的着陆顺序，并依据此顺序分配航班着陆时 间。在考虑航班的到达顺序和航班之间着陆的安全间隔的基础上，使各航班在最 接近预计着陆时i 、甘j 的时刻着陆，是先来先服务调度的调度策略。但在终端区较繁 忙时，待着陆航班密集，先来先服务调度方法将难以得到最优调度方案，甚至有 时无法给出一个合理的调度方案。 在终端区较繁忙时，待着陆航班较多，需要不断根据终端区当前的空中交通 情况，合理调度航班的着陆时间。这不但需要航班调度算法具备有效性，同时更 要求该算法具有实时性，以便在尽可能短的时间内得到高效的调度方案，以跟上 空中交通的变化情况。目前，相关的代表性研究工作包括： f r a n kn e u m a n ( 1 9 9 0 ) 总结了航班调度模型，并且提到了受限位置偏移 ( c o n s t r a i n e dp o s i t i o ns h i n i n g ，c p s ) 丰i 时间预付( t i m e a d v a n c em e t h o d ) 两种航班 调度方法。其中受限位置偏移方法包括最优受限位置偏移( o p t i m a lc p s ) 和启发式 受限偏移方法( h e u r i s t i cc p s ) 。 m a g i l l 于1 9 8 7 年提出了时间预付方法( t a ) ，其中称之为负延迟效应。这种 方法只改变每组航班的第一架航班的着陆时间，而保持根据先来先服务得到的航 班队列。第一架飞机通过加速，在预计到达时间之前着陆，其后的所有航班都会 减少相同的延迟，同时会减少相邻航班队列之间的着陆间隙。由于加速需要付出 一定的代价，所以飞机只有在其后的飞机会造成延迟的情况下才会加速。 第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 ) ，只调度 着陆航班，而航班的顺序不能随意改变。这种方法规定某架航班在调度后的位置 是其初始在f c f s 中位置前后一定的范围内。受限位置偏移思想可以大大缩小搜 索空间，加快搜索速度。后来，b a l a k r i s h n a n 和c h a n d r a n ( 2 0 0 6 ) 采用了动态规划 和c p s 结合的方法，在使用d e n v e r 国际机场的实际数据的仿真实验中取得了很 好的效果。 b e a s l e y ( 2 0 0 0 ) 给出了一个航班着陆调度问题的数学模型，该模型综合考虑了 航班延误或提前带来的额外开销。该模型假设开销和延误或提前量成线性关系， 而该模型的约束条件也是线性的。因此，这是一个带线性约束条件的线性目标函 数优化问题，可以用线性规划方法来求解。b e a s l e y 在提出这个模型的同时，也 提出了一种基于混合整数线性规划的树搜索算法，来解决静态航班调度问题。而 由于这也是一个空间搜索问题，b e a s l e y 给出了一种高效的启发式方法来加以解 决。之后，b e a s l e y 又提出了动态调度的模型。在该模型中，每次新出现航班需 要调度的同时会修改之前的己调度方案：考虑到这会带来一系列的额外开销，他 用一个移位惩罚函数来评估这个开销，然后提出了一种采用线性规划算法的解决 方案。 b e a s l e y 提出的模型的最大贡献在于不但考虑了航班延误带来的开销，而且 考虑了航班通过加速来提前着陆带来的额外开销，加上航班间的安全着陆间隔和 航班的着陆时间窗的约束，从而将航班着陆调度问题模型化为一个带约束的复杂 优化问题。在此之后，该模型得到了众多研究者的承认，作为一个被广泛接受的 航班着陆调度问题的标准模型，不断有新的方法被提出以提高调度的效果和算法 的运行速度。 c i e s i e l s k i ( 1 9 9 7 ) 引入遗传算法以解决这个问题。在他的方法中，每架航班的 着陆时间和跑道被编码为基因，采用交叉和变异算子，并利用精英池保存1 0 的最好的个体。其中，通过计算调度方案造成的总着陆耗费来比较个体的优劣； 而为了剔除违反约束的个体，违反约束的个体会导致在总耗费上加上一个比较大 的耗费。实验表明，遗传算法对解决这个组合优化问题比线性规划方法要快得多， 虽然有时无法达到全局收敛、得到最好的调度结果，但是在实时性问题的解决上 比线性规划方法更进了一步。之后，c i e s i e l s k i ( 1 9 9 8 ) 又加入改进，采用了带滑动 窗口的遗传算法来解决，并在悉尼机场的航班数据上进行了验证计算。 r a n d a l l ( 2 0 0 4 ) 弓i 入蚁群算法，将每架飞机的有限可能着陆时刻( 设为整数) 看成 若干条路径，让蚁群在这些路径上不断演化，得到最短路径。 相对近期的研究成果是p i n o l ( 2 0 0 7 ) 弓l 入禁忌表搜索和生态算法来求解航班 着陆调度问题。这两种方法都是遗传算法的变种，也属于启发式随机搜索算法的 4 第1 章引言 范畴。二者采用不同的双亲选择策略，通过过滤相同的着陆顺序的个体来维持群 体的多样性。这为我们将问题分成两个部分来解决提供了直接的技术依据。 总之，航班着陆调度是一个典型的组合优化问题，其存在的多约束等复杂性 使得这一问题成为公认的一个难解问题；同时，应用时的调度实时性要求进一步 增加了这一问题的求解难度。目前，业内实际采用的先来先服务调度方案简单快 速，但它无法进一步提高飞行效率，而且在航班较密集的情况下该算法可能无法 给出合理的调度方案；研究界提出的线性规划算法具有高效性和正确性，但缺乏 全局搜索能力，在很多情况下很难找到最优解：遗传算法、蚁群算法等计算智能 算法是近年来解决航班着陆调度问题的一个研究热点，但计算代价过大，特别是 在较为繁忙的机场终端区，所以它需要结合有效的启发式方法才能更好的解决航 班着陆调度问题。 1 4 主要工作和内容安排 1 4 1 本文的主要工作 本文重点研究机场终端区航班着陆调度问题的快速优化方法。在充分调研现 有航班着陆调度优化方法之后，选择了一种与实际航班着陆调度较为吻合的航班 着陆调度模型，设计了一种基于元胞自动机的航班着陆调度优化算法。实验表明， 该算法能快速得到较优的航班着陆顺序和在此基础上的最优着陆时间。 总之，本文的主要研究工作与特色包括： 1 ) 引入元胞自动机来模拟航班着陆过程，建立了基于元胞自动机的航班着陆调 度模型。其中，特别将航班的着陆时间窗借由元胞状态的速度窗来控制；通 过将终端区映射到一条单行道上来简化航班着陆飞行过程，使元胞自动机的 模拟更加形象。进一步，针对航班着陆调度的特点，设计了可以优化航班着 陆调度的元胞自动机规则。 2 ) 针对航班着陆问题的特点，提出了一个本地优化方法来优化航班着陆时间。 通过将航班着陆序列分成一个个紧密联系的航班子序列，通过整体调整子序 列的方法来优化航班着陆的时间。 3 ) 设计了一个深度优先搜索算法来优化航班着陆顺序。本文设计了一个遗传算 法和一个深度优先搜索算法，在之前步骤的基础上进一步寻优航班着陆顺 序，通过对比实验确定了深度优先搜索作为本文方法的最后一个寻优步骤。 第1 章引言 1 4 2 本文的内容安排 本文内容共分为五章： 第1 章引言。介绍航班着陆调度的研究背景，研究意义和研究现状。 第2 章终端区航班队列调度模型与方法。介绍航班着陆调度模型，并介绍 了以往提出的较经典的方法，特别是针对航班着陆调度模型的现有的各种典型的 调度方法。 第3 章基于元胞自动机的航班着陆优化方法。分三个部分介绍了我们的算 法。首先，介绍如何元胞自动机引入航班着陆优化；然后，介绍用于优化航班着 陆时间的本地优化算法；最后介绍了用于进一步优化航班着陆顺序的算法( 遗传 算法和深度优先算法) 。由于我们的算法是基于元胞自动机的，我们称之为 c e l l u l a ra u t o m a t ab a s e do p t i m i z a t i o n ( c a o ) 。 第4 章实验及结果分析。介绍了验证本文方法的几组实验并分析实验结果， 包括元胞自动机的参数选取实验、不同元胞自动机规则实验、不同后续优化算法 实验以及验证本文方法有效性和实时性的实验。通过参数选取的实验确定其余实 验中使用的元胞自动机参数。通过不同元胞自动机规则对比明确了我们的优化规 则的思路正确性。通过比较遗传算法和确定深度优先搜索算法，确定深度优先搜 索算法作为完整优化算法的组成部分。在和以往算法的结果对比实验中证实了 c a o 的有效性和实时性。在最后，通过对比c a o 三步骤结果，确认了c a o 三 步骤的必要性。 第5 章总结与展望。总结本文的主要贡献，提出两点未来可能的研究方向。 6 第2 章机场终端区航班队列调度模型与方法 第2 章终端区航班队列调度模型与方法 本章首先简要介绍航班着陆调度问题，概括这一问题的特点；之后介绍用于 解决航班着陆调度问题的几种典型方法，包括先来先服务算法、线性规划算法和 启发式搜索算法等；最后对比分析了这些算法。 2 1 航班着陆调度问题 航班着陆调度的目的是：通过调度在终端区的航班的着陆时间，在确保安全 性的前提下，最小化调整航班着陆时间带来的额外开销。本节将简介航班着陆调 度问题的定义，并在其后给出航班着陆调度模型的数学描述。 2 2航班着陆调度定义 航班航行过程中，在机场终端区最容易受到机场拥挤等因素的影响，调度会 导致航班需要通过空中等待或者加速来确定具体的着陆时间并在此时间着陆。在 这个过程中，油耗的增加、顾客的满意度下降等因素会增加额外的开销，给航空 公司等部门造成巨大的经济损失。因此，对终端区进场航班进行合理的排序和管 理，使航班安全有序地着陆，并保证航班着陆的额外开销尽可能小，成为了航班 着陆调度的研究重点。 航班着陆调度问题是终端区交通流量管理的核心内容之一。该调度指的是针 对给定的待着陆航班队列( 其中包含各航班的预计着陆时间和时间窗约束等参 数) ，在满足各种约束条件的同时给出一个合理的调度方案，其中包括队列中每 架航班的着陆时间。这里的约束条件包括航班的着陆时间窗限制和航班之间的最 小着陆间隔限制。 在航班进入机场的空中管铜j ( h t c ) 雷达区域后，它会要求空中管匍j ( h t c ) 为其 分配一个着陆时间，称为广播时间。航班的着陆时间必须控制在一个特定的时间 窗口中，时间窗口由最早着陆时间和最晚着陆时间规定。不同的飞机的时间窗大 小和相对预计着陆时间的偏移是不定的。最早着陆时间和航班的最快速度有关， 航班以最快速度飞行最快能着陆的时刻就是它的最早着陆时间。最晚着陆时间和 飞机的载油量有关，飞机以最省油的方式飞行不断在空中等待直到燃油耗光着陆 的时间就是它的最晚着陆时间。 每架飞机都有一个最经济的飞行速度，称作巡航速度，飞机以这种速度飞行 第2 章机场终端区航班队列调度模型与方法 时额外开销( 燃料耗费等) 最小。一架飞机以巡航速度飞行且不作空中等待就着 陆的着陆时间称为该飞机的最佳着陆时间或目标着陆时间。如果空中管制要求飞 机加速或减速，飞机会产生额外开销( 燃料耗费等) ，这个开销会随着飞机的加 减速幅度增大而增大，表现在航班着陆时间上就是航班的额外开销随航班着陆时 间和最佳着陆时间偏差的增大而增大。 任意一架飞机和这架飞机之后的飞机之间的着陆时间差必须大于一个规定 的最小值( 间隔时间) ，这称作航班着陆的安全间隔约束约束。安全间隔约束是 从空气动力学角度考虑的。( b e a s l e y2 0 0 0 ) 举个例子，一架波音7 4 7 在飞行时会在 尾部产生大量的空气湍流( 尾迹涡) ，如果之后的飞机飞行得过近就会失去气动 稳定性。实际上确实有不少飞机事故被认为是由这种情况产生的( m u l l i n s1 9 9 6 ) 。 所以为了安全方面的原因，波音7 4 7 着陆之后其他的飞机必须要在它着陆之后过 一段时间才能着陆。相对来说，轻型飞机产生的尾迹涡非常小，所以其他飞机在 这种飞机着陆以后很快就可以着陆了。飞机起飞时，因为相同的原因也会需要有 类似的延迟操作。国际民航组织( i c a o ) 依据允许最大起飞重量将飞机分为重型 机、中型机、轻型机，并规定了无风条件下不同类型飞机之间尾流间隔的最低标 准。大型机比如波音7 4 7 自身能够产生很强的尾流，同时也能够承受很强的尾流 而不至于失控。安全间隔不仅和两架航班的机型相关，还和两架航班的相对位置 有关。如果前机是大型机，后机是轻型机，则这两架航班之间的最小时间间隔一 定大于前机是轻型机，后机是大型机的情况。 d e a r ( 1 9 7 6 ) 对航班着陆调度问题做了研究，指出航班调度可以分为静态航班 调度和动态航班调度两种。静态航班调度是指待调度的航班队列是固定不变的， 算法只需要给出最优的调度方案即可，并没有考虑航班到达加入队列以及航班着 陆离开队列的情况；动态航班调度中，待调度的航班队列是随时间的改变而改变 的，每当待调度的航班队列发生变化时，模型需要在原来调度结果的基础上进行 重新优化，并给出新的调度结果。 关于动态优化更新时机的选择，我们可以归纳为事件驱动型，时间驱动型以 及事件、时间混合驱动型。对于事件驱动型，当有新航班到达时，需要对新的队 列进行优化。因为航班到达时间具有随机性，当多架航班同时或连续小时间间隔 从不同航路进入终端区，将导致优化过程短时间连续启动，对优化算法实时性的 设计是一个极大的挑战；对于时间驱动型，以雷达扫描周期6 s ( 或倍数) 为单 位，当雷达信息更新时，启动优化算法，对队列进行优化。相比事件驱动型，时 间驱动型以雷达周期为优化间隔，更加符合管制实际，同时避免了短时间频繁更 新。但有可能雷达信息更新时刻，无新的到达事件发生，这时并没有必要进行优 化操作，反而增加了系统开销；对于事件、时间混合驱动型，以时间驱动型为基 第2 章机场终端区航班队列调度模型与方法 础，在雷达信息更新时，探测是否有新的航班到达事件，如没有，则不进行优化： 反之，则对新的队列进行优化。 2 2 1 航班着陆调度的模型描述 航班的着陆时间必须控制在一个特定的时间窗口中，时间窗口由最早着陆时 e 间和最晚着陆时间规定。不同的飞机的时间窗大小和偏移是不定的。最早着 陆时间巨表示第f 架飞机以最大速度飞行能最早着陆的时间。最晚着陆时间工表 示第i 架飞机以最省油的速度飞行时，飞机的油量能支持其飞行的最长时间之后 的着陆时间。 每架飞机都有一个最经济，最合适的飞行速度，称作巡航速度。一架飞机如 果被调度为最佳着陆时间( 目标着陆时间z ) ，它就能以巡航速度飞行直到着陆。 如果空中管制要求飞机加速或减速，就会产生额外的开销。这个开销会随着飞机 的着陆时间和最佳着陆时间偏差的增大而增大。当飞机在最佳着陆时间之前着 陆，会有一个随着提前着陆时间增加以系数g 线性增加的额外开销，若飞机晚 于最佳着陆时间着陆，会有一个随着延后着陆时间增加以系数忽线性增加的额外 开销。 航班f 和航班之间的最短着陆间隔表示为s ，。图2 1 为该模型的约束示意 图： 航班厂_ 厶 飞+ 卜一 e i t i x i l i 时间窗 航班j 图2 1 航班着陆调度( a l s ) 模型示意图 综合以上所述，航班着陆调度参数定义如下： 尸表示航班数量 9 第2 章机场终端区航班队列调度模型与方法 r 表示航班f 的预计着陆时间 e ，表示航班f 的最早着陆时间 厶表示航班f 的最迟着陆时间 置表示航班f 的调度后着陆时间 s ，表示航班f 和航班，之间的最小时间间隔，航班f 在航班之前着陆时 & 表示航班f 先于预计着陆时间z 着陆的单位成本系数 扛表示航班f 后于预计着陆时间z 着陆的单位成本系数 时间窗约束：由着陆时间窗的规定，航班调度着陆时间必须在区间【巨，厶】 中，这使得航班受调度后着陆时间墨必须要满足如下公式： 互誓厶( f = l d( 2 1 ) 安全间隔约束：每架航班必须与之前的航班保持一定的着陆时间间隔，即每 两架航班f 和的着陆调度时间( 其中f 在7 之前着陆) 之差必须大于规定值，即 x j - 五品o = 1 ，只j = 1 ，只i d ( 2 2 ) 安全间隔约束是为了保证在一架飞机之后着陆的所有飞机都不会受此飞机的尾 迹涡影响，从而保证之后飞机的着陆安全。所以只要是在航班f 之后着陆的所有 航班的着陆时间都必须满足与它的着陆时间的安全间隔约束，而不仅仅是相邻的 航班需要满足此约束。从这点可以看出航班着陆问题的约束数目很可观。 t i 图2 2 额外开销和着陆时刻的关系 航班调度的目的是在符合约束的基础上最小化航班的着陆额外开销。着陆过 程中每架航班的额外开销与航班着陆时间和最佳着陆时间之差( 以下称为着陆偏 l o 第2 章机场终端区航班队列调度模型与方法 移时间) 有关。此开销和着陆偏移时间的关系如图2 2 所示， 销的公式表示如下： ，一j 蜀( 巧一x i ) z 【红( 毛一z ) z 1 ) ( 2 6 ) 黾=+ 墨，岛) ，气) ( = 1 ，一， ) p 一7 i 取下一架飞机 钳 当前航班的降航班降落时间为 落时间定为t i r a i n t i ，) 【( 1 一l ，+ s ( 1 一1 ) ，i ) 否 分段调整队列 降落时间 图2 4 改进的先来先服务算法流程图 基于先来先服务算法，有一些改进被加入其中，比如在航班总队列中选取能 够调整的组，通过调整组头尾航班的着陆时间来提升总体效果，降低航班队列总 着陆耗费，则改进的算法流程如图2 4 所示。 2 4 2 基于c p s 的航班着陆调度方法 c p s 是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 的缩写，意即受限位置偏移。由于可操 作性的限制，航班在着陆调度中在队列中不能作相对于f c f s 顺序的大的移位。 比如，若航班f 在f c f s 队列中的位置为鼻位，则在调度之后的着陆队列中，其 第2 章机场终端区航班队列调度模型与方法 位置必须在区间f 只一七，鼻+ j i 】中。其中j 为受限偏移半径，表示调度后位置的偏 移量的最大值。这样，就可以通过构造一个c p s 网络来穷举可能的航班着陆顺 序，从而来搜索最优的航班着陆调度顺序。( b a l 妇i s h n a n2 0 0 6 ) 表2 1 刀= 5 ，k = l 时可能的航班分配 位置l23 4 5 11234 可能的航 22345 班分配 3 45 如表2 1 所示，k = l 时着陆队列的每个位置可能有最多三个可能的航班。依 靠这样的表就能得到如图2 5 所示的c p s 网络，通过构建这样的网络可以穷举所 有可能的航班着陆顺序。 厂s l a g e l 、厂s l a g e2 、厂s l a g e 3 、，s l a g e 4 、，s l a g e 5 、 1 - 2 - 3 k 1 - 2 4 i 一1 2 - 3i l2 i 一1 2f l 1 - 2 - 5 l - l 1 - 2 4 l l1 l 、2 - 3 5 一一一一 f 乃体s 心 l 、 j 2 4 5一一1 - 孓2 、 1 4 3 、 1 fi 1 - 3 k 。| 嬉f q2 “ 、f1 一弘l 7 7 2 - 卜 、 2 2 _ 1 k j 一2 - 1 - 3 ， n 2 3 5k 抖5 | 、i2 3 kl f 1 2 4 3k 1 州l 厶4 1 5 ltt i | _ 似5 | 2 - 卜 例形 ， n 3 。5 、抖5 图2 5 甩= 5 ，k = 1 的c p s 网络示意图 从图2 5 可以看出，有很多节点是冗余的，它们并不能形成一个有效的着陆 1 4 第2 章机场终端区航班队列调度模型与方法 顺序，如1 2 3 4 ，1 - 2 3 5 等等。这时需要采用剪枝策略剪去不需要的路径，剪 枝完毕的网络如图2 6 所示。 采用c p s 方法可以很容易得到以最大流量为目的的航班调度最优方案。对于航 班偏离最佳着陆时间着陆产生最小额外开销为目的的航班调度，由于依靠着陆顺 序得到最优