伴随着中国民航业的快速发展,航班延误已经成为一个全社会关注的焦点问题。航班恢复是指航空公司在发生延误时通过对一个时间窗口内的时刻、飞机、机组人员和旅客等相关资源的重新安排和调度,使得后续航班能按照原计划进行。航班恢复的质量对减轻延误程度以及降低延误所造成的损失具有至关重要的影响。由于问题的复杂性,航班恢复分成多个步骤,本文对其中的旅客恢复问题进行研究,主要研究内容与成果如下:(1)提出了一个基于行列同时生成求解LP松弛问题的启发式算法。旅客恢复问题的本质是一个规模巨大的有附加条件的集合划分问题,由于在每步迭代需要求解数以万计的定价子问题而使得经典的列生成算法效率很低。本文提出了一个有两重循环的算法来克服这一困难,在内层循环中算法仅对部分旅客流进行重调度,而在外层循环中对下一个内循环问题的构成进行调整。在不同的航班延误程度、客座率以及旅客流规模的条件下,对该算法的性能进行了实验验证。实验结果表明,该方法在相同或更少的运算时间内所得到的结果大幅优于仅考虑部分旅客流的经典列生成算法。对于困难问题,与考虑全部旅客流的经典列生成方法相比,该算法的运行速度提高一倍,而结果与最优解非常接近。(2)提出了一个基于分支定价算法与局部搜索技术相结合的方式获得整数解的算法。针对旅客恢复问题提出了一种基于分支定界框架和启发式方法相结合的整数解算法。该方法在获得了一个节点的LP解之后,基于LP解和当前最优整数解定义一个邻域,并采用上面求解LP的算法而生成一组新的变量,然后利用经典分支定界算法实现局部搜索;基于一个松弛的网络流模型中的边对节点进行分支,以代替按照路径分支的经典方法;在算法运行过程中采用一个独立的线程来运行遗传算法,它通过共享同一个整数解缓冲池的方式以实现与分支定价算法的交互与相互促进。实验结果表明,该算法所获得的结果可以大幅地降低旅客取消和延误人数,尤其是对于大规模的困难问题,它可以在满足时限要求的前提下获得令人满意的解。