航空公司不正常航班恢复模型及算法研究

【类型】学位论文

【作者】赵秀丽 

【关键词】 航空公司 不正常航班 计划恢复 建模 算法

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

【学位名称】博士

【学位授予单位】南京航空航天大学

【学位授予年度】2016

【导师姓名】朱金福

【读秀链接】读秀链接