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

中图分类号：V351学科分类号：082300论文编号：1028707 10-0001博士学位论文航空公司不正常航班恢复 模型及算法研究 Nanjing University of Aeronautics and Astronautics The Graduate SchoolCollege of Civil AviationResearch on Modeling and Algorithm of Airline Irregular Recovery 承诺书本人郑重声明：所呈交的学位论文，是本人在导师指导下,独立进行研究工作所取得的成果。尽我所知，除文中已经注明 引用的内容外，本学位论文的研究成果不包含任何他人享有著 作权的内容。对本论文所涉及的研究工作做出贡献的其他个人 和集体，均已在文中以明确方式标明。本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文。（保密的学位论文在解密后适用本承诺书）作者签名：_日 期：摘 要恶劣天气、飞机故障、空中流量控制等外界条件的不确定性常常造成航班计划不能正常执 行，航班不正常对旅客造成了很大的不便，也成为航空公司提高服务质量，降低运营成本的一 大障碍，不正常航班计划恢复正是针对这一问题提出的。不正常航班计划恢复问题是一个实时 大规模整数规划问题，其变量和约束条件复杂，目前能够满足航空公司实践需要的研究成果很 少。由航空公司资助开发的航班计划恢复算法，具有保密性和专用性，而且不同航空公司的运 作机制具有很大差异，目前还没有商业化的软件供航空公司使用。我国对不正常航班计划恢复 问题的研究处于起步阶段，航班计划恢复工作依然是由签派人员手工完成，很难在较短的时间 内实现资源的优化配置。本文的目的就是采用数学方法描述和求解不正常航班计划恢复问题。本文的主要研究工作包括以下几个部分：1）取消航班问题。取消航班是不正常航班计划恢复过程中经常遇到的一个调度问题：给出 多个建议的取消航班起点和终点对，求最优的取消航班路径。将Floyd-Warshall算法应用到取 消航班问题中，为取消航班设计了求解算法，使签派人员在取消航班决策时能够快速有效的获 得优化方案。2）飞机路线恢复问题。飞机路线恢复问题是典型的资源指派问题，本文从目标函数、约束 条件两个方面改进资源指派数学模型。构造了两个不同的目标函数，一是旅客延误时间最小，二是航空公司损失最小。旅客延误时间最小目标函数中引入了延误权重因子，在保证总延误时 间最短的情况下克服了少数航班被分配长时间延误的不足；航空公司损失最小目标函数改变了 以往延误成本的计算方法，并首次引入了旅客失望溢出成本的概念。约束条件增加了机场设施 和天气条件对飞机的起降约束、不出现超售、定检约束和重要航班优先执行。提出了逐延误指 派算法对模型求解，逐延误指派算法按照签派人员调整航班的思路启发式地恢复飞机路线，可 快速获得问题的可行解。案例测试显示，该算法能够获得比签派人员手工调整优化、高效的恢 复方案。3）机组恢复问题。机组是航空公司除飞机以外的第二个重要资源，在飞机路线恢复完成后,如果机组无法到位，航班会依旧延误。机组恢复就是给完成了飞机指派的航班分配合适的机组。本文为机组恢复问题构造了数学模型，以加机组使用成本最小为目标函数，充分考虑了机组执 行任务的约束条件，采用蚁群算法对模型求解，在蚁群算法中引入蚂蚁种类参数对蚁群算法改 进，使之适合机组恢复问题的求解需要。案例测试显示，设计的模型和算法能够满足机组恢复 的实际要求。4）一体化航班计划恢复问题。目前求解航班恢复问题，采用的是分阶段方法：首先恢复飞 机路线，然后是机组路线，最后将受影响的旅客重新指派到相应的航班上。一体化航班恢复是 针对这几个问题的综合恢复，目前还没有能够在计算机上实现。一体化航班恢复属于大规模数 学规划问题，本文给出了描述一体化航班恢复问题的数学模型，由于问题规模较大且变量和约 束条件复杂，直接求解无疑是困难的，采用Benders，分解算法对模型求解，将一体化航班计划 恢复问题分解为一个限制主问题和三个子问题，限制主问题是航班时刻表恢复问题，子问题分 别是飞机路线恢复、机组恢复和旅客路线恢复问题。给出了各个子问题和对偶问题的数学表达,求解子问题及对偶问题，将产生的可行割或优化割反馈同限制主问题，迭代直到获得主问题的 最优解。给出了算法的详细求解步骤并编码实现。最后案例测试显示算法能够实时地给出较为 满意的结果。关键词：航空公司，不正常航班，计划恢复，建模，算法AbstractBad 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 become an obstacle to the improving service quality and reducing operational costs for airline,the irregular flight recovery is made to solve this problem.Irregular flight recovery is a real-time,large-scale and integer programming problem,it has complex variables and constraints,the works that can be used in airline practice is less,and the operating mechanisms of the different airlines are also different,the algorithms of flight schedule recovery,which are funded by several famous airline companies,are confidential and exclusive,we have not found commercial software in market yet.Nowadays,the research of irregular flight recovery in China is just at the early stage,flight recovery work is still done manually by dispatchers,and it is difficult to allocate the resources in short time and optimal way.The purpose of this paper is to use mathematical methods to describe and solve the problem of irregular flight recovery.This major research work includes the following sections.1)The cancellation of flight.The cancellation of flights is a rescheduling problem in flight recovery decision which is often encountered:advising one more pairs of origination and destintion,to find an optimal cancellation path.In this thesis,Floyd-Warshall algorithm is applied to solve cancellation problem,the detail of algorithm is described,and case shows it can get optimization solutions quickly and efficiently.2)The aircraft route recovery.Aircraft route recovery is a typical resource assignment problem,this thesis present an improved resource assignment mathematical models from objective function and constraints.Two different objective functions have been constructed,the one is the shortest of passenger delays,and the other is the smallest delay loss of airlines.We introduce a weight factor to balance the passenger delays in the first objective function,to overcome the shortage of some flights being allocated long delays.In the second objective function,it is about airline loss in the process of irregular flight recovery,we present a new method to caculate the airline cost,and draw a definifion of Passengers Disappointed Spilling Cost.Much more constraints has considered,such as the facilities and weather conditions in airport,no overbooking,aircraft maintainance,and important flight first.A chasing delay assignment algorithm is proposed to solve the model.The algorithm restore the aircraft routes according to the idea of dispatchers in the process of resuming flight schedules,and the detail is presented step by step.Cases show it can quickly obtain near optimal solution,and the solution is better than given by dispatchers.in3)The crew recovery.Crew is the second important resources in airlines.Even the aircraft route is restored perfectly,if a crew is not in the right place,flights still delay.The problem of crew recovery is to assign appropriate crew to flight duties after that duties have been allocated right aircraft already.This thesis introduce a mathematical model to solve this problem.The objective function is to minimize the crew loss in the disrupted flight schedule recovery,the requistite constraints have been taken into account in the model to describe the crew recovery problem.Ant colony algorithm is developed for solving the model,and a new concept of ant species is proposed to fit the crew type in ant colony algorithm.Computational experiment has shown that the designed algorithm can meet the practical requirements for crew recovery.4)Integrated flight recovery.Recovery models today solve flight recovery problem in a phased approach.First,the aircraft routing is restored,then crew pairings are restored.Finally affected passengers are reassigned accordingly.Integrated flight recovery has been the focus of a number of studies,yet it has never been solved computationally.Integrated flight recovery is an instance of a large-scale mathematical program.In this thesis,mathematical model is presented to describe the integrated flight recovery problem.Given the large-scale nature,and variables and constraints are complex,it is extremely difficult to solve the model integrating all components in a suitable runtime.By a Benders5 decomposition method,the model is decomposed into one restricted main problem and three sub-problems:schedule recovery,aircraft route recovery,crew recovery,and passenger itinerary recovery.The sub-problems and its dual problem produce feasible cut or optimal cut,and fed the cut back to the main issues,the progressive loops until the main problem get its optimal solution.The detail of algorithm is presented step by step and run it in computer.Cases show that the algorithms can provide a satisfied solution in a suitable runtime.Keywords:Airline,Irregular flight,Schedule recovery,Modeling,Algorithmiv目 录第一章绪论.11.1 研究背景和意义.11.2 研究目标及主要内容.21.3 研究方法与技术路线.4第二章不正常航班计划恢复问题研究综述.62.1 飞机路线恢复问题综述.72.2 机组恢复问题综述.102.3 一体化恢复问题综述.122.4 本章小结.13第三章不正常航班恢复业务流程及经典数学模型简介.143.1 不正常航班恢复业务流程.143.1.1 相关术语和定义.143.1.2 不正常航班计划恢复业务流程.163.1.3 不正常航班计划恢复业务总结.223.2 时空网络简介.243.3 不正常航班恢复问题数学模型.263.3.1 资源指派模型.263.3.2 多商品网络流模型.283.3.3 时间离散近似模型.303.3.4 机组恢复数学模型.303.4 本章小结.32第四章飞机路线恢复模型及算法.334.1 弓|言.334.2.1 航班取消问题描述.344.2.2 基于Floyd-Warshall的取消航班算法.344.2.3 算例分析.364.3 改进的资源指派数学模型及逐延误指派算法.394.3.1 问题描述及约束条件.394.3.2 目标函数.414.3.3 逐延误指派算法.444.3.4 逐延误指派算法复杂度分析.454.3.5 算例分析.454.4 考虑旅客失望溢出成本的飞机路线恢复数学模型.494.4.1 成本描述及定义.494.4.2 数学模型.524.4.3 算例分析.534.5 本章小结.55第五章机组恢复模型及算法.565.1 机组恢复问题描述.565.2 机组恢复问题的数学模型.575.3 蚁群算法求解机组恢复问题.605.3.1 蚁群算法.605.3.2 基于蚁群算法的机组恢复问题求解.615.4 算例分析.645.5 本章小结.67第六章 不正常航班的一体化恢复模型及算法.686.1 不正常航班一体化恢复问题描述.686.2 一体化航班计划恢复的数学模型.696.3 Benders9 分解方案.756.3.1 Benders，分解算法回顾.756.3.2 一体化航班计划恢复的限制主问题.776.3.3 ARM子问题及其对偶问题.806.3.4 CRM子问题及其对偶问题.826.3.5 PRM子问题及其对偶问题.836.4.1 限制主问题求解算法.846.4.2 ARM子问题求解算法.856.4.3 CRM子问题算法设计.876.4.4 PRM子问题算法设计.886.5 算例分析.89vi6.6 本章小结.93第七章 全文总结与研究展望.947.1 研究工作总结.947.2 创新点总结.957.3未来工作展望.95参考文献.96致谢.103在学期间的研究成果及发表的学术论文.104附录.105附录1：延误航班旅客失望系数调查表.105附录2：逐延误指派程序部分代码.105V11图表清单表3.1不正常航班调整的相关定义和说明.15表4.1顺延的航班计划.46表4.2飞机信息表.47表4.3广州机场出发的航班串CC表.47表4.4广州机场可用飞机简表.47表 4.5 优化结果.48表4.6优化结果.54表5.1原计划机组执勤表.65表5.2打乱的机组执勤计划.65表5.3优化的机组执勤表.66表5.4方案运行结果.67表6.1集合标识.70表6.2参数标识.71表6.3主问题及子问题中用到的对偶变量与约束条件的对应关系.79表6.4飞机信息表.89表6.5机组任务表.90表 6.6 机场信息表.92表6.7案例运行结果.92图3.1机务故障导致的不正常航班计划恢复流程.19图3.2流量控制导致的延误调整流程.20图3.3严重流量控制/机场关闭情况下的不正常航班计划恢复流程.21图 3.5 时空网不意图.26图3.6多商品流网络的一个典型机场子偶图.28图4.1航班一机场网络.35图4.2邻接矩阵。.37图4.3路径矩阵2（21）.38图4.4邻接矩阵。）.38图4.5时空网络示意图.40图4.6曲线拟合结果.50viii图6.1 一体化恢复Benders，分解算法流程图78IX第一章绪论1.1 研究背景和意义随着国民经济的高速发展和航空运输市场需求量的不断增长，国内航线网络不断扩充，航 班密度不断提高，同时各航空公司也相应加大了运力的投入，航班计划的编制随着计算机功能 的增强也越来越紧凑。这些都导致航班延误正在大幅度提高，不正常航班给航空公司带来了巨 大的成本损失，也给旅客造成了诸多不便。不正常航班计划恢复问题是世界各航空公司面临的 难解问题，美国Delta航空公司统计了 95000起不正常航班，影响到850万旅客，损失近五亿 美元（不包括旅客满意度的损失），平均一起不正常航班带来的损失就高达5200多美元，这 还不包括航班延误给旅客造成的损失。我国三大航空集团2008年共执行航班1492031班，其中 不正常航班258866班，航班不正常率为17.35%，如果按照Delta航空公司的统计，平均延 误一个航班损失5200美元，三大航空集团2008年因航班延误的损失就达13亿美元。为了减少 航班延误，航空公司在制订航班计划时，预留充分的过站时间，给航班扰动一定的缓冲，这样 虽然减少了航班延误率，但过长的过站时间也造成了资源的大量闲置浪费。这也是三大航空集 团虽然垄断了大部分航空市场，但利润一直不高，甚至出现亏损的一大原因。据2008年统计年 鉴，我国目前共有21家中小航空公司，像山东航空公司，上海航空公司，深圳空公司等等，还 有一些私营的航空公司，像春秋航空公司等，共执行航班176785次，其中不正常航班数39126 次，航班不正常率为22.13%,为了提高服务质量，在夹缝和困境中生存下去，提高航班正常率 是目前这些航空公司最期待解决的问题。民航运输业面临着激烈的竞争和挑战，一方面来自于公路、铁路运输业，另一方面来自于 航空公司之间地竞争，为了应对激烈的市场竞争，在制订航班计划时，航空公司面临着两难的 选择，要么是充分利用飞机、机组和航线资源，设计最合理的飞机路线和制定最紧凑的机组任 务，尽量减少航班过站时间，保证资源的最大化利用，以降低运营成本；要么就是为应对各种 意外的变化留下足够的缓冲时间，以减少航班延误。由于航空公司资源的闲置成本极高，航班 之间预留的缓冲时间越高，意味着资源的闲置时间越长，这种资源浪费是航空公司难以容忍的，且航班计划的运行环境是动态变化的，如恶劣天气、机务故障等等都会导致航班不正常情况的 发生，即使是预留了足够的缓冲时间，也无法保证航班总是能够按照计划运行。航班不正常是 必然会发生的，只有积极的应对才是正确的选择，航空公司设立了运行控制部（以下简称运控 中心），对不正常航班计划恢复工作负责，当航班不正常情况发生之后，运控中心需立即作出 反应，给出调整方案，做出实时性的决策，以最小的成本代价，通过重新调配飞机、机组，推 1迟或取消航班等，在给定的时间区间内（通常要在当天机场关闭之前）恢复航班计划，这个过 程就是不正常航班计划恢复。航空资源的昂贵性要求资源最大限度被利用，然而航空运输过程 中的不确定性却总是打乱精心制定的资源利用计划，不正常航班计划恢复似乎是航空公司必须 永远面对的问题，对不正常航班计划恢复问题的研究会一直存在，并随着民航运输规模的扩张,显示出更加重要的地位。对于航空公司来说，不正常航班运行成本占年收入的3%,因此可以优化的潜能和空间是明 显的，航空公司航班正常率的高低与公司盈利水平存在很大关系，航班正常性保持较好的航空 公司盈利水平也较强。美国西南航空公司的航班正常率一直保持在美国航空运输统计的前五 名之内，正常率在80%以上，同时它的盈利能力也在18%以上，这是很多航空公司梦寐以求的 骄人业绩。由于航空业的特点和竞争的需要，航空公司的航班运行控制对运筹学的许多分支理论和方 法，特别是最优化技术有着非常迫切的需求。随着航空运输业内部和外部竞争地加剧，我国三 大航空公司先后从美国萨伯公司（SABRE）引进了全套运行控制系统，旨在提高公司对航班运 行监控和管理的信息化水平，但由于内部管理体制、航线结构、机组薪酬制度等的不同和不正 常航班计划恢复系统的复杂性和面向对象的特定性，信息系统的优势没有充分发挥出来，斥巨 资引进的优化系统几乎成了摆设或者手工操作替代品。我国不正常航班计划恢复的研究目前还 处于初级发展阶段，没有可以供航空公司使用的成型软件产品。随着民航局对不正常航班管理 的加强，提高不正常航班的运行控制现代化水平也越来越引起各航空公司重视，优化控制、算 法设计、管理创新必将成为不正常航班计划恢复问题研究的热点。1.2 研究目标及主要内容不正常航班计划恢复问题是一个实时大规模整数规划问题，其变量复杂，难解约束条件多，目前精确求解该问题还非常困难巴 由于不同航空公司运作机制的差异，某些大型航空公司资 助开发的软件在通用性上还存在问题，由于技术的保密性，市场上也很难得到这样的软件。我 国不正常航班计划恢复系统的研究尚处于起步阶段，自动化航班计划恢复系统严重缺乏，目前 尚无成功开发、应用的案例，航班计划恢复全凭签派人员开现场会研究，依靠经验手工操作。面对庞大的昂贵资源和复杂的限制条件，凭经验很难满足资源的优化利用和航班计划恢复的实 时性要求。研究不正常航班计划恢复模型和优化算法，实现自动化恢复软件的开发，成为目前 我国航空公司迫在眉睫的当务之急。论文的目标就是为加速我国航空公司不正常航班计划恢复 系统的自动化和现代化进程服务，构造适合我国航空公司运作特点的不正常航班计划恢复模型 和算法，在航班计划受到干扰后尽快使其恢复正常，提高航空公司处理不正常航班问题的能力，降低航空公司的延误成本，最大限度的减少航班延误或取消地影响范围。2这篇论文的主要内容是对我国航空公司不正常航班计划恢复问题建立数学模型并设计求解 算法。论文的篇章安排按照问题的解决流程和研究进展进行。首先回顾了不正常航班计划恢复 问题的研究现状，为全文的展开奠定理论基础；论文的研究工作是以我国航空公司航班计划恢 复为背景，通过对我国某大型航空公司的航班计划恢复实际情况进行了详细调研，总结了运控 中心工作经验和航班计划恢复流程，为数学模型构建和算法设计奠定实践基础；取消航班决策 是运控中心经常面对的一个决策问题，论文单独为航班取消问题构造了模型和算法；飞机路线 恢复问题和机组恢复问题是不正常航班计划恢复的两个主要部分，文中辟出了大量章节进行详 细讨论，给出了相应的模型和算法；目前对不正常航班计划恢复问题的研究是大部分是分阶段 进行的，先进行飞机路线恢复，然后是机组恢复，最后把旅客指派到恢复过的航班上，这种分 阶段恢复方法相对简单，但存在缺陷：当后一阶段无法找到可行解时，前一阶段的恢复方案将 无法执行。如果能将三个阶段放在一个模型中，同时安排这三种资源在航班计划上的指派，就 能获得全局的优化方案，得到完整意义上的航班计划恢复方案，本着这个目的，论文研究了一 体化航班计划恢复问题，给出了一体化恢复数学模型，并设计了求解算法。飞机路线恢复问题主要内容分三部分讨论，第一部分是单纯航班取消问题，航班取消是不 正常航班调整中经常遇到的一个问题，如何取消航班才能保证航空公司损失最小，本文给出了 解决方案；第二部分是飞机路线恢复问题，飞机路线恢复问题是典型的资源指派问题，论文从 目标函数、约束条件两个方面改进了资源指派数学模型：目标函数方面，从旅客角度和航空公 司角度设计了两种不同的目标函数：一是旅客延误总时间最小，二是航空公司总损失最小。旅 客延误总时间最小目标函数中引入了延误权重因子，在保证总延误时间最短的情况下克服了少 数航班被分配长时间延误的不足;航空公司总损失最小目标函数将不正常航班损失细分为四类,并首次引入了旅客失望溢出成本的概念。约束条件中增加了机场设施设备和天气条件对飞机的 起降约束、舱位数约束、飞机当天飞行任务结束后的定检约束和重要航班优先保证约束。提出 了逐延误指派算法对模型求解，逐延误指派算法按照签派人员调整航班的思路启发式地恢复飞 机路线，可快速获得问题的优化解；通过对两种不同的目标函数对比求解，获得的结果具有显 著不同，为航空公司设计航班计划恢复目标提供了数据证明，测试数据同时也显示了该算法能 够获得比签派人员手工调整优化、高效的恢复方案。机组作为航空公司第二个重要资源，在飞机路线恢复完成后，如果机组无法到位，航班会 依旧延误。机组恢复就是给完成了飞机指派的航班分配机组，属于集合覆盖问题范畴，采用集 合覆盖问题对机组恢复建立数学模型，以机组资源浪费最小化作为目标函数，保证所有航班都 能被机组覆盖，机组不允许超时。给出了机组恢复的蚁群算法的详细求解步骤，案例测试显示,设计的模型和算法能够满足机组恢复的实际要求。3一体化航班计划恢复是不正常航班计划恢复研究的难点，也是世界各航空公司最期待解决 的课题。本文构建了一体化的不正常航班计划恢复模型，面对异常复杂的变量和约束条件，直 接求解无疑是非常困难的，文中采用Benders，分解算法将一体化航班计划恢复问题分解为主问 题和飞机恢复(ARM)、机组恢复(CRM)、旅客恢复(PRM)三个子问题，给出各个子问题的对偶 问题和子问题的求解方法，将子问题求解获得地可行割或优化割反馈回主问题中，逐步迭代直 到获得主问题的最优解。作为研究的国际前沿，虽然是第一次尝试用程序实现一体化航班计划 恢复问题，计算机运行显示获得了较为满意的结果。全文共分为七章：第一章，绪论。首先陈述本论文的研究背景和研究意义，主要研究内容、研究方法和技术 路线，旨在为整个研究的展开作好铺垫。第二章，不正常航班计划恢复相关文献的综述。综述了不正常航班计划恢复问题数学模型 及算法的发展历程、研究现状及前沿动态，力图理清各个研究分支之间的关系，建立起完整的 不正常航班计划恢复问题研究框架，进而为后面内容的展开奠定理论基础和研究依据。第三章，对航空公司运控中心不正常航班调整进行了深入调研，理清了签派员日常恢复航 班计划的思路和流程；简单介绍时空网络和常见的不正常航班恢复问题数学模型，为后面模型 和算法的研究奠定实践基础。第四章，给出了解决飞机路线恢复的模型和算法第五章，探讨了机组恢复问题模型和算法。第六章，研究了不正常航班一体化恢复模型和算法。第七章，全文总结与研究展望。结合本论文的研究情况，概述论文的主要工作和创新点，以及论文的不足之处和未来的研究方向。L3研究方法与技术路线全文通过理论分析、实际调查、流程分析、模型建立与求解、实例分析论证等对不正常航 班计划恢复问题进行了探讨。以理论研究为主，通过对实际问题的抽象和工作流程的研究，建 立数学模型，设计求解方法。数学模型采用机场一航班时空网络为基本的建模工具，并设计不 同的算法对模型求解。飞机路线恢复中的单纯取消航班问题，设计了基于Floyd-Wallshall的取 消航班算法；对飞机路线恢复问题，采用逐延误指派算法，这是按照签派人员恢复航班计划的 流程设计的一种启发式算法。机组恢复问题采用集合覆盖问题建模，求解采用蚁群算法。一体 化恢复问题以时空网络为设计基础，采用Benders，分解算法、约束最短路算法等基本理论和方 法为依据设计求解方法。4实践方面采用去航空公司跟随签派员值班、亲自参与航班计划恢复过程、访问、开座谈会 等形式，了解解决不正常航班计划恢复问题的方法、经验和规则，并将其抽象成目标函数和约 束条件，为数学模型的描述和约束条件的表达奠定基础；不同原因导致的不正常航班计划恢复 流程在签派人员眼里是复杂多变的，将这些流程以框图的形式表达出来，并归纳总结，在调研 的过程中反复修改，直到获得签派人员的一致认同，为算法的设计奠定基础。采用C+作为编程语言，对设计的算法编写了相应的计算机程序，以航空公司提供的案例 作为测试数据。文章的研究工作按如下步骤进行：（1）充分利用现有研究成果，继承与创新相结合。（2）在认真收集、挖掘、整理数据信息和仔细研究问题特点的基础上，构建数学模型，提 炼数学算法。（3）数学模型的建立遵循因素分析、指标量化、优化建模的步骤。（4）验证算法的合理性、实用性和有效性。（5）认真总结所提出的模型的优点及不足，明确所面临的挑战，以及进一步的研究方向。5第二章不正常航班计划恢复问题研究综述由于恶劣天气、航空管制、机务故障等原因常常导致航班计划无法正常执行，称为航班计 划不正常，也称作航班计划扰动(Perturbation)或干扰(Disruption)o为使航班计划恢复正常 运作，航空公司需要对航班计划(Flight schedule)、飞机路线(Aircraft Routing)、机组排班(Crew Scheduling)维修计戈tl(Maintenance Scheduling)旅客路线(Passenger Itinerary)及地面保障资源等进行调度和恢复，使原计划的航班任务能够顺利执行，飞机和机组能够到达 原计划应该到达的机场，旅客能够顺利到达目的地，这些统称为航空公司不正常航班计划恢复 问题(Airline Irregular Flight Recovery Problem)o不正常航班计划恢复通常是分阶段进行的：首先是飞机计划恢复(Aircraft Schedule Recovery,ASR),主要是通过最小化延误和取消航班的决策达到，第二阶段是机组恢复(Crew Recovery),通过重排机组计划和使用备份机组，使航班任务的执行满足民航管理局的安全规定 和机组人员不超时规定；第三阶段是旅客路线恢复，将旅客指派到相应的航班上，使之能够到 达预定的目的机场。采用这种恢复次序是因为飞机是航空公司里最昂贵的资源，而机组相对更 容易获得，可以通过使用备份机组(Reserve)和加机组方式(Deadhead)的方式获得更多机组，重新安排机组计划。航空公司经常面临不正常航班计划恢复的实时调度问题，如何在有限的昂贵资源中调配飞 机，而且保证后续航班有飞机可用，机组到位，还要兼顾飞机定期维修的要求，第二天的飞行 计划不能被打乱，机组不能超时，旅客路线保证衔接等等诸多的约束条件，同时还要使航班延 误和取消成本最小，公司损失最低，这诸多的限制因素和庞大的飞机、机组和航班数量，要求 签派人员必须在短时间内做出反应，给出航班计划恢复方案。无论对航空签派人员和研究人员，这无疑都是巨大的挑战，因为问题的复杂度和求解要求的实时性，目前国际国内还没有完全自 动化的航班计划恢复商业软件可以使用，虽然面临诸多困难，但还是有不少前辈和新人对不正 常航班计划恢复问题怀着极大的兴趣进行系统的研究。需要指出的是，在现有的研究成果中，绝大多数的文章研究的计划恢复只限于一个航空公司的范围，考虑多个航空公司合作条件的文 献极少，本文也是以一个航空公司的航班计划为讨论范围。对航班计划恢复问题的研究以 Teodorovic、Stojkovic Ahmad Jarrah Gang Yu、Jonathan F.Bard、Micheoal Clarke、Ellis Johnson、Cynthia Barnhart 为代表的教授学者 及他们的博士生为主。6Teodorovic和Stojkovic是前南斯拉夫Yougoslavie Belgrade大学交通运输学院的教授，是较早研究航班排班和不正常航班计划恢复的学者。Gang Yu曾经在奥斯丁得克萨斯大学McCombs商务学院管理学院，致力于不正常航