航班恢复问题的迭代局部搜索算法  

An Iterated Local Search Algorithm for Aircraft Recovery Problem

作　　者：肖晚霞 董兴业[1,2] 林友芳 XIAO Wan-xia;DONG Xing-ye;LIN You-fang(School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China;Beijing Key Laboratory of Traffic Data Analysis and Mining,Beijing 100044,China)

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044 [2]交通数据分析与挖掘北京市重点实验室,北京100044

出　　处：《计算机与现代化》2019年第9期1-6,共6页Computer and Modernization

基　　金：中央高校基本科研业务费专项资金资助项目(2017JBM027)

摘　　要：在恶劣天气和机械故障等原因造成航班不能按照原计划执行时,航空公司需要采取相应的措施对航班进行恢复。本文基于经典的资源指派模型,综合考虑了调整时间、换机、联程拉直、取消航班和调机5种恢复策略,提出一种以最小化加权成本为优化目标的航班恢复模型,并设计一种迭代局部搜索算法。首先用构造-修复启发式方法构造可行解,然后从该初始解出发,在飞机路线对的邻域中进行局部搜索。当陷入局部最优后,对解进行扰动,然后从扰动后的解重新出发进行局部搜索。为了提高搜索效率,同时降低陷入局部最优解的概率,局部搜索过程采用模拟退火算法。实例结果表明,本文提出的模型及算法能够在短时间内对受到影响的大规模航班计划进行恢复。Airlines are required to take corresponding measures to recover the flights when they cannot be implemented as original plan due to certain disturbations.This paper puts forward a flight recovery model based on the classical resource assignment model,taking into account five recovery strategies,i.e adjusting time,changing aircraft,adjusting connecting flight,cancelling flight and deadhead flight.The model minimizes total weighted cost and an iterative local search algorithm is designed.Firstly,the feasible solution is constructed by construct-repair heuristic method,and then the local search is carried out from it in a multi-neighborhood of the aircraft route.When the search is trapped into a local optimum,the current solution is disturbed,and then the local search is performed again from the disturbed solution.To accelerate the local search and reduce the probability of falling into the local optimal,a simulated annealing algorithm is used.Experimental results demonstrate that the proposed model and algorithm can recover the large-scale flight schedule that is affected in a short time.

关 键 词：航班恢复问题 迭代局部搜索 模拟退火 联程航班 飞机路线 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]