基于计算智能的航空调度优化方法研究

【类型】学位论文

【作者】刘兆明 

【关键词】 航空调度 改进型遗传算法 航线冲突消解 整数编码机制

【摘要】随着航空运输量的不断增长，现有的航空管理系统不堪重负，不断出现机场空域不足和航班延误问题。从未来航空运输的发展来看，空管系统的相对落后将成为发展的瓶颈。因此高效的空中管理系统对于系统资源的有效利用变得越来越重要，而航空调度是空中管理系统的核心，国内外对该领域的系统研究还非常少。本文针对航空调度优化过程中的有限域约束满足优化问题，进行了航空调度问题的分解和设计；同时，利用遗传算法等计算智能方法的不需要所求问题可导、不依赖于问题具体领域和种类等特点，研究了一类基于计算智能的航空调度优化方法。 本文首先针对传统遗传算法(GA)在实际应用中存在易产生早熟收敛以及在进化后期搜索效率较低等缺陷，通过引入“幼代”及其“成长过程”思想，采用自适应交叉、变异算子和适应值指数变换等方法，提出了改进型遗传算法(IGA)，提高了算法收敛速度，增强了算法稳定性；同时，针对GA虽然收敛速度快但求取精确解效率低、而基于正反馈机制的蚁群算法(ACO)虽然求解精度高但收敛速度慢的特点，提出了一种遗传算法与蚁群算法融合的优化算法(IGA-ACO)，并以求解旅行商问题(TSP)为例，验证了IGA-ACO算法的有效性。 然后，根据航空调度优化的特点，将调度优化问题分解为空中调度优化和机场调度优化两个问题。其中，空中调度优化问题可分解为航线冲突消解和航线实时优化两个问题，机场调度优化问题可分为停机位优化分配和滑行道优化分配两个问题。针对这四个问题，采用不同方法分别进行求解，以期得到全局满意解。在航线冲突消解问题研究中，首先对改变航速大小和改变航向角的两种航线冲突消解方式进行了研究，结果表明：改变航向角方法能够有效避免航线冲突，且耗时较少。在此基础上，提出了基于改进型遗传算法(IGA)的航线冲突消解方法，且通过仿真验证了IGA算法对消解航线冲突问题的有效性。在航线实时优化问题研究中，通过采用增加虚拟台站建立了航线寻优模型，进而针对该模型中由于航线线路集规模扩张造成的求解计算耗时问题，采用遗传算法与蚁群算法融合的优化算法(IGA-ACO)对航线实时优化问题进行了求解，结果表明，优化算法的求解计算耗时与各段飞行时间相比，可以忽略，完全能满足实时应用的要求。在停机位优化分配问题研究中，采用适合该特定问题的整数编码机制，并针对种群经过遗传算子作用后可能存在停机位未分配航班的情况，在遗传算法进化过程中引入贪婪算法对种群进行优化，以保证分配航班尽可能都分配到停机位上，且停机坪的航班数目最少；同时为避免陷入局部最优，引入模拟退火思想对适应度函数进行修正。通过对停机位优化分配问题的仿真求解，验证了该算法与贪婪随机自适应搜索算法(GRASP)相比，能大大改善收敛性。在滑行道优化分配问题研究中，将机场滑行道分配问题的数学模型转化为数据结构图的形式，并采用遗传算法，针对该特定优化分配问题设计了合适的编码方式和相应的交叉、变异算子，且运用图论的Dijkstra算法进行滑行道分配最短路径的搜索，加快了该优化命题求解的速度。最后，在Windows XP Professional平台下VS2003.Net环境中基于上述模型和算法用C＋＋语言实现了一个模拟航空调度系统。实验结果表明，该系统准确率高，实时性好，为航空调度问题提供一种新颖有效的求解方法。

【学位名称】硕士

【学位授予单位】华东理工大学

【学位授予年度】2016

【导师姓名】钱锋

【读秀链接】读秀链接