空中交通流量管理改航策略初步研究

空中交通流量管理再寻径策略初步研究1.1空中交通流量管理概述一、绪论随着日益增长的旅客吞吐量和飞行运行总架次，我国空中交通系统面临着越来越严重的航线拥挤;此外，恶劣天气、导航设备故障也必然导致容量资源严重不足。由此产生的航班延误、改期、备降及油料消耗等己造成严重的经济损失。在这种形势下，空中交通流量管理的重要性更加突出。空中交通流量管理实际上就是在对现有机场、空域、航路容量的准确评估的基础上施用各种策略，合理地组织放飞、调配流量，使流量需求和容量资源能得到最佳的耦合。1.1空中交通流量管理概述一、绪论为减少拥挤，适应空中交通发展的需要，空中交通流量管理针对这些矛盾提出了解决方法，概括起来主要包括如下几种:长期法，中期法，近期法。其中近期法是通过采用地面等待、空中等待、修改飞行计划等策略直接对空中交通流量进行控制，使得空中交通流量与空域、机场的容量相匹配，从而减少拥挤。1.2再寻径策略研究的主要内容一、绪论再寻径策略是空中交通流量管理的一个重要组成部分，它研究的是由于种种原因(主要是恶劣天气、导航设备失效)而使机场、空域容量下降的条件下如何组织航班的放飞以及如何为每架航班动态的选择临时航路以避开容量限制区域，以使产生的总损失最小的问题。它的主要目标就是考虑在非正常条件下怎样把经济损失降到最低。在航路受恶劣天气条件影响时，如果只让航班做地面等待直到预定航路恢复容量，随之而来必然是带来严重的航班延误。而实际上只要安排这些航班临时选择一条不受天气影响的航路，绕过恶劣天气影响区，以少量的空中飞行时间，换取大量的地面等待时间。这样便可产生可观的经济效益，而且还可提高飞行安全水平。1.2再寻径策略研究的主要内容一、绪论1997年，麻省理工学院的SarahStockPatterson在其著作“DynamicFlowManagementProblemsInAirTransportation”中对改航策略进行了深入细致的分析，建立了针对此问题的数学模型，并以拉格朗日松弛算法对该模型进行求解，最后借助大型计算机完成了优化运算得出了优化结果。但是该理论和模型是以做大量简化抽象为代价的，使得该方法与空管工作的实际有较大出入，而且用计算机实现起来非常困难，如果完全按照这种方法来实际解决再寻径问题，无法得到实际最优解(或者近似最优解)，甚至连飞行安全都无法得到保证。虽然拉格朗日乘子法解决再寻径策略问题与实际相结合方面存在一定的不足之处，但是它确实提出了不少开创性1.2再寻径策略研究的主要内容一、绪论的思路，对随后学者所做的研究工作具有极大的启发意义。基于拉格朗日乘子法解决再寻径问题有诸多缺陷和难点，故改用动态网络流问题求解再寻径策略问题，它的理论核心部分是阐述用在人工智能领域取得突出成果的A*算法来求解动态网络的最短路问题，以及怎样把这套方法运用于动态航路网络中以实现再寻径策略的基本目标。2.1总体思路二、动态网络中运用A*算法解决改航问题再寻径问题的核心是动态网络的最短路问题，它的目标是要规划所有航班的飞行方案，使总损失值达到最小。如果仅对单一航班而言，要使它的损失值最小，只要让它尽可能早的起飞，飞行尽可能短的航路就可以了。但是对所有航班这个集合而言，这样做的结果并不是最佳方案，因为不同类型的飞机对容量资源的占用所产生的经济效益不一样，只有让经济效益高的飞机优先占用容量资源才能最大限度的降低损失。然而，对于而恶劣天气、导航设备失效等突发事件无法事先调整航班时刻表，而且更改起飞时间会涉及到不同航空公司间的利益，所以安排航班起飞最早不能早于其预定起飞时间。2.1总体思路二、动态网络中运用A*算法解决改航问题另外，在实际操作上，由于要符合各种空管习惯和规定以及要兼顾总体利益和各航空公司的个体利益，在这样的前提下做优化，其结果只能是一个为各方所能接受的近似最优方案。所以改航问题的重点应该放在如何寻求一种公平、合理和具有明显经济效益的方案，而不是一味在数学上讨论最优解的理论值应该是多少。综上所述，可以从以下两方面入手来解决改航问题:1)按对空域资源的占用/产出比的高低以及其它各种实际影响因素综合考虑来安排各种航班的放飞顺序.2)研究如何把应用于静态网络的求最短路的方法应用于动态网络的求最短路问题。2.2算法实现二、动态网络中运用A*算法解决改航问题为了得到具有实际意义的改航问题解决方法，同时为了简化数学模型中的变量个数，采用了一些启发式算法的思想，也就是让算法优先考虑那些成为最优解可能性较高的方案.首先，把当天所有航班按一定的规则排序。排序的目的是为了让那些对航路资源利用率高的航班优先起飞。其次，在确定了各航班的优先级之后，下面的工作就是在每个时刻，让当前优先级最高的航班按照其最优飞行方案飞行，优先使用当时的航路资源。此外，还要考虑让航班做一段时间地面等待后，再按其它时刻的最短路飞行的其他方案，把所有这些方案综合比较得出损失值最小的方案，才是该航班的最优飞行方案。2.2.1航班优先级的概念二、动态网络中运用A*算法解决改航问题当空域或机场容量受恶劣天气影响下降而不能满足所有待起飞航班的需求时，让地面等待成本高的飞机先于地面等待成本低的飞机起飞，肯定比反之更具经济效益，另外让耗油率高的飞机飞尽量短的航路也是降低损失的重要途径。而且航班的放行不能完全只考虑整体利益而严重损害个别航空公司的个体利益。所以，组织放飞还必须以航班时刻表为基本方案，这样的优化放飞方案才会被各方面接受。另外，准点起飞的航班的优先级也要高于产生延误的航班的优先级。同时考虑以上各方面情况，将航班优先级划分为以下三类，即时间优先级、机型优先级和延误优先级，三种优先级的高低顺序为时间优先级、机型优先级、延误优先级。2.2.1航班优先级的概念二、动态网络中运用A*算法解决改航问题a、时间优先级：就是指根据航班时刻表，预定起飞时间早的飞机比预定起飞时间晚的飞机具有优先权。b、机型优先级：是指如果按航班时刻表两架飞机起飞时间相同的情况下，地面等待成本高和耗油率高的机型比地面等待成本低和耗油率低的机型优先起飞。机型优先级是根据机型的成本率来排列。机型成本率就是该机型的航班做一个小时的地面等待和一个小时的空中飞行所产生的费用之和。c、延误优先级：延误航班是指一架航班在航班时刻表预定的起飞时间15分钟以上以后还未能起飞的情况。其优先级是最低的，只有把正点起飞的飞机安排完后再能考虑到它。三种优先级这样设定可以确定任何一架航班，在任何时刻的优先级。2.2.2航班优先级的计算二、动态网络中运用A*算法解决改航问题为了综合考虑航班的三种优先级，有必要对优先级进行量化。优先级量化是以“机型成本率”为基础的。由于大多数飞机每天都不止进行一次飞行，所以很多航班是作为其他航班的“后续航班”出现的，这些后续航班与非后续航班基本一样，只是它们的起飞时间一定要晚于前继航班的降落时间加上一个机场周转时间。因此要确定一架航班的优先级，还必须考虑其后续航班的数量以及各次续航飞行间的间隔时间。设当前时刻为T,航班k的预定起飞时间为,航班优先级为，机型成本率为，航班k的各后续航班可用时间间隔为(i=1,2,3，一架航班最多有三架后续航班)，以每5分为一单位时间：kTkPkCiTw2.2.3航班优先级的计算二、动态网络中运用A*算法解决改航问题若k为非后续航班:当时(dt=0,1,2,3(单位时间)):(正点航班)如果当时（延误航班）如果若k为后续航班，且它是某次航班的第n次续航（n=1,2,3）当时(dt=0,1,2,3(单位时间)):(正点航班)如果当时（延误航班）如果ii+1kkkkk=nk=nTwdtTwdt:P(i-n)Cdt(dt)且kTT-dtkTT-T(T3)ii+1kkkkk=0k=0TwTTwT:PiCT(T)且ii+1kkkkk=0k=0TwdtTwdt:PiCdt(dt)且(T3)ii+1kkkkk=nk=nTwTTwT:P(i-n)CT(T)且kTT-dtkTT-T(t)上述两式中，函数表示航班优先级随着地面等待时间的一个递增值。2.2.3动态网络模型二、动态网络中运用A*算法解决改航问题该网络由机场节点、导航台节点、以及连接它们的航路构成。机场节点是航班流的起始点和终止点。在每个时段内机场节点规定有限的起飞容量和降落容量。机场模型示意图如图所示。2.2.3动态网络模型二、动态网络中运用A*算法解决改航问题上图中，任何一个机场由5个节点构成，如图中的A,B,C,D,E;所有到达机场i的航班流首先达到如果节点，如果当时机场容量饱和，则该航班只能在做空中等待，上的自环弧表示一单位时间的空中等待。如果可以降落，则该航班要么到达，要么到达。到达的航班表示当天己完成所有任务，没有后续航班了，将从B点退出航路网络。到达的航班是还有后续航班的。在C点进行必要的机场周转如加油、检修、上客等，C点的自环弧便表示这些周转时间。做好下次飞行的准备之后，这些后续航班再流向D点，准备起飞。到达D点的飞机还包括一部分从E点流出的的当天第一次起飞的其他航班。所有到达D点的飞机，都在D点按航班优先级排序，如果容量允允许，优先级高的航班便优AiAiAiAiCiBiCi2.2.3动态网络模型二、动态网络中运用A*算法解决改航问题先起飞，优先级靠后的航班如果空域资源不足，则只能在D点做地面等待。D点得自环弧便表示一个单位时间的地面等待。从机场节点D出发的航班通过航路到达导航台节点，导航台节点本身不具备任何容量，也就是说飞机不允许在导航台上空停留。连接所有节点的是航路，在网络中称之为“弧”。根据航路长度为每段航路设定有初始容量值。在正常天气条件下，这些容量值便是各段航路的最大容量值。在天气的影响下，各段航路的容量值都是一个随时间t变化而变化的动态值，当航段上的容量值降为0时，该航路便可视作不再存在。所以，两点间的连通、断开状态也是一个动态值。这样的网络便称为动态网络。2.2.4天气模型二、动态网络中运用A*算法解决改航问题天气是一个最富有变化，不易模拟的一个因素。不过，为了模拟能影响到航路容量的天气状况，可以将其简化考虑成由6个变量构造的模型:6个变量分别为;1、云团的形状;2、云团面积:3、云团的移动路线;4、云团产生时刻和消失时刻;5、云团面积的衰减率;6、云团内航路的容量值损失率。这样就可以模拟任意一个路线和形状变化情况都已知天气状况。对导航设备失效状况的模拟，也可以通过设定天气模型来实现。设该失效导航台上空的雷达盲区是一固定不动，容量损失率为100%的云团即可。将该天气模型与上节的网络模型按时间t一叠加，便可确定一个动态网络。该网络在任意时刻、任意航段上的容量值都唯一确定。2.2.5航班流模型二、动态网络中运用A*算法解决改航问题对航班定义的明确与否直接影响到优化结果的准确性。所有航班都是根据一天的航班时刻表产生。由同一架飞机执行的前继航班、后续航班看作是两架不同的航班。每架航班都有明确的定义，这些定义包括:航班编号、航班号、机型、机型优先级、航班优先级、起飞机场、预定起飞时间、降落机场、预定降落时间、备降机场、预定航路、续航航班数、续航航班编号、各续航航班间的可用时间间隔等。在每个时刻T，凡预定在T时刻起飞的航班都加入网络，能够起飞的航班作为飞行航班流通过网络流向目的机场;不能起飞的航班作为地面航班流，在各机场做地面等待。将航班流模型、天气模型、动态网络模型、以及时间t一叠加，必定产生流量一容量冲突。这种矛盾的解决正是下节介绍的优化算法的重点。2.3优化算法二、动态网络中运用A*算法解决改航问题一般来说，网络中求解最短路问题都是研究的是静态网络，也就是说，随着求解的进行，网络的连通状况不变，两点间要么始终连通，要么始终断开。但是，本问题中研究的网络是一天中全国的航路网，而且随着时间的变化，由于天气情况的转变，该网络的连通状态也在不断变化。在任何以各时刻，按传统的静态网络最短路求法求出来的最短路都无法保证在下一时刻该最短路