使用多计算机分布式整数规划求解飞机运行计划修复问题

摘要

在航空公司的运作中时常会出现干扰航空公司正常运作的现象。当干扰现象发生的时候，航空公司必须马上制定航线修复计划使受到干扰的航线计划复原到原计划，以防止更大面积的航班取消和航班延误。考虑到航线运行计划是由飞机运行计划，机组人员排班计划以及乘客乘机计划三部分组成，因此整个航线扰动问题需要修复飞机运行计划，修复机组人员排班计划以及乘客乘机计划。这三个问题对于各自来说都是非常复杂的问题，由于修复飞机运行计划是修复整个航线计划中最重要的一个环节，因此本论文主要研究飞机运行计划的修复。
　　 本文提出一种分布式整数规划算法来解决航线扰动问题。首先将此问题建模形成两子问题:可行航线的生成和飞机重指派。对于第一个可行航线生成的子问题，本文分别提出了两种不同的模型，第一个是模型是基于机场连接网络建立起来的，第二个模型是通过修改旅行商问题(TSP)建立起来的。当求解这两个模型中任意一个模型前，本文提出了两个分割方法分别用来把第一个子问题的问题空间分割成若干个独立片段。然后提出一种分布式整数规划算法用来在这些独立的片段上求解生成可行航线。之后用这些得到的可行航线用来解决第二个子问题，即飞机重指派问题。
　　 新可行航线的生成是基于原航线的，并且可以同时按照比原航线字典序大和比原航线字典序小的两个方向来生成。对于按照比原航线字典序大的方向来说，每一个新生成的可行航线都比之前刚生成的航线字典序大。对于按照比原航线字典序小的方向来说，每一个新生成的可行航线都比之前刚生成的航线字典序小。所以先生成的可行航线相比原航线比后生成的可行航线相比原航线，改变更小。对于一个非常大的航线扰动问题来说，想在理想时间把可行航线全部算出来是几乎不可能的事情。所以在每个求解独立片段上，只生成了部分可行航线。
　　 文献Argüello et al.[1], Argüello[2], Thengvall[3], Liu et al.[4], Babic et al.[5]and Andersson and V(a)rbrand[6]中的航线运行计划表被用来测试本文提出的求解方法。通过比较分布式整数规划算法生成的可行航线和CPLEX CP Optimizer生成的可行航线，可以发现分布式整数规划算法比起CPLEX CP Optimizer更有能力生成能组成飞机重指派方案的可行航线。再通过比较分布式整数规划算法生成的可行航线求得的飞机重指派方案和文献中给出的飞机重指派方案，可以发现本文提出的方法不仅可以求出文献中给出的飞机重指派方案，还能求解出比文献中给出的那些方案更好的飞机重指派方案。

目录

声明

摘要

第1章 绪论

1．1 研究背景和动机

1．1．1 制定航线运行计划过程

1．1．2 航线调度控制组

1．1．3 航线运行计划扰动概括

1．1．4 研究动机

1．2 运筹学的应用

1．2．1 运筹学在航空公司管理中的应用

1．2．2 运筹学在曲面造型中的应用

1．3 文献综述

1．3．1 航线扰动问题综述

1．3．2 整数规划综述

1．4 论文组织结构和贡献

第2章 飞机运行计划修复问题数学模型

2．1 飞机运行计划修复问题综述

2．1．1 由飞机停飞引起的扰动

2．1．2 由机场关闭引起的扰动

2．2 数学模型

2．2．1 可行航线的生成

2．2．2飞机重指派

第3章 基于Dang迭代方法的多机分布式整数规划算法

3．1 两种求解整数规划的迭代方法

3．1．1 迭代方法一

3．1．2 迭代方法二

3．1．3 应用于求解出所有的整数点

3．2 迭代方法的分布式计算

3．2．1 准平均分割法

3．2．2 基于初始点的串分割法

3．2．3 分布式计算的实现

第4章 算例分析

4．1 单机型飞机停飞问题

4．1．1 机型757结果

4．1．2 机型737-100结果

4．1．3 计算效率

4．2 单机型机场关闭问题

4．2．1 机型MD-90结果

4．2．2 机型DH-8结果

4．2．3 计算效率

4．3 多机型飞机停飞问题

4．3．1 欧洲中型航线结果

4．3．2 瑞典国内航线结果

第5章 总结与展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果