伴随着运输需求的增长,航空公司的航班计划被设计得越来越紧密,而恶劣天气、设备故障等不可预料的因素会频繁中断航班计划的正常执行。当计划被中断后,快速地进行恢复对航空公司来说是重中之重。旅客行程恢复问题就是恢复过程中最重要的环节之一。旅客作为航空公司的主要服务对象,是航空公司盈利的决定性因素,为旅客提供匹配的高质量恢复方案可以有效降低航空公司的损失,提高旅客满意度,挽回公司声誉。目前使用的人工辅助决策的方法已经很难满足旅客行程恢复的需求,通过优化算法实现智能决策是业界的迫切需求。本文根据航空公司实际运营场景研究了旅客行程恢复问题模型及优化算法,主要工作及成果如下:（1）为了能够切实匹配应用需求,从航空公司的实际需求出发,考虑了中转航班舱位共享约束、PNR不可分割约束、旅客多行程衔接约束,构建了以最大化航司收益和旅客满意度为优化目标的多目标问题约束模型。通过给不同目标赋予不同权重的方式来处理多个优化目标。（2）通过构建旅客行程恢复图来表示旅客行程恢复过程。提出了一种基于变邻域搜索的优化算法。为了获得问题的初始解,提出了一种基于禁忌表的回溯搜索算法。在优化的过程中,设计了三种不同的邻域规则来构造邻域,并采用随机选择邻域生成解进行局部搜索的方法来避免陷入局部最优。基于不同测试数据的实验结果表明,该方法能在短时间内取得良好的优化效果。（3）为了进一步优化旅客行程恢复问题,基于列生成方法将问题分解为主问题和子问题并分别建立了限制主问题整数规划模型和子问题模型,提出了一种分支定价优化算法求解整数解。为求解子问题,提出了一种基于节点预处理的贪心搜索算法。限制主问题使用CPLEX求解。实验结果表明,该算法可在时间相近的情况下取得比变邻域搜索优化算法更优的结果,与理论最优解最大偏差3.34%。