Research On Flight Recovery Optimization Algorithm

Due to bad weather and mechanical failures,flights often fail to follow the original plan,disrupting the normal operation of the airline,and thus raising the flight recovery problem.Because this problem has urgent practical needs and is a combinatorial optimization problem with multi-variable and complex constraints,it has attracted the attention of many researchers.At present,the research on this issue has achieved many achievements,but with the continuous development of the aviation industry,the constraints and recovery strategies considered by existing models and optimization methods are not comprehensive enough,and the solution efficiency for solving large-scale flight recovery problems is low.At the same time,new demands have been put forward,including the handling of connecting flights and adopting deadhead flight strategies.In order to solve these problems,this paper studies the flight recovery problem of five types recovery strategies including the connecting flight and deadhead flight strategy,and establishes the corresponding flight recovery model and optimization methods.The main contents are as follows:Firstly,based on the idea that each aircraft only can have a limited number of flights after executing a flight,an integer programming model is established through the building of a flight recovery network.Due to the large number of variables and constraints of the network,a feasible solution discovery algorithm is designed to reduce the nodes and arcs in the network,so that the variables in the network are more conducive to the construction of the model.The experimental results show that the integer programming model designed in this paper can effectively solve the problem of small-scale flight recovery,but due to the slow solving speed,large-scale problems cannot be solved in an acceptable time.Secondly,in order to solve the problem of inefficient in solving large-scale flight recovery problem,the recovery optimization model based on aircraft path is established.In this model,the connecting flight constraints are added into the classical resource assignment model,with the characteristics and constraints of the flight recovery problem considered.The model considers five types of recovery strategies:adjusting time,changing aircraft,adjusting connecting flight,cancelling flight and deadhead flight,to minimize the total cost of recovery as the optimization goal.An iterated local search algorithm is proposed to solve this model.In the process of algorithm design,in order to satisfy the resource balance constraints,a construction-repair heuristic method is proposed to generate the initial solution;in order to improve the search efficiency and reduce the probability of trapping into local optimum,six types neighborhood operators are designed to construct the neighborhood of the aircraft route pair,and the simulated annealing algorithm is used to search the neighborhood;and finally,in order to expand the search space while ensuring that the disturbed solution satisfies the constraints,a new perturbation strategy is designed.The experimental results on the actual flight data provided by an airline show that the proposed iterated local search algorithm can solve large-scale flight recovery problems in reasonable time,and can effectively reduce the cost of loss caused by flight schedule interruption.