| 分布式整数规划及其在航线扰动问题的应用 |
| |
| 引用本文： | 李奔驰,党创寅,郑津津. 分布式整数规划及其在航线扰动问题的应用[J]. 计算机工程与应用, 2013, 49(14): 19-24 |
| |
| 作者姓名： | 李奔驰 党创寅 郑津津 |
| |
| 作者单位： | 1.中国科学技术大学 精密机械与精密仪器系，合肥 230026 2.香港城市大学 系统工程及工程管理学系，香港 999077 |
| |
| 摘 要： | 在航空公司的运作中时常会出现干扰它正常运作的现象。在这种情况下，航空公司必须马上制定航线修复计划使受到干扰的航线尽快复原，以防止更大面积的航班取消和航班延误。提出一种基于递增映射迭代方法的分布式整数规划算法来解决由于机场关闭引起的航线扰动问题。整个问题分成了两个子问题：可行航线的生成和飞机的重指派。第一个子问题的问题空间被初始点分割方法分割成了若干片段。然后在一个分布式的计算网络中使用递增映射迭代方法在分得的每个片段上同时求解第一个子问题。得到的可行航线用来求解第二个子问题。最后的算例结果可以发现提出的方法要好于CPLEX和多目标基因算法。
|
| 关 键 词： | 航空扰动管理 不正常调度 整数规划 分布式计算 字典序 消息传递接口（MPI） OpenMP |
Distributed-computation approach to integer programming and its application in airline disruption problems |
| |
| LI Benchi,DANG Chuangyin,ZHENG Jinjin. Distributed-computation approach to integer programming and its application in airline disruption problems[J]. Computer Engineering and Applications, 2013, 49(14): 19-24 |
| |
| Authors: | LI Benchi DANG Chuangyin ZHENG Jinjin |
| |
| Affiliation: | 1.Department of Precision Machinery and Precision Instrumentation, University of Science and Technology of China, Hefei 230026, China2.Department of Systems Engineering and Engineering Management, City University of Hong Kong, Hong Kong 999077, China |
| |
| 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. |
| |
| Keywords: | airline disruption management irregular operation integer programming distributed computation lexicographical order Message Passing Interface（MPI） OpenMP |
|
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
