杨新湦， 屈琮博， 王梓旭

(1.中国民航大学中欧航空工程师学院， 天津 300300； 2.中国民航大学空中交通管理学院， 天津 300300)

航空运输系统是一个复杂的巨系统，航班不正常是每个航空公司不可避免会面临的问题。航空公司大面积不正常航班恢复是困难问题，一般而言，航空公司不正常航班恢复可分为分阶段恢复与一体化恢复。分阶段恢是将整个恢复问题分为飞机恢复、机组恢复、旅客恢复三个阶段逐步求解；一体化恢复则是综合考虑飞机、机组、旅客因素。

对不正常航班恢复的研究多数集中于分阶段恢复研究。Teodorovic等[1-4]在1984～1995年先后对飞机停运、机场关闭航班恢复问题、旅客恢复和机组恢复问题进行了研究。分别使用分支定界、动态规划、启发式算法进行了求解，奠定了不正常航班分阶段恢复的基础。吴刚等[5]提出一种改进列生成算法，每次迭代过程中加入多个列，并对加入的多个列需要满足的条件进行了分析，最后给出的算例验证了该方法的正确性和有效性。田倩南等[6]改进时空网络算法，给出占优准则，有效减少了可恢复航线的组合数量，提升计算效率。

已有文献中多采用时空网络进行建模，时空网络中不仅有描述航班衔接的航班边，还有机场节点和时间节点。当进行一体化建模时导致模型过于复杂。Sherali等[12]系统介绍了航班网络的使用，相比时空网络模型复杂度低，但是不能将时间、地点等属性表现在图中，诸如飞机维修约束、机组执勤时间约束、客票取消操作不易表达。……