基于深度优先搜索算法的机组复原研究

Solving the Crew Recovery Problem by Depth First Search

现实中会有很多因素影响航空公司的时间表,例如恶劣的天气、飞机故障、航空管制等等。为了应对这些突发状况,航空公司不得不修改原来的时间表。在前人对航空复原研究的基础上,提出了一种机组复原的方法。该方法的模型考虑了原来的时间表、时间地点约束以及排班规则,算法采用了一种启发式算法——深度优先搜索,并调用Gurobi4.6.1求解。文章中的数据来源于国内某航空公司的真实数据。结果表明该方法适用于中小规模机组复原问题,有较高的效率。

In real life,an airline schedule is often disrupted by many factors,such as sever weather,aircraft maintenance problems,air traffic control,etc.On this account,airline conditioners have to revise the original flight schedules.Based on the previous researches on airline recovery,we present a formulation of crew recovery considering the original schedule,time,place and crew assignment rules.A depth first search,a kind of heuristic algorithm,is applied in solving this problem.We got the solution using Gurobi4.6.1.The data in this paper come from a domestic airline.The result shows that this method is quite efficient for small and medium-sized problems.