Abstract: The operation of an airline schedule often deviates from the original planned schedule due to some disruptions happen. In this situation, the airline must be able to get back to the original schedule by producing recovery plan as quickly as possible. This paper proposes a distributed implementation of an iterative method for integer programming to solve the airline disruption problems caused by the airport closures. The problem is formulated as two sub problems： feasible flight routes generation and aircraft reassignment. The solution space of the first sub problem is divided into several segments by the initial seeds cluster division method. The iterative method is applied to solve the first sub problem in each segment simultaneously in a distributed computation network, and the resulting feasible flight routes are used to construct an aircraft reassignment which is the second sub problem. Numerical results show that the proposed approach performs better than CPLEX and multi-objective genetic algorithm.

Key words: airline disruption management, irregular operation, integer programming, distributed computation, lexicographical order, Message Passing Interface（MPI）, OpenMP

摘要： 在航空公司的运作中时常会出现干扰它正常运作的现象。在这种情况下，航空公司必须马上制定航线修复计划使受到干扰的航线尽快复原，以防止更大面积的航班取消和航班延误。提出一种基于递增映射迭代方法的分布式整数规划算法来解决由于机场关闭引起的航线扰动问题。整个问题分成了两个子问题：可行航线的生成和飞机的重指派。第一个子问题的问题空间被初始点分割方法分割成了若干片段。然后在一个分布式的计算网络中使用递增映射迭代方法在分得的每个片段上同时求解第一个子问题。得到的可行航线用来求解第二个子问题。最后的算例结果可以发现提出的方法要好于CPLEX和多目标基因算法。

关键词: 航空扰动管理, 不正常调度, 整数规划, 分布式计算, 字典序, 消息传递接口（MPI）, OpenMP