不正常航班恢复模型贪婪模拟退火算法研究.docVIP

不正常航班恢复模型的贪婪模拟退火算法研究 　　摘 要:为解决不正常航班恢复对航空公司带来的严重影响,研究了不正常航班恢复模型及其优化算法,对现有不正常航班恢复优化模型提出适当改进,重点设计了一种贪婪模拟退火算法。算法融合了GRASP和模拟退火算法的特点,提高了领域解的选择效率并且降低了陷入局部最优解的概率。实例证明这种算法可以处理大规模的不正常航班恢复问题,并且能够达到时间代价与结果质量的均衡。 　　关键词:不正常航班恢复;领域解;GRASP;模拟退火算法 　　中图分类号:F560 文献标识码:A 文章编号:1003-5192(2010)01-0066-05 　　 　　Research on Greedy Simulated Annealing Algorithm of 　　Irregular Flight Schedule Recovery Model 　　TANG Xiao-wei, GAO Qiang, ZHU Jin-fu 　　(College of Civil Aviation, Nanjing University of Aeronautics Astronautics, Nanjing 210016, China) 　　Abstract:Irregular flight schedule recovery is of great importance to the civil aviation industry. The model and optimization algorithm of irregular flight schedule recovery is researched in this Article. First proper improvement is made to the original model, and a new type of greedy randomized simulated annealing algorithm is designed. The new algorithm integrating the characteristics of simulated annealing algorithm and greedy randomized adaptive search procedure improves the efficiency of neighborhood selection and reduce the probability of falling into local optimal solution. Example proves that the algorithm is able to solve the problem of large-scale irregular flight schedule recovery, with the time cost suitable to the outcome quality. Key words:irregular flight schedule recovery; neighborhood; greedy randomized adaptive search procedure; simulated annealing algorithm 　　 　　1 引言 　　 　　不正常航班是指由于天气、机械故障、流量控制等原因,造成航班延误、备降或取消。据统计分析,我国2005年由于不正常航班引起的各类经济损失已经超过30亿元,同时造成巨大的社会影响。面对日益突出的不正常航班问题,社会各方面呼吁航空公司尽快采取有效解决措施。不正常航班的恢复首先是飞机计划恢复,第二阶段是机组恢复,第三阶段是旅客中转衔接恢复。关于飞机计划恢复的决策对航空公司的收益影响最大,因此这一步也是最重要的。本文讨论的不正常航班恢复指飞机计划恢复。 　　航空公司为提高市场竞争力和最大化利用飞机资源,对航班计划(包括飞机计划和机组计划)的优化进行了较多的研究,航班计划基本上没有为应对各种意外的变化留下足够的松弛时间(Slack Time)[1]。因为飞机资源的备份成本极高,没有一家航空公司愿意专门为应付航班计划变化而让一架飞机空闲待命。这是造成航班不正常情况下运力调配困难的主要原因之一。此外,航班计划的运作环境是不确定的,除了考虑飞机可用性、机组可行性和维修约束之外,机场跑道条件、高原地区飞行条件、航线限制等因素都会增加计划调整的复杂性。 　　刻画不正常航班恢复问题的准确模型和寻找优化算法一直是航空运筹学领域研究的热点,快速有效的算法对于解决航空公司随时可能发生的资源优化利用问题将会产生巨大的经济效