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