空中交通流量管理动态网络流模型及实现算法的研究

南京航空航天大学硕士学位论文摘要随着我国航空运输业的迅速发展，由于气象原因所引起的空中交通延误问题越发严重。目前，当航路受恶劣天气条件影响时，相关部门通常采用地面等待策略对航班进行调配，直到航路容量恢复。因此造成了严重的航班延误和巨大的经济损失。为了缓解这一矛盾，空中交通流量管理中的改航策略正日益受到国内外学者的普遍关注，并已经成为重要的研究课题。本文首先对空中交通流量管理问题进行了归纳与综述，并针对改航问题，较深入地探讨了多任务动态网络流模型和马而可夫天气模型。接着，文章在分析比较了两种已有的多任务动态网络流模型实现算法（拉格朗日乘子法和改进的 A*算法）后，结合人工智能遗传算法，研究提出了一种新的模型求解方法。最后，论文对改航问题进行了系统结构与功能模块的设计，并对多任务动态网络流模型和所提出算法进行了计算机仿真实现，验证了其可行性。关键词：空中交通，战术流量管理，动态网络，改航问题，遗传算法I空中交通流量管理动态网络流模型及实现算法研究AbstractAs the rapid development of air traffic transportation in our nation, the air trafficdelay problem caused by severely weather has become worse and worse. When the airroutes were being affected by the bad weather, we used to impose Ground Holding(GH) to flights until the capacities recovered, complying with enormous loss anddelay. In order to change this situation, more and more work has been devoted on airtraffic reroute problem recently. The Rerouting has become a significant topic aroundthe world now.This thesis first presents a critical review of the air traffic problem. Then it givesa discussion about multi-commodity dynamic network flow model and stationaryMarkov chain weather model. After comparing with the Lagrangian GenerationAlgorithm and A* Algorithm, this article addresses the multi-commodity dynamicnetwork flow model with a Genetic Algorithms (GA).At the rest part of this article, abrief de design for rerouting software are also provided.Keywords: ATFM, Tactical Model, Dynamic Network, Genetic Algorithm, ReroutingII南京航空航天大学硕士学位论文图、表目录图 1.1图 2.1图 2.2图 2.3图 4.1图 4.2图 4.3图 4.4图 4.5表 2.1空中交通流量管理层次图.44个机场、6 个扇区的网络图.12机场模型.13二维马尔可夫模型天气变化图.17改进的遗传算法流程.34系统结构关系示意图.35系统主界面.38优化结果生成界面.38仿真界面.39多任务网络流模型输入参数.13表 2.1 （续）.14表 4.1 Flight 类数据成员描述表 .31表 4.2 Genome 类数据成员描述表 .31表 4.3 GeneAlgrithm 类数据成员描述表 .32V空中交通流量管理动态网络流模型及实现算法研究缩略语AOCARTCCATSATCATCCATFMAVOSSASMGHPSGHPMGHPFAAFCFSTAGAVIAirport Operation CenterAir Route Traffic Control CenterAir Traffic ServiceAir Traffic ControlAir Traffic Command CenterAir Traffic Command CenterAir Traffic Flow ManagementAircraft Vortex Spacing SystemAir System ManagemenGround Holding Program(s)Multiple Ground Holding ProblemFederal Aviation AdministrationFirst Come First ServiceTime-AdvanceGenetic Algorithms机场运行中心空中航路交通管制中心空中交通服务空中管制中心空中交通流量管理飞机尾流间隔标准空域系统管理地面延误程序单机场地面等待问题多机场地面等待问题美国联邦航空局先到先服务时间提前算法遗传算法单机场地面等待问题承诺书本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文。（保密的学位论文在解密后适用本承诺书）作者签名：日期：南京航空航天大学硕士学位论文第一章 绪论1.1 前言近几年来，世界民用航空业正随着世界经济的快速增长而迅猛发展。在我国，空中交通运输量从80年代以来开始大幅度增加，航空运输量更以年平均20%的增长率在迅速增加。根据国际民航组织提供的最新统计信息显示，除去我国香港、澳门和台湾地区的民航空运量，2002年中国民航航空运输总周转量为162亿吨公里，比同期上升17%，在全世界的排名由第六位上升至第五位，如果将香港、澳门和台湾地区的民航业的运输量统计在内，中国在世界的排名仅次于美国，列第二位。然而，伴随着航空运输的飞速发展，我国的空域和机场也开始面临越来越严重的空中交通拥挤问题，并因此造成了较大的经济损失和事故隐患。2004年前5个月，各航空公司航班平均延误率为22.1，比去年同期上升了1个百分点，高于国际上20的行业平均延误率水平。以2004年4月为例, 航班正点率平均仅为77.5%，影响航班正点率的原因中，流量控制（包括航空公司计划不当与天气原因）占66.2。因此，加强空中交通流量管理，大力开展这方面的研究已成为当务之急。1.2 空中交通流量管理空中交通流量管理（Air Traffic Flow Management：ATFM）22本来是作为一种紧急而特殊的程序产生的，但现在随着民航的发展已经成为了一个经常运用的普遍化工具。空中交通流量管理服务的目的是：在需要或预期需要超过空中交通管制（AirTraffic Control：ATC）系统的可用容量期间内，保证空中交通最佳地流向或通过这些区域。空中交通流量管理是空中交通管理的三项内容（ ATS、ATFM、ASM）之一。术语“ATFM”包括组织与处理空中交通流量的各种方法，以此方法进行的任何工作，使得在保证各架航空器安全、有秩序和迅速过程中，任一个给定的点上或任一个给定的区域内所处理的交通总量是与空中交通管制系统的容量相适应。ATFM 支持 ATC 达到其主要目的：防止航空器之间相撞，加快并保持空中交通有序地流动，以及达到可用空间和机场容量最有效率的利用。为此，ATFM服务必须与参与的 ATC 单位以及各类不同的空域用户保持持续的合作与协调。术语“ATC 容量”一词反映 ATC 系统或其任一个子系统或者工作席位，在其正1空中交通流量管理动态网络流模型及实现算法研究常工作期间内向航空器提供服务的能力，并以在一段既定期间内进入某一部分空域的航空器数量来表示。在短时间内可以达到的最大高峰容量可能比能够接受的容量高许多。ATFM 服务的职能主要是以下五方面：（1）收集、整理关于航行基础设施和关于 ATS 的容量以及在该“ATFM”区域内的一些经过选择的机场，包括跑道、滑行和登机门的容量；（2）收集、分析进、出和通过该 ATFM 区域和在其内运行的、已作了计划的全部管制飞行的数据；（3）确定预期的交通需要的一贯局面，包括预期的和特别的交通，与可用容量相比，确认预期出现超出符合的区域和时期；（4）与 ATS 主管当局协调，以便尽一切可能在需要的地方增加可用的 ATS容量。设立国家和地方航班时刻安排委员会（来自国有 ATS、机场主管当局、国内和国际航空器经营者）在研究制定减少高峰需求期间冲突的战略时，可以做出重大贡献。在不能解决 ATC 容量不足问题的场合，要在适当的时间确定并实施适当的战术措施。这些措施要根据需要与遍及 ATFM 的区域的有关航空器/机场运营者协调。空中交通网络的拥挤是由于机场、空域或航路交叉点的容量限制造成的“瓶颈”现象所至，特别在天气情况恶劣的时候，机场容量减小，这种现象更加严重。美国取得执照的民用机场有 566 个，但客运量的 70%发生在 22 个主要机场；在我国北京首都、上海虹桥、浦东和广州白云四个国际机场集中了我国民航约 40%的旅客量和 55%的货运量，这些机场构成了空中交通网的主要“瓶颈”，并导致了全国 90%到 95%的航班延误。同时，随着航空运输业的不断发展，空中交通流量的大幅度增加，“瓶颈”现象、空中交通拥挤现象将越发严重。空中交通流量受到空管系统中的“瓶颈”限制，空管系统中任何约束将成为限制容量的促成因素：现行系统的缺点与系统发展的不协调；雷达数据共享受到限制；最小间隔标准的应用变化很大； ATC 协调程序和不同高度层的应用变得很繁琐；空域使用限制（军方）、机场夜间禁航、降低噪音程序；设备、人员不足，ATC 程序不完善。空中交通的拥挤还有一些外在原因：（1）节假日和公众的旅行习惯，在一年的某些时期内、在一星期的某些时间内和在一天的某些小时内空中交通的积累；（2）各 ATC 系统或系统的某些部分容量受交通积压的影响不同；（3）把可能发生的交通需求（超负荷）一事，通知 ATC 单位的时间提前量不够；2南京航空航天大学硕士学位论文（4）缺少（使经营者可以接受、恢复需求与可用容量平衡的）经过证实的技术和程序。为减少拥挤，适 应空中交通发展的需要，空中交通流量管理针对这些矛盾提出了解决方法，概括起来主要包括如下几种：（1）长期法（从概念到实现一般要 15 年左右）：包括建造更多的机场，增加机场的跑道数量，改善硬件设备环境，提高空中交通管制技术，如 ICAO 提出的未来新航行系统。但是这些都需要大量的资金，周期长，见效慢。（2）中期法（从概念到实现一般要 6 个月到几年）：包括增加空中航线，修改空域结构等。这些方法使得空中交通网络的飞行流量从宏观上更加合理，能更加有效的利用空域，相比之下也更加经济。（3）近期法：该法通过采用地面等待、空中等待、修改飞行计划等策略直接对空中交通流量进行控制，使得空中交通流量与空域、机场的容量相匹配，从而减少拥挤。流量管理程序应分三个阶段执行：（1）战略流量管理（strategic planning），在行动生效之日七天以前执行的措施。战略规划一般会提前进行，通常在二到六个月之前；战略规划应由 ATC和航空器经营人共同完成。它应包括对下一季节的需求进行审议，评估何处或何时需求可能会超出 ATC 提供的容量，并采取如下措施解决不平衡：a) 与 ATC 当局达成共识，在要求的地点和时间提供足够的容量；b) 改变某些交通流量的航向（交通流向）；c) 适当时安排或重新安排航班时刻；d) 确定战术 ATFM 措施的必要性。（2）预战术流量管理（pre-tactical planning），在行动生效之日前一天至七天采取的措施；预战术规划须根据更新的需求数据对战略规划进行细致的调整。在此阶段：a) 必须审议交通流向；b) 对低负荷航路协调；c) 商定战术管制措施；d) 商定调整飞行计划；e) 向有关方面公布次日的 AFTM 计划细节。（3）战术运行（tactical operations），在行动生效前 2 小时至 24 小时采取的措施；战术管制包括：a) 执行协商一致的战术管制措施，特别是航空器地面延误所适用的时段分配程序，以便能降低交通和使其均衡流动，若非如此需求会超出容量；3空中交通流量管理动态网络流模型及实现算法研究b) 监视 ATFM 状况的变化，确保采用的措施达到预期的效果。当报告有长时间延误时，采取或开始实施改正行动，包括改变交通的航向和飞行高度层的分配；c) 灵活使用空域，减轻拥挤；d) 合理安排飞机着陆次序，最大限度地使用 ATC 容量。下图是空中交通流量管理的层次图。系统计划（包括航路结构、ATC 程序等）航班时刻计划的制定战略流量管理预战术流量管理战术流量管理5 年6 个月7 天24 小时2 小时时间图空中交通流量管理层次图在上面介绍的三种流量管理方法中，由于前两种方法实施周期较长，投入多，见效慢，所以在实际空中交通流量管理中往往采用第三种方法，这也就是本论文所要讨论的空中交通流量管理方法。其中地面等待策略是最为经济有效的一种途径。地面等待（也称为：入口等待，地面停止）典型应用于那些飞往拥挤的机场或穿越拥挤空域上空的飞机上。地面等待就是指飞机不按预定时刻起飞而延迟起飞的一种方法。这样做的原因是在延误不可避免的前提下，地面等待比空中等待更安全经济。而地面等待策略就是如何确定航班的最优起飞时间，通过地面等待来调节空中交通网络的流量，并使航班的流量与机场、空域的容量大体匹配，减少延误时间，从而减少经济损失，提高机场、空域的利用率，保证飞行的安全与准时。终端区交通流量管理是指在本终端区的范围内进行空中流量的管理，主要处4南京航空航天大学硕士学位论文理机场及其走廊口区域，飞机的到达和出发流量的排序规划问题。根据机场的跑道数量和运行构型，在不违反飞机安全间隔的情况下，采取优化的调度策略，改善现有机场的容量，科学，合理地安排飞机的着陆和起飞次序，以及起飞比例，保证空中和机场地面交通快速，有序地流动，有效缓解机场交通阻塞的现象。在确保安全前提下使到场飞机充分发挥各自的飞行性能，尽量减少飞机之间的相互影响和飞行延误，提高飞机的正点到达率。对终端内的飞机进行排序，可以高效地为到达的飞机合理安排着陆的次序。其主要功能是：（1）监控终端区内，机场跑道和进出走廊口的交通流量状况；（2）预测终端区的流量分布；（3）预测机场跑道和进出走廊口飞机延误的数量和时间；（4）为管制部门提供管理飞机进出港的优化调度策略。由于天气或其他原因等,各个起飞机场,降落机场以及各个区域和航线的容量往往不是确定的而是动态变化的。地面等待策略和终端区飞机排序策略并不能很好解决这样的空中流量管理问题。因此有些学者通过建立模型，采用改航解决动态的空中交通流量管理问题。1.3 国内外研究现状国外关于空中交通流量管理（ATFM）的研究自20世纪80年代中期以来就非常活跃，在理论方面和实际应用方面都取得了重要成果。1987年，Odoni首次对空中交通流量管理问题作了系统描述，提出了战术管制和战略管理两种流量管理模式1。进入20世纪90年代以来，美国和欧洲根据本国、本地区的特点，利用先进、科学的流量管理方法，陆续建立了各自的流量管理中心。这不仅对空中交通流量的协调、控制和管理起到了重要作用，而且还大大提高了空域利用率，减轻了管制员负担，加速了空中交通流量，增加了飞行安全水平。1990年，Terrab和Odoni完整地对单机场地面等待策略问题进行了研究， 1992年Peter B.Vranas和Odoni等人发表的“The Multi-Airpot Groud-Holding Problem in Air Traffic Control”论述了多机场地面等待策略问题；1994年，Varanas等人研究了地面等待策略的实时性问题和多机场受限的地面等待策略问题，Dimitris Bertsimas 和S. Stock研究了航路容量受限的流量管理问题“The air traffic flow management problem withenroute capacities”2。在理论研究的基础上，美国已经把地面等待策略应用于实际的空中交通流量管理，取得了很好的效果。美国麻省理工学院的Sarah StockPatterson 于 1997 年 5 月 发 表 的 “Dynamic Flow Management Problem in AirTransportation”一文中用了大量篇幅介绍空中交通流量管理中的改航问题，并提出了解决此问题的拉格朗日生成算法（Lagrangian Generation Algorithm）9。美5空中交通流量管理动态网络流模型及实现算法研究国Neuman F，Erzberger H发表的“Analysis of sequencing and scheduling methodsfor arrival traffic”分析了到达航班的排序问题。 Sofiane Oussedik 和 DanielDelahaye发表的“Air Traffic Management by Stochastic Optimization”以遗传算法为例介绍了通过随机优化的方法进行全局性流量管理的问题。2004年Jimmy Krozel,Joseph Prete 发表的Comparison of Algorithms for Synthesizing Weather AvoidanceRoutes in Transition Airspace10分析比较了受天气影响的终端区改航算法问题，但国外这些研究和成果并未形成空中交通流量管理的统一模式，也不一定完全适合我国的实际情况，因而有其一定的局限性。国内关于空中交通流量管理问题的研究起步较晚，近几年来随着空中交通流量的急剧增加，流量问题开始显得异常突出，并引起了国内空管部门和民航院所的极大重视。相关单位开始展开了一系列研究工作。华北管理局1988年曾对北京空中交通流量问题进行了初步研究；民航一所1996年开始进行空中交通流量统计方面的研究。在借鉴国外的理论模型和应用系统的基础上，中国民航学院的研究则以开发适合我国管制实际的流量管理试验、应用系统为主。中国民航飞行学院、四川大学、西北工业大学和西南交通大学研究的重点则集中在流量管理的理论模型上，尤其是GDP,航空器进场排序算法的方面。清华大学结合“空中交通管制指挥监测系统”的开发，提出了管制区级的短期流量管理模型。南京航空航天大学民航学院从1993年以来一直把空中交通流量管理问题列为研究的主要方向，几年来进行了一系列卓有成效的研究。胡明华教授及其学生结合我国的实际情况，对空域评估模型进行了比较细致的研究。陈爱民对地面等待问题27，宋柯对改航问题26，李丹阳对终端区动态排序问题进行了有价值、有深度的研究。张颖结合广州地区流量状况开发出了广州地区空中交通流量管理策略生成系统28。1.4 本文主要研究内容本文主要对空中交通流量管理动态网络流模型及其实现算法进行了研究，全文的内容安排如下：第一章 绪论本章介绍了课题的研究背景和研究意义，对国内外交通流量管理问题的内容目的及意义进行了综述，总结归纳了现今的流量管理的研究方向，并简述了本文的主要工作。第二章 空中交通流量管理动态网络流模型本章首先对空中交通流量管理问题进行了分析与研究，包括地面等待问题、终端区排序问题、改航问题。然后针对我国的具体情况，选择研究了空中交通流量管理中的改航问题进行了深层次的研究，并对改航问题的典型模型 多任务6南京航空航天大学硕士学位论文动态网络流模型以及产生改航的主要原因（天气问题）进行了建模。第三章 多任务动态网络流模型解决算法在第二章建模的基础上，本章主要介绍了求解动态网络流模型的两种已有算法 拉格朗日乘子法和改进的 A*算法，并对两种算法的利弊进行了分析。然后，从实际效率的角度考虑，研究提出了人工智能的遗传算法来对模型进行的求解。第四章 系统设计与实现本章首先介绍了改进的遗传算法在求解拉格朗日模型时的主要求解步骤与流程，然后对整个改航系统进行了功能与结构的设计，给出了系统的结构图。最后，介绍了整个系统的开发工具，并给出了系统已完成部分的界面截图。第五章 结束语本章首先介绍了本文主要的工作内容以及创新点，然后对改航研究的进一步研究进行了的展望。7空中交通流量管理动态网络流模型及实现算法研究第二章 空中交通流量管理动态网络流模型本章首先对空中交通流量管理问题进行了分析与研究，然后对空中交通流量管理中的改航问题以及产生改航的主要原因（天气问题）进行了建模。2.1 空中交通流量管理问题分析与研究在现今的空中交通管理体系中，空中交通战术流量管理的方法主要包括地面等待，终端区排序和改航策略。2.1.1 地面等待问题地面等待问题（GHP）27是在满足空域系统可用容量的条件下，通过合理分配航班的地面等待时间，使系统的延误损失降到最低。地面等待问题典型应用于那些飞往拥挤机场或穿越拥挤空域的飞行场合，即不按预定时刻起飞而延迟起飞的一种方法。原因是在延误不可避免的前提下，地面等待比空中耗时更安全经济。其等待时间是指飞机从预计起飞时间到得到管制员的允许从跑道滑跑起飞时间的差值。从本质上说这是一种主动的流量管理方法，因为管制员通过其他途径（如通讯、天气预报）得知即将安排起飞的飞机将要“赶”上拥挤的区域，于是飞机在地面等待一段时间后起飞可以避开拥挤时段。如果说地面等待对突发事件（如暴风雨）的处理具有的意义不大，那么对于那些非突发拥挤（指每天的高峰时段），由于这种冲突几乎每天都发生，就完全可以根据航班沿途区域和目的机场的评估容量，从航班时刻的角度出发修改航班的预计起飞时间。根据决策制定时间的早晚地面等待问题分为静态和动态两个类型。所谓静态，是指在每次求解模型前所有的决策都是提前做好的，比如每段时间 (一般是一天)内的计划到场航班数、所有航班在起飞和降落机场之间的飞行时间等都是已知和给定的；而动态则是指相关决策是不断更新的。根据机场容量是否已知确定地面等待问题可分为确定型和随机型。在地面等待策略研究中，空中交通的操作请求和机场容量的之间的矛盾是问题的关键所在。其中操作请求由各个航班所确定，所以通常是可以预测的；而机场容量，由于天气等客观不确定因素，却是变化迅速不易预测和确定的。根据对象机场的多少，我们可以将地面等待问题分为单机场地面等待问题(SGHP)和多机场地面等待问题(MGHP)。单机场地面等待问题考虑的对象仅仅是目标机场，但整个问题的处理过程肯定至少要涉及两个机场。地面等待问题的研究初期，研究对象几乎都是单机场，而关于单机场地面等待问题的研究往往忽略8南京航空航天大学硕士学位论文了模型的网络或回路(down-theroad)效应，所以多机场地面等待问题随即产生。根据系统驱动模式的不同，地面等待问题可分为时间驱动型和事件驱动型。所谓时间驱动型是指，将所研究的时间段等分为多个小的时间区间，然后分别在这些区间上研究分析航班的地面等待情况，大多数线性规划和动态规划都采用这种时间驱动模式；事件驱动型是指，将所研究系统看作是一个离散事件动态系统(DEDS)，把航班的起飞、到场和着陆视为输入事件，相应的时刻作为系统的服务时间。2.1.2 终端区排序问题终端区排序问题主要处理机场及其走廊口区域，航班的到达流的排序规划问题。在终端区，机场的流量管理是相当复杂的，也是非常重要的一环。首先机场情况十分复杂，很难给出具有普遍意义的考虑。因为不同机场有着不同的特点。有的是大型国际机场，有的是地区性的机场，有的是中心机场而有的更小。在机场地面面积上，跑道数量和结构上等等不同机场都是不同的。同时不同机场的自动化程度和信息系统，以及旅客所能利用的设施以及航空公司等都是不一样的。终端区到达飞机排序算法主要包括先到先服务（FCFS）算法、约束位置交换（CPS）算法时间提前（TimeAdvance）算法、延误交换算法、动态尾流间隔算法和滑动排序窗算法。29 31先到先服务算法依靠飞机预计到达时间（ETA）的次序来决定飞机的着陆次序。当需要着陆的飞机进入终端区排序区域时，系统根据飞机进入终端区的时间、飞机的性能数据和初始状态计算出飞机到达目标点的 ETA，系统根据飞机的 ETA和当前飞机队列的排序情况给出相应的飞机的计划到达时间（STA）。如果飞机对中的间隔不足以插入新的着陆飞机，系统在保证飞机间隔标准的前提下，对这架飞机后面的飞机依次重排，进行延迟处理。如果对后面的飞机不能进行重排和延迟操作，就要对这架新到的飞机实施等待策略，使其在某一固定空域进行空中等待。约束位置交换算法从不同类型飞机必须保持不同的“最小安全间隔标准 ”入手，通过对飞机队列次序的重新排列，对所有可能的飞机排序方式进行搜寻，找到一种成本（指队列中每两架飞机之间所需时间间隔的总和或以等待时间为参数的每架飞机的等待成本的总和）最小的排队次序，即该组飞机的最佳排序方案。但得到的最佳排序方案有可能会使原飞机队列的次序改变较大，这不仅加剧了管制员的负担，而且与先到先服务原则冲突较大，降低了不同航班飞机的公平性，从而增大了实现的难度。因此带约束的位置交换被提出，即飞机的最终位置只能被排在初始位置前后一定范围内的适当位置上。位置约束是通过在算法中对待排序飞机初始位置与最终优化位置之间的差值进行限定来实现的。CPS 算法通常只9空中交通流量管理动态网络流模型及实现算法研究能使相邻位置间的飞机进行交换。时间提前算法对每个飞机队列的第一架飞机实施控制，而不改变整个队列的原有顺序。通过使第一架飞机加速，使其先于正常的预计到达时间到达目标点。这样，队列中后面的所有飞机都可以减少相同时间的延误。这种方法同时也减少了不同飞机队列之间的间隔。一般情况下，所有飞机的最大时间提前量为 60 秒；而在 CTAS 系统中，每个飞机队列的首架飞机的时间提前量是根据系统的计算结果而定。因为 TA 算法对于加速飞机来说是以提高飞行成本为代价的，所以只有当紧跟第一架飞机之后的飞机需要延迟处理时，前者才进行加速从而使后者的延误减少。TA 对多数飞机来说使其减少了延误和燃油消耗，但那些加速的飞机不是按照飞机的最优巡航和下降剖面飞行，其燃油消耗是增加的。所以，采用 TA算法时，要综合考虑多方面的因素。延误交换算法是一种基于公平原则的排序方法。在机场运行高峰时，等待着陆的大量飞机需要延迟处理，这种方法会接受某个航空公司提出对其公司在等待队列中的某架飞机实施提前着陆的请求，同时对此公司在等待队列中的另一架飞机实施延误处理。航空公司做出延误交换决定，延误交换需考虑以下因素：机组成员的状态、乘客的连续性（对下一航班的转机要求）、重要航班的往返时间、准点要求、油料情况及跑道情况。动态尾流间隔算法是 NASA Langley 研究中心正在研究一种能提供动态尾迹涡流间隔标准的系统，它通过预测多种气流条件下涡流的衰减和转移情况来实现 。 这 种 系 统 被 称 作 飞 机 尾 流 间 隔 系 统 （ Aircraft Vortex SpacingSystem AVOSS）。AVOSS 通过把天气和尾流长度作为输入，对尾迹涡流的衰减和转移情况进行建模。尾迹涡流模型用来确定在考虑尾流效应影响情况下，前后飞机的飞行间隔。AVOSS 的输出将是对于不同飞机组合的时变间隔约束。例如，波音 747 与前面的 DC10 的间隔是 95 秒。由于不断变化的间隔标准将影响空域内所有的飞机，所以系统的稳定性必须加以考虑。在这里，稳定性是指通过对将要着陆的飞机的调整能将产生的延误尽量 “消化”掉，而不影响空域内的其它飞机，这会使管制员不断的改变对飞机的管制安排。排序窗算法的理论根据在于：优化排序的过程就是对原有的飞机队列进行重排，重新确定每架飞机在新队列中的位置。在确定新队列的某个或某些位置时，由于约束交换范围的限制，并不需要对由整个队列所有飞机所产生的所有可能的排序进行搜索，只需挑出那些与所要确定的位置相关的飞机，然后对由它们产生的可能排序进行搜索，就可找到所需要的优化排序结果。2.1.3 改航问题改航策略是空中交通流量管理的一个非常重要的组成部分，它研究的是由于10南京航空航天大学硕士学位论文种种原因(主要是恶劣天气、导航设备失效)而使机场、空域容量下降的条件下如何组织航班的放飞以及如何为每架航班动态的选择临时航路以避开容量限制区域，以使产生的总损失最小的问题。它的主要目标就是考虑在非正常条件下怎样把经济损失降到最低。国外不少管制机构和学者已对此问题进行过研究。在美国，空中交通管制单位集中于22个区域管制中心。这些中心接收来自于飞机和雷达传来的关于飞机位置、高度、速度和天气等信息.当天气情况恶劣时，全国范围内一些机场或区域的容量显著减少甚至降低为零。在这种情况下，空中交通指挥中心 (ATCC)执行一系列措施来重新安排航班时刻及改航，以便将由天气所引起的延误损失降至最低点。若飞机原计划要经过容量减少的区域，那么它就必须改航。目前，改航决定由ATCC和航空公司运行中心 (AOC)之间的协调措施来完成。 ATCC就改航的必要性与各航空公司的 AOC联系。每个AOC根据新的有限容量条件的信息来制定他们所能接受的新的航班路线，以便完成他们的计划航班。1997年，麻省理工学院的SarahStock Patterson在其著作“Dynamic Flow Management Problems in AirTransportation”中对改航策略进行了深入细致的分析，建立了针对此问题的数学模型，并以拉格朗日松弛算法对该模型进行求解，最后借助大型计算机完成了优化运算得出了优化结果.虽然该理论在与实际相结合方面和实现方面都存在一定的不足之处，但是它确实提出了不少开创性的思路，对随后学者所做的研究工作具有极大的启发意义。我国在实际操作上，无论是机场塔台还是区调管制部门，在遇到航路受恶劣天气条件影响时，都只有让航班做地面等待直到预定航路恢复容量，随之而来必然是带来严重的航班延误。而实际上只要安排这些航班临时选择一条不受天气影响的航路，绕过恶劣天气影响区，以少量的空中飞行时间，便可换取大量的地面等待时间，从而产生可观的经济效益。国内改航问题相关的研究也相对较少，2002年南京航空航天大学民航学院研究生宋柯针对我国的空中交通流量管理改航策略进行了初步研究。宋柯将动态改航问题的核心转换为求解动态网络流的最短路径问题，并尝试引入A*算法对改航问题进行求解，取得了一定的成果。然而，随着我国空中交通流量的快速增长，由于航路恶劣天气造成的航班延误正大幅度的提升。因此，针对我国空域的具体情况，对空中交通改航问题的进一步研究，争取早日应用于实际操作，从而减少可避免的大量经济损失，已成为一个重要的课题。2.2 多任务动态网络流建模恶劣天气是造成航班改航的重要因素，所以本节在介绍了多任务动态网络流11空中交通流量管理动态网络流模型及实现算法研究模型后，建立了马尔可夫天气模型，作为动态网络流的天气约束条件。2.2.1 多任务动态网络流模型多任务动态网络流模型是由DIMITRIS BERTSIMAS 所创建。该模型由动态网络、汇聚流变量、非汇聚变量和容量约束几部分组成。下文将对每部分进行说明。首先介绍一下用于模拟空中交通系统的动态网络。机场 /空域的抽象地理位置如图2.1所示（4个机场和6个扇区），图中的节点代表机场和扇区。通过该图，可以简单了解网络节点及弧的构造方式。图个机场、个扇区的网络图图2.1中，实线代表扇区，星号代表扇区的进出点，圆圈代表机场。每个扇区都包含有限的扇区交叉点。弧线连接扇区的进出点、交叉点和机场。每条弧线( i, j)都有相应的飞行时间 ti,j。为了表示空中延迟，在网络中特意定义了一单位时间的自环飞行。网络的中的运输任务定义为起降机场对。所以如果有A个机场起飞飞行的航班的话，那么就共有A (A-1)个运输任务。这样就可以把所有在同一个起飞降落机场对之间起降的飞机归为同一个任务。然而，如果想进一步区分属于同一任务的不同航班（如，根据机型或所属航空公司），则需要分解这些任务。为了模拟航班流量在机场中的流动过程，必须建立适合的机场模型。通过4个节点iA、iB、iC、iD可以建立了一个简单机场的运行模型，如图2.2所示：12南京航空航天大学硕士学位论文图机场模型节点 iA 用以表示所有进场航班。只要有航班在此机场降落，它必须首先到达节点 iA 。然后它可以到节点 iB 或节点 iC 。到达节点 iB 的飞机表示该航班已经完成当天所有的飞行计划，而且没有后续航班。因此，流入节点 iB 的流量在以后的时间中将被从网络中扣除。到达节点 iC 的飞机表示该飞机当天至少还要飞行一次，也就是还有后续航班。因为运输任务是根据起降机场对来定义的，所以进出同一机场的航班都会被定义不同的任务。在节点 iC ，航班任务应保持进出平衡。iC 的延迟弧(自环)表示该航班在其后续航班计划离场时间之前到达机场，因而不得不在机场作等待直到计划离场时间。在这之后，流量从 iC 流向 iD 。在节点 iD ，新航班被引入网络，所有出港航班都从该节点起飞。该点的延迟弧(自环)表示航班的地面等待。下面用 N = (S , ) 表示航空网络（由机场和扇区组成的网络），用1 , ,A(A-1) 表示任务集，其中A表示机场个数。将全天可用飞行时间分隔成一个时间集 =1 , , T)，用时间片t来表示其中特定的时刻。将一次航班任务理解为飞机完成在两个机场之间的起降。一架航班是另一架航班的“后续航班”是指该航班必须在它的前继航班完成飞行任务后才能开始执行它的飞行任务。该问题的输入参数如表2.1所示：表多任务网络流模型输入参数13ti,j沿弧(i,j)的最小飞行时间Ci(t)t时刻，扇区i的容量r(i)在机场i，加燃油、装载和清理航空器的中转时间orig(k)任务k的起飞机场dest(k)任务k的目标机场N(k)运送任务k可用的弧线集航班集空中交通流量管理动态网络流模型及实现算法研究表（续）为降低问题的复杂度，在此整合了飞行中的一些变量，并定义：xik, j (t ) 为在t时刻从节点i起飞，经过时间 tij 到达j的运送任务k的航班数量。请注意这些变量是合成流变量，而非航班变量。所以为了选取可行的飞行路线，必须分解这些变量。例如，将合成流量变量转换成航班变量。在3.2节中，将应用随机方案实现分解。对于后续航班，模型也引入发散航班变量：yf1，如果航空器完成航班f l ，并在时间t Tf准备起飞0，其它情况由于定义了这些非合成变量，所以有必要增加附加约束以保证每一个后续航班 f C 在某一时刻必须有飞机可供其使用。定义这些非合成变量是为了确保能将任务转化为后续航班。虽然也有其它转换方法，但要在公式中引入大量的约束。而这种方法只需要求增加| C |约束。本问题的目标是使所有航班的总延误损失最小。航班可能由于地面等待，或是空中减速，或是选择了一条比预计航路长的航路而延误。此外一个后续航班也可能因为在预计起飞时间没有飞机可用而延误。所以，目标函数表示如下：k t i g() cgxikD ,iD (t ) +( k , t, f ) : f l ,k( f ) = k , tTf f f i ,ia k k ,i ,t k , t( i , )N (k )a（2-1）第一部分表示由地面等待引起的损失；第二部分表示后续航班因没有飞机可用而产生的延误损失；第三部分表示由于减速引起的空中延误损失；剩下的是由于航班该行而引起的延误损失，它等于空中飞行总的实际费用减去所有空中飞行的预计费用。第四部分给出了空中飞行中的实际总费用；第五部分表示所有空中14df航班集内航班f的预定起飞时间gc航空器在地面等待一个单位时间所需的费用ac航空器飞行一个单位时间的平均费用H所有航班的总飞行时间l航空器在地面等待一个单位时间所需的费用Tf后续航班集中航班f的可行离场时间集k ( f )航班集中航班f的任务k ( f )航班集中航班f前的任务Supk(t)在预定起飞时间t，任务k的航班数量（非后续航班）Demk(t)在最迟着陆时间t，任务k的航班数量（无后续航班）(t ) = (t d ) y (t ) + c x (t ) + c ati, j ix ,k j ( t ) c H, , =o r i k, j南京航空航天大学硕士学位论文飞行的预计费用。以下是约束条件： j:(i , j )N ( k )k j:(j ,i )N ( k )k（2-2） j:(j ,i A )N ( k )k k k（2-3）xikA ,iB (t ) + xikB ,i B (t -1) xikB ,i B (t ) = Demk (t ) , k, i, t = dest (k )k k kf f l :k=k t （2-4）（2-5）N kki D , jy f ( t) - xikD Di, (t -1) = Supk (t ) , k, i, t = orig (k ) （2-6）kx k j (t) Ci (t ) , i, t（2-7）tT fy f (t ) = 1, f l（2-8）xik, j (t) 0,整数i, j ,k ,ty f (t ) 0,1，f , t.（2-9）（2-10）约束（2-2）表示扇区内动态流量的守恒。对每个扇区节点 i ，任务 k 和时间 t 都有一个约束。约束（2-3）、（2-4）、（2-5）、（2-6）表示在节点 iA、iB、iC、iD 处的流量守恒。约束（2-3）表示在机场 i 节点 iA 处的流量守恒。在节点 iA 处，计算所有来自扇区 j、带有任务 k、到达机场 i 的节点的流量，可由 j :(j ,i A) N (k) xkj ,i A (t t j ,iA ) 得到。其中，t-tj,iA 表示流量从 j 流出，在 t 时刻到达机场 i 所用的时间。这些流量必须和 t 时刻从 iA 流出的流量相等，之后将会流向节点 iB（