Application of Greedy Random Adaptive Search Algorithm (GRASP) in Flight Recovery Problem

Abstract With the rapid growth of air transportation, capital is becoming increasingly scarce, and the abnormal situation of flight is becoming more and more serious. Irregular flights have become popular in society, and it is also a great difficulty for airlines. Flight recovery is a classic NP problem. It is of great theoretical significance and practical value to study flight restoration problem. The punctuality of the airline’s schedule is a key factor in retaining current customers and attracting new passengers. However, because the civil aviation transportation system is very complex, many reasons will cause the flight plan can not be carried out normally. Weather, air traffic flow control, airport security check, passenger’s own reasons and temporary shortage of crew cause the flight can’t be executed normally, that is, abnormal flight or flight interruption. Flight interruption will affect the normal operation of airlines. Some flights have to be cancelled or delayed, which will cause huge economic losses to airlines. Besides, the delay or cancellation of flights will cause great inconvenience to passengers and affect the reputation of airlines. The operation control and management level of abnormal flights has attracted more and more attention from domestic airlines. Optimization control and algorithm design have also become a hot topic in the research of abnormal flights in China. Based on the further understanding of the NP problem, this paper verifies the feasibility of the greedy random adaptive search algorithm GRASP algorithm in the NP problem solving process under the flight recovery problem model. According to the analysis, the resource allocation model is established to verify the shortcomings of Lagrange relaxation algorithm (LRS) in flight recovery problem. Meanwhile, the greedy random adaptive search algorithm (GRASP) is used to solve the model, and the new flight schedule is obtained. Through the experimental results, the feasibility of the algorithm is proved in the error range.