混合遗传算法求解航班延误恢复调度

混合遗传算法求解航班延误恢复调度摘 要：综合考虑航班延误各类损失，建立了合理的大规模航班 延误恢复调度模型。以此模型的目标函数为适应度函数，设计了基 于遗传算法和模拟退火算法的混合遗传算法来快速有效的寻找优 化恢复调度方案。仿真结果表明，该算法与先到先服务的现行调度 方法相比，可以有效的减少各种延误损失。关键词：航班延误；调度模型；混合遗传算法引言航班延误恢复调度(recovery scheduling of flight delays, rsfd)是指由于某些原因造成了大面积的航班延误，当恢复起飞时， 需要重新调度延误航班。航班恢复调度问题是一个多目标的优化问 题，目前国际、国内在理论与实际应用上都没有很好的解决方法。 国内机场的普遍做法是靠航空管制员自身的经验和判断进行的，基 于先到先服务原则(first come first serve， fcfs)，调度效率 较低。因此本文考虑引入遗传算法，遗传算法( g e n e t i c a l g o r i t hm ， ga)在解决最优化问题上有较好的效果，但“早熟”(prematurely) 现象是目前遗传算法研究中的关键问题。所以在这种情况下考虑引 入模拟退火算法对遗传算法进行改进，利用该算法在搜索时可以以 一定概率接受劣质解的策略避免遗传迭代过程提前陷入局部最优， 从而提高算法的鲁棒性，将两者结合，有利于丰富优化过程中的搜 索行为，增强全局和局部搜索能力和搜索效率。1 航班延误经济损失