【作者】 赵秀丽；

【导师】 朱金福；

【作者基本信息】 南京航空航天大学 ， 交通运输规划与管理， 2010， 博士

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

【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 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. 3) 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 Benders’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.更多还原