文档介绍：南京航空航天大学
博士学位论文
航空公司不正常航班恢复模型及算法研究
姓名:赵秀丽
申请学位级别:博士
专业:交通运输规划与管理
指导教师:朱金福
2010-06
南京航空航天大学博士学位论文
摘要
恶劣天气、飞机故障、空中流量控制等外界条件的不确定性常常造成航班计划不能正常执
行,航班不正常对旅客造成了很大的不便,也成为航空公司提高服务质量,降低运营成本的一
大障碍,不正常航班计划恢复正是针对这一问题提出的。不正常航班计划恢复问题是一个实时
大规模整数规划问题,其变量和约束条件复杂,目前能够满足航空公司实践需要的研究成果很
少。由航空公司资助开发的航班计划恢复算法,具有保密性和专用性,而且不同航空公司的运
作机制具有很大差异,目前还没有商业化的软件供航空公司使用。我国对不正常航班计划恢复
问题的研究处于起步阶段,航班计划恢复工作依然是由签派人员手工完成,很难在较短的时间
内实现资源的优化配置。本文的目的就是采用数学方法描述和求解不正常航班计划恢复问题。
本文的主要研究工作包括以下几个部分:
1)取消航班问题。取消航班是不正常航班计划恢复过程中经常遇到的一个调度问题:给
出多个建议的取消航班起点和终点对,求最优的取消航班路径。将 Floyd-Warshall 算法应用到
取消航班问题中,为取消航班设计了求解算法,使签派人员在取消航班决策时能够快速有效的
获得优化方案。
2)飞机路线恢复问题。飞机路线恢复问题是典型的资源指派问题,本文从目标函数、约束
条件两个方面改进资源指派数学模型。构造了两个不同的目标函数,一是旅客延误时间最小,
二是航空公司损失最小。旅客延误时间最小目标函数中引入了延误权重因子,在保证总延误时
间最短的情况下克服了少数航班被分配长时间延误的不足;航空公司损失最小目标函数改变了
以往延误成本的计算方法,并首次引入了旅客失望溢出成本的概念。约束条件增加了机场设施
和天气条件对飞机的起降约束、不出现超售、定检约束和重要航班优先执行。提出了逐延误指
派算法对模型求解,逐延误指派算法按照签派人员调整航班的思路启发式地恢复飞机路线,可
快速获得问题的可行解。案例测试显示,该算法能够获得比签派人员手工调整优化、高效的恢
复方案。
3)机组恢复问题。机组是航空公司除飞机以外的第二个重要资源,在飞机路线恢复完成后,
如果机组无法到位,航班会依旧延误。机组恢复就是给完成了飞机指派的航班分配合适的机组。
本文为机组恢复问题构造了数学模型,以加机组使用成本最小为目标函数,充分考虑了机组执
行任务的约束条件,采用蚁群算法对模型求解,在蚁群算法中引入蚂蚁种类参数对蚁群算法改
进,使之适合机组恢复问题的求解需要。案例测试显示,设计的模型和算法能够满足机组恢复
的实际要求。
i
航空公司不正常航班计划恢复模型及算法研究
4)一体化航班计划恢复问题。目前求解航班恢复问题,采用的是分阶段方法:首先恢复飞
机路线,然后是机组路线,最后将受影响的旅客重新指派到相应的航班上。一体化航班恢复是
针对这几个问题的综合恢复,目前还没有能够在计算机上实现。一体化航班恢复属于大规模数
学规划问题,本文给出了描述一体化航班恢复问题的数学模型,由于问题规模较大且变量和约
束条件复杂,直接求解无疑是困难的,采用 Benders’分解算法对模型求解,将一体化航班计划
恢复问题分解为一个限制主问题和三个子问题,限制主问题是航班时刻表恢复问题,子问题分
别是飞机路线恢复、机组恢复和旅客路线恢复问题。给出了各个子问题和对偶问题的数学表达,
求解子问题及对偶问题,将产生的可行割或优化割反馈回限制主问题,迭代直到获得主问题的
最优解。给出了算法的详细求解步骤并编码实现。最后案例测试显示算法能够实时地给出较为
满意的结果。
关键词:航空公司,不正常航班,计划恢复,建模,算法
ii
南京航空航天大学博士学位论文
Abstract
Bad weather, aircraft failures, air traffic control and other external conditions of uncertainty often
resulted in the normal flight schedules cannot be implemented, irregular flights cause much
inconvenience to the passengers, and it has also e an obstacle to the improving service quality
and re