基于DRDG模型的空中交通改航系统的研究与实现

摘要

空中交通改航问题是一类特殊的资源分配与调度问题，它包括航班起飞时间的确定和最短路的搜索，以达到总延误最小为目标。本文以改航问题为研究对象，建立了DRDG(DynamicRerouting Dynamic Ground holding)模型，由于改航问题是一个NP-Hard 问题，本文采用混合的启发式算法，得到可达目标的近似最优解。 在DRDG模型中将改航问题划分为两个子问题：航班起飞时刻安排和最短航路选取，提出一个集成了遗传算法和MDA*算法的动态实时改航算法，其中航班起飞时刻安排采用基于窗口的遗传算法进行求解，最短航路选取采用MDA*算法求解，同时考虑到两问题之间的相互影响和反馈，以MDA*求出的空中延误的倒数作为遗传算法的适应度函数的一部分，最终采用动态实时改航算法对模型进行求解，获得近似全局最优解。 在搜索最短路的问题中，根据空中交通的规则，证明了空中交通图满足FIFO原则，并解决了航班空中盘旋等待问题，从而采用MDA*算法求解航班最短路问题；在航班起飞时刻安排问题中，首先将监控时段划分成若干时间片，然后利用尾流间隔的规则对时间片进一步的划分，最后采用基于窗口机制的编码规则对航班地面延误进行编码，结合MDA*算法解决航班起飞时刻的安排问题。 最后，以VC++为开发工具对改航系统进行了实现，基于相同的真实航班数据和航图，分别采用动态实时改航算法和CPLEX 对模型进行求解，对比二者的求解时间和结果，得出以下结论：①动态实时改航算法在求解时间上有一定的优势；②存在天气突变的情况下，动态实时改航算法给出的策略在总延误上占优。

目录

文摘

英文文摘

论文说明：图表目录

声明

第一章 绪论

第二章 相关基础知识

第三章 DRDG模型与改进的改航算法

第四章 基于DRDG模型的空中交通改航系统的实现

第五章 总结与展望

参考文献

致谢

在学期间的研究成果和发表的学术论文

附录