基于并行GRASP的不正常航班调度算法

Irregular Flight Scheduling Algorithm Based on Parallel GRASP

将并行计算与GRASP结合,设计了一种新的基于并行GRASP的不正常航班调度算法,给出了详细的算法流程与步骤;同时考虑了使用备用飞机、延误航班与取消航班等不正常航班调度策略,通过并行GRASP算法优化了构造的飞机路线和取消路线组成的初始解,给出了每架飞机新的航班路线和航班取消路线。国内一家中等规模航空公司实际算例的结果证明了算法能有效降低以往算法的时间复杂度,明显提升运算效率,可用于较大规模的不正常航班调度运算。

In order to improve the efficiency of algorithms for disrupted airline schedules and reduce the time complexity of those algorithms, this paper introduces parallel computing and GRASP（ Greedy Randomized Adap- tive Search Procedure） into optimization of irregular flight scheduling. A new irregular flight scheduling algorithm based on parallel GRASP is proposed, which considers such a scheduling policy as spare planes, delaying flights and cancelling flights. The initial solution constructed for irregular flight by flight cancellations and flight delays is optimized by the parallel GRASP algorithm, and the new flight route and route of flight cancellations of each plane is presented in this paper. An example of a medium scale airlines flight plan is given to demonstrate the validity and feasibility Of the scheduling algorithm. The results show that the new algorithm is significantly higher and more efficient in solution time than serial GRASP algorithm and can also solve a large-scale irregular flight problem effectively.