飞机计划恢复的混合集合规划方法研究

Research on Mixed Set Programming for Aircraft Schedule Recovery

恶劣天气和机械故障等原因造成航班不能正常运行,航空公司需要重新安排飞机路线和受扰航班的起降时间.不正常航班的飞机计划恢复问题是一个典型的NP-Hard问题,为解决这一问题,采用混合集合规划方法,引进更一般的约束条件,建立了自然约束语言模型,设计简洁且高效的求解策略,实现了多机型的飞机计划恢复.最后对各种规模的实例进行了测试,并与贪婪模拟退火算法进行比较,表明了这种方法在求解质量和时间效率上的优越性.

Imclement weather, mechanical failures often prevent airlines from executing their schedules as planned, and will bring about a lot of losses to airlines and passengers. To recover the schedule, the decision makers must reroute the aircrafts and re-time the disturbed flights. Aircraft Schedule Recovery problem is a typical NP-Hard problem in Irregular Flight Operation. This paper proposes a mixed set programming method to solve the problem by building a natural constraint language model and designing efficient search rules. Finally, instances of different scales are tested respectively using the mixed set programming and greedy simulated annealing algorithm, which shows the superiority of mixed set programming method in solution quality and time efficient over greedy annealing algorithm.