论文总字数：35321字

摘 要

台风、雾霾、雷暴或飞机故障等因素常常导致机场出现大面积航班延误的情况，对航空公司的运营和乘客的正常安全出行造成影响。由于大面积航班延误问题中涉及到的机场、航班、飞机及旅客等数据量庞大，约束关系复杂且多变，目前这一问题还没有通用的解决方案。随着我国航空事业的蓬勃发展，针对恶劣天气下航班的应急恢复规划逐渐成为研究的热点。

本文首先以飞机路线恢复、机组恢复、机场整体恢复三个切入点介绍国内外研究现状。其次针对航班恢复问题，建立时空网络模型并通过算法进行实现。同时，考虑到NP-Hard问题的复杂性和特殊性，分别从飞机路径、航班时间调整、乘客整体分派三个方面建立分布式航班应急规划模型，利用启发式算法进行求解。求解算法主要包括动态延误路径求解算法和基于贪婪算法的航班时间调整方案。随后，以国内某航空公司提供的数据为例，对2365条航班信息，8694条航线限制信息，8704条飞行时间信息以及12个台风场景进行恢复运算，模型求解效果较好，算法得到验证。最后，本文提出了一种基于列生成算法的航班恢复模型改进思路，对航班应急恢复背景下的限制主问题及子问题进行描述，并对小规模案例进行算法验证。

关键词：恶劣天气，航班应急恢复，时空网络模型，启发式算法，列生成算法

Abstract

Typhoons, haze, thunderstorms or aircraft failures often lead to large-scale flight delays at airports. This will affect the operation of airlines and the normal safe travel of passengers. Due to the huge amount of data related to airports, flights, airplanes and passengers, and the complex and changeable constraints, there is no universal solution to this problem. With the vigorous development of China's aviation industry, emergency recovery planning for flights under severe weather has gradually become a research hotspot.

Firstly, This paper introduces the research status at home and abroad from three aspects: aircraft route recovery, crew recovery and airport overall recovery. Then, aiming at the problem of flight recovery, the spatio-temporal network model is established and programmed.At the same time, considering the complexity and particularity of NP-Hard problem, a distributed flight emergency planning model is established from three aspects: aircraft routing, flight time adjustment and passenger assignment.The heuristic algorithm is used to solve the problem. The algorithm mainly includes delay-by-delay path algorithm and flight time adjustment scheme based on greedy algorithm. Subsequently, taking the data provided by a domestic airline as an example, 2 365 flight information, 8694 route restriction information, 8704 flight time information and 12 typhoon scenarios are restored. The results show that the model is effective and the algorithm is validated. Finally, this paper proposes an improved flight recovery model based on column generation algorithm, describes the main and sub-problems of constraints in the context of flight emergency recovery, and validates the algorithm for small-scale cases.

KEY WORDS: Extreme Weather, Flight Recovery, Spatio-temporal Network Model, Heuristic Algorithm, Column Generation Algorithms

目 录

摘要 I

Abstract I

第一章 绪论 1

1.1 研究背景和意义 1

1.2 研究目标及主要内容 3

1.3 研究方法及技术路线 4

第二章 航班应急恢复研究综述 6

2.1 飞机路线恢复问题 6

2.2 机组恢复问题综述 7

2.3 一体化恢复问题综述 8

第三章 航班恢复模型及算法设计 10

3.1 案例说明 11

3.2 时空网络模型的建立 14

3.2.1 时空网络模型 14

3.2.2 时空网络模型的算法实现 17

3.3 规划模型的建立及算法设计 18

3.3.1 分布式模型的建立 18

3.3.2 启发式算法设计 22

3.4 算法实现及求解 25

第四章 基于列生成算法的模型改进思路 28

4.1 列生成算法背景知识 28

4.1.1 算法术语 28

4.1.2 算法思路 28

4.2 航班恢复模型改进 29

4.2.1 限制主问题的建立 30

4.2.2 限制主问题的初始解 30

4.2.3 限制主问题的求解步骤 30

4.2.4 子问题的建立 31

4.3 航班应急恢复案例分析 31

第五章 总结与展望 36

5.1 论文总结 36

5.2 课题展望 36

参考文献 37

致 谢 38

附 录 39

绪论

研究背景和意义

随着科学技术的进步和交通工具的升级，越来越多的人在日常生活中选择飞机这一出行方式。但是受到各种因素的影响，航班往往会出现延误的情况，不仅影响了乘客的正常出行，也对航空公司的运营提出了挑战。

据2018年民航机场生产统计公报^[1]显示，我国422家航空企业共完成1108.8万架次航班起飞，而航班的平均正常率不到八成。航班延误不仅会打乱航空公司的正常排班计划，更会造成公共交通资源的浪费，如果情况严重甚至会扰乱社会公共秩序。造成航班延误的原因有很多，航班延误可能是多种随机因素和部分可控因素的共同作用。据统计资料显示，造成延误的各主要原因和占比如下图所示。

剩余内容已隐藏，请支付后下载全文，论文总字数：35321字