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

Abstract:  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.

Key words: flight recovery problem, iterated local search, simulated annealing, connecting flight, aircraft route