分布式整数规划及其在航线扰动问题的应用  

Distributed-computation approach to integer programming and its application in airline disruption problems

作　　者：李奔驰[1,2] 党创寅[2] 郑津津[1] 

机构地区：[1]中国科学技术大学精密机械与精密仪器系,合肥230026 [2]香港城市大学系统工程及工程管理学系,香港999077

出　　处：《计算机工程与应用》2013年第14期19-24,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.10979065;No.61073109);香港研究资助局优配研究金(No.CityU 112809);111引智工程(No.B07033)

摘　　要：在航空公司的运作中时常会出现干扰它正常运作的现象。在这种情况下,航空公司必须马上制定航线修复计划使受到干扰的航线尽快复原,以防止更大面积的航班取消和航班延误。提出一种基于递增映射迭代方法的分布式整数规划算法来解决由于机场关闭引起的航线扰动问题。整个问题分成了两个子问题:可行航线的生成和飞机的重指派。第一个子问题的问题空间被初始点分割方法分割成了若干片段。然后在一个分布式的计算网络中使用递增映射迭代方法在分得的每个片段上同时求解第一个子问题。得到的可行航线用来求解第二个子问题。最后的算例结果可以发现提出的方法要好于CPLEX和多目标基因算法。The operation of an airline schedule often deviates from the original planned schedule due to some disruptions hap- pen. In this situation, the airline must be able to get back to the original schedule by producing recovery plan as quickly as possi- ble. This paper proposes a distributed implementation of an iterative method for integer programming to solve the airline disrup- tion 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.

关 键 词：航空扰动管理 不正常调度 整数规划 分布式计算 字典序 消息传递接口(MPI) OPENMP 

分 类 号：U8[交通运输工程]