航班恢复优化算法研究.caj

航班恢复优化算法研究
作者 : 肖晚霞
学位授予单位 : 北京交通大学
学位名称 : 硕士
导师姓名 : 董兴业
学位年度 : 2019
关键词 : 航班恢复问题；整数规划；迭代局部搜索；模拟退火；联程航班；飞机路线
摘要 : 恶劣天气和机械故障等原因常常造成航班不能按照原计划执行,扰乱了航空公司的正常运营,从而提出了航班恢复问题。由于该问题有迫切的现实需求,且是一个具有多变量和复杂约束的组合优化问题,所以吸引了许多研究者的关注。目前,虽然对该问题的研究取得了许多成果,但随着航空业的不断发展,现有模型和优化方法存在考虑的约束条件和恢复策略不够全面、求解大规模航班恢复问题效率低等问题,同时航空公司又提出了新的需求,包括处理联程航班、采用调机策略等。为了解决这些问题,本文考虑联程航班拉直及包括调机策略在内的五种恢复策略,对航班恢复问题的模型及优化方法进行了研究,并提出了新的模型及优化算法。包括以下几个方面:第一,基于每架飞机执行一个航班后可衔接的航班数有限的思想,提出通过建立航班恢复网络设计整数规划模型的求解方法。由于构建的恢复网络的变量和节点众多,提出了一种可行方案发现算法对网络中的节点和弧数据进行约减,使网络中的变量更有利于模型的构建。实验结果表明,本文提出的整数规划模型能有效地解决小规模航班恢复问题,但由于求解速度慢,无法在可接受时间内对大规模问题进行求解。第二,为解决大规模航班恢复问题求解效率低下的问题,根据航班恢复问题的特点和约束条件,在经典的资源指派模型的基础上增加了联程拉直约束,建立了基于飞机路径的航班恢复优化模型。该模型综合考虑了调整时间、换飞机、联程拉直、取消航班和调机五种恢复策略,以最小化恢复总成本为优化目标。为求解该模型,提出了一种基于迭代局部搜索的求解算法。在算法的设计过程中,为满足资源平衡约束,提出了一种构造-修复启发式方法构造问题的初始解;为提高搜索效率并降低陷入局部最优的概率,设计了六种邻域算子构造飞机路线对的邻域,并采用模拟退火算法对该邻域进行搜索;然后为了在扩大搜索空间的同时保证扰动后的解满足约束条件,设计了一种新的扰动策略。在某航空公司提供的实际航班数据上的实验结果表明,对于大规模的航班恢复问题,本文设计的基于迭代局部搜索的求解算法可以在较短的时间内获得恢复方案,同时可以有效地降低航班计划中断造成的损失成本。