航线网络优化方法研究

杨思浩 罗凤娥

摘要：航线网络优化对民航业有着举足轻重的作用。以现如今的航线网络分布而言还有很多不合理的地方，由于历史和经济原因，我国现如今的航空资源分布不合理，航线规划过时，缺少及时的更新，以及资源利用率低，造成了大面积的空域不能合理运用，而部分空域航线规划又过于紧密。在这种情况下就会造成资源浪费，且效率低下的问题。所以航线优化这一题目就具有极高的研究价值和现实意义，可以直接作用于提升民航业的运行效率，优化整体结构。

关键词：民航网络，调配，寻优，状态图

1.引言

随着民航业的不断发展，航空器数量增加但可用空域却无法进一步开拓，于是在数年前就提出了“自由飞”这个概念。但是为了保证安全运行，所有上天的航空器都必須接受管制员的“管制”。目前为止为了实现这个目标，可以从优化航线网络、加强导航技术与导航系统和数据传输系统等方式，下面就航线优化方面进行叙述，主要对基于GA寻优算法和航线调度优化管理进行研究。

首先从一条航线的诞生开始分析，因为航空历史悠久，发展过程较长，所以目前为止已经产生的航线大都是数年前的老旧航线，而当时的设计师并没有足够的前瞻性来预见现在的情况。而局限于多种因素无法对这些已经诞生的航线网络进行大规模的改进，所以现代设计师即使是从这个基础上进行不断的改进，依旧是杯水车薪难堪大用。基于我国现在的航空使用权绝大部分还是归属于空军的背景下，民航业所能使用的只是极其有限的一部分，从上图上来显示就是诸多的危险区、禁区和限制区，所以如何利用好这些资源显得更加重要。综合以上内容，可以总结出一条航线的诞生需要考虑的因素：

（1）空域。所规划设计的空域首先必须是允许飞行的航段，因为一条航路还需要考虑到数公里的宽度。

（2）确定保护区评估障碍物高度.以保证航空器的安全。

（3）与现有的航路有多少交汇点。若是与已有航路出现了过多交汇点，势必会影响这一条航路上航空器飞行计划的制定，会凭空增加许多难度，同时也增加了突发事件发生的概率。

（4）主要飞行器机载设备要求。因为航线规划在不同的地方对于航空器的性能要求也是不一样的，比如以高高原机场为起降场的航线，就会对于机载导航设备有更高的要求，同时由于环境的特殊情况，会对数据通信也有更高的要求以保证航空器的安全运行。

（5）还需要考虑给当地管制或流量新增多大压力是否需要分流。就如上文所言，在航空业高速发展的今天，有部分机场已经是高负荷工作了，所以在设立一条新航线时，还需要考虑管制人员的工作量与机场的服务能力。

2.航线优化的评价内容和指标

（1）油耗指标。油耗是航班在执行日常飞行计划中与航空公司运营成本直接相关的内容，若在航线优化后可以获得明显的油耗量减少效果，从经济方面而言减少了航空公司大量的运营成本，从绿色运行而言减少了碳排放量，符合可持续发现的观念。

（2）.时间指标。这一项指标主要是为了体现动态管理的优势，在遇到突发事件时可以灵活变通。比如航班在运行过程中突然得知着陆机场有恶劣天气，那么就可以在条件允许的情况下，安排合适的航班提前降落以躲避恶劣天气。

（3）准时到达。该指标主要是指在机场当局考虑到经济、安全和效率等方面的情况下，给予飞机进场和离场的时间有一个严格的规定，并依据制定的计划来完成飞机进场和离场的时间安排，除此之外，在航空公司日常的运行中，准时到达率也是一项重要的评价标准。

当前以有学者对航线的动态优化进行了研究，在研究的过程中发现，在航线动态优化的过程中，飞机系统和ATC系统是最重要的两个部分。首先是飞机系统通过接受地面ATC系统发布的不同种类的信息，将其汇总，并根据指标评估该条航线是否需要重新规划。若是需要重新规划线路，则需要在新的航线规划数据生成后对其进行模拟仿真来检测其合理性，合格之后将信息发送给地面相关部门。地面ATC系统在接受到信息之后首先是对信息进行处理，将信息中包含的飞行环境、交通情况和不可用空域等情况发布出去。整个过程用图来表示结果见图1。

3.基于GA寻优算法的简介

对于航线实时优化优化来说，一旦当作用的对象（航路网络）规模超过一定界限时，一般的寻优算法所消耗的时间是令人难以接受的，而GA寻优算法在众多的算法中具有面对大规模航线进行寻优计算的能力，而且还具有高速得出结果的功能，这就使得它是目前为止效果最好的算法，然而随着实时优化的任务量在不断的增大，即使是GA算法也需要进一步的改进，才能用于解决相关的航线实时优化任务。

由于在实现航路的实时优化过程中发现因为大多数情况地形比较复杂，所以求解的质量并不能令人满意，于是在研究过程中，专家引入了“成长”和“幼代”这两个概念来完善GA算法。在GA算法未进行改进之前，其实也是一种“幼代”，只不过在产生下一代的过程中，所有的种类都被保存下来，致使所得到后代的质量无法得到保证，而优化后的GA算法则是在产生下一代的过程中，加入了竞争阶段，然后令优秀的后代得以保存下来。在这一过程中，需要保证的是初代种群数目足够大，这样在不断地淘汰过程中才能保持整个种群的多样性，也就是GA算法中的随机搜索能力。在这整个过程中采用了自适应交叉的延续方式，并在后续指导染色体的产生，可以达到将没有优势的染色体得到完善的目的，然后加强该算法的寻优能力，使所得结果的质量得到提高。

3.1总结基于GA寻优算法

基于GA寻优算法的优点是可以比较准确的解决在飞行中航线的动态实时优化的问题，但是缺点是整体过程较为复杂，需要付出大量的人力物力进行计算过程的数据处理。创新点在于实时进行优化，可以极大地增加航线网络优化的准确率和效率。

4.航线调度优化方法的简介

除了对整个航线网络进行优化，还有一种思路是进行航线优化调度。航空公司在日常的计划制定后需要根据已有的航路来分配特定的机型，然后合理的分配航班，需要满足过程中的安全问题以及飞行器在运行任务后的定期维修检查，所以在构建模型时，需要考虑多个因素。为了满足这一要求，研究出了将各个因素作为约束条件所构成的方程中。由于现实情况的特殊性，方程在构建完成时往往是非线性的，然后根据运筹学中的解非线性方程组的方法得出一个最优解，这是最初代解决航线调度优化方法的基本思路。

在解决航线调度优化的时，首先需要考虑的就是其需要满足航空公司所指定的航班飞行计划得以正常运行，然后在保证航行安全的情况下，生成新的调度方案。除此之外，航线调度还需要将各类规则考虑其中，满足上述几点条件后，可以令该问题模型转变另一种思路，即逆向思维将航线匹配至适合的机型，如此便将整体建模的难度降低了。

4.1生成调配方案时需要注意的规则

在整个航线的调配过程中需满足所述几条要求：

（1）符合航班计划：在航线调配方案生成时不能之前已有的飞行计划产生冲突，比如不改变原计划中的机型、航班起飞到达机场、航班起飞到达时间等。

（2）航班覆盖，在一般情况下只有一架航空器可执行单次飞行任务。

（3）维护要求：在正常情况下，为了方便和经济效益，维护检修工作都是在航空公司所属的机场进行的，维护检修的目的是为了使航空器在执行任务时能在需要的时间在正确的机场获得检修。

4.2航线调配等图建模

航线优化调配模型的建立需要先表述一下参数：

用两个三元的方程组来表示一个航班，第一个方程组来描述该航班的起始状态，相应的第二个方程组来描述该航班的降落状态。该方程还需要包括以下重要参数。

过夜集合：用来表示该航班属于某一过夜集合。

维护过夜集合：用来表示在某一机场过夜维修的航班。

过站时间：来表示相连的两架航班的时间间隔和过站所需要时间的比较。

航班串：如果相邻的两架航空器的维护周期时长满足一个维护过夜集，说明该两架航空器为可行航班串。

运营天数：在航空器出发时距离上次检查维修的过夜时间的天数。

考虑到线路规划的特殊性，就在以上的基础上将整个建模问题带入到一张图中，从图中更加清晰的展现出优化结果和思路。

图的定义：

一个图（G）定义为一个偶对（V，E） ，记为G=（V，E） 。其中： V是顶点（Vertex）的非空有限集合，记为V（G）;E是无序集V&V的一个子集，记为E（G） ，其元素是图的弧（Arc）。将顶点集合为空的图称为空图。

其形式化定义为：

G=（V ，E），V={v|vÎdata object}，

E={<v，w>| v，wÎV∧p（v，w）}，

P（v，w）表示从顶点v到顶点w有一条直接通路。

弧（Arc） ：表示两个顶点v和w之间存在一个关系，用顶点偶对<v，w>表示。通常根据图的顶点偶对将图分为有向图和无向图。

有向图（Digraph）： 若图G的关系集合E（G）中，顶点偶对<v，w>的v和w之间是有序的，称图G是有向图。在有向图中，若 <v，w>ÎE（G） ，表示从顶点v到顶点w有一条弧。 其中：v称为弧尾（tail）或始点（initial node），w称为弧头（head）或终点（terminal node） 。

无向图（Undigraph）： 若图G的关系集合E（G）中，顶点偶对<v，w>的v和w之间是无序的，称图G是无向图。 在无向图中，若"<v，w>ÎE（G） ，有<w，v>ÎE（G） ，即E（G）是对称，则用无序對（v，w） 表示v和w之间的一条边（Edge），因此（v，w） 和（w，v）代表的是同一条边。

在了解了图的基本定义之后，可以进一步介绍本方法中的航线调配等图建模。

可以将飞机航线调配有向图进行以下定义，任何一个机场在任何时间，如果有大于等于一个航班在离开时刻，机场都会相应的形成一个点，称之为内部点，而相对应的将每一个源节点赋予该机场，并将一架飞机的起降点在图中表现为其的航班弧。将航班离开飞机的连续的时间点作为一个地面弧，那么就会有N条地面弧生成。再将所有满足初始条件和限制条件的节点命名为中间点。

我们可以根据之前的研究得出其实可以将航班的航线调配问题看成是在一张等图上对其进行一个路径划分问题的研究，所以就可以进一步转化为研究在解决一个状态图中的路径划分问题解决方法的研究，在此基础之上可以加入航线调配过程的一些限制条件以及初始状态，可以更加准确的描述这个问题。所以就可以将网络路径划分问题的可行解作为航线优化调配问题的可行解。依赖以上所建立的模型，依据状态图整体的构造流程和数学方程构建的约束，可以得出可行解。

使用软件（java）完成状态图的构建，并利用（lingo）对得出的状态图进行处理和计算，可以得出相应的可行解。

4.3总结航线调度优化管理方法

航线调度优化管理方法的优点就在于将复杂的航线优化问题转化为一个相对简单明了的图形来解决，并且在其中将限制条件和初始状态以数学模型和图相结合的形式来呈现，极大地简化了问题。缺点是只单独的提出了航线优化这一问题，并没有将其他（例如机型分配，机组调配等）问题结合在一起。创新点是别出心裁的用图表示了航线优化这一复杂问题并将其划为路径分配问题来解决。

5.结语

为了解决航班网络优化这一难题，国内外专家学者都进行了大量的研究与实验，但是囿于已建成老航线的干扰以及可飞空域的限制，总会伴随有诸多问题的出现。而经过不断的努力现在已经有类似于基于GA寻优算法和航线调度优化管理等优秀方法的出现，逐渐是航线优化的可行性和准确性得到不断提高，在接下来的时间还需要进一步的修正与改善，并通过将多种因素考虑其中而研究出更加完善的航线网络优化方法。

参考文献

【1】乐美龙，黄文秀，基于时空网络的航班机型分配问题研究【J】交通运输系统工程与信息，2014.14（1）：81-87.

【2】孙宏，杜文，航空公司飞机排班问题的排序模型及算法【J】系统工程理论方法应用，2002，11（3）：244-247

【3】R Gopalan，K T Talluri. The aircraft maintance routing problem【J】Operations Research，1998，32（1）：43-53

【4】于详，樊玮  ，机场航班航线调度优化管理仿真研究【J】计算机仿真，2018.7（7）：54-58

【5】胡小兵，吴树范，江 驹，民航飞机飞行航线动态实时优化仿真研究【J】计算机仿真，2001.5（3）：80-83

【6】朱星辉 ，朱金福 ，髙强，基于约束编程的飞机排班问题研究【J】交通运输系统工程与信息，2011.（6）

【7】朱星辉，朱金福，髙强， 基于动态列生成算法的飞机排班问题 研究【J】数学的实线与认识 ，2014，（19） .

作者简介：杨思浩，男，1997.6-  籍贯：宁夏省惠农县;研究方向：交通运输规划与管理。

通讯作者：罗凤娥，女，1972.11- ，职称：教授，学历：硕士，研究方向：航空运行和飞行签派。