Research On Irregular Flight Recovery Problem

On-time performance of airlines schedule is key factor in maintaining satisfaction of current customers and attracting new ones. But civil air-transport system is so complex that flights can’t be executed normally for varieties of reasons. Weather, air traffic control, airport security, passengers’own reasons, temporary lack of crew etc. can lead to flights can’t be executed normally, namely so-called irregular flight, also named flight disruption. Irregular flights not only disrupt airlines’normal operation, bringing much inconvenience to passengers, but also even impact airlines’revenue and reputation. Domestic airlines are giving more and more attention to irregular flights operations and management; Optimization control technology and algorithm design are becoming a hotspot of current research in irregular flight problem.This paper first tries to analyze the affect brought to airlines operation by disruption from the perspective of resource, and points out major disruption solutions. Then this paper describes discrete time-space network and how we get a recovery flight plan according to known flight info in irregular flight period. First, this paper researches and analysis the generation algorithm of time-space network, and then implements the algorithm after a detail summary of a number of articles. Second this paper builds a new model on the base of the improved time-space network considering of flight cancelled cost, flight delayed cost and passenger sunk cost. Then, improved column generation algorithm and branch and price algorithm are promoted and separately applied to solve the model. Here, improved column generation is integrated with SPFA algorithm to solve the sub-problem produced in column generation algorithm process; Branch and price algorithm is also implemented in this paper, and improved column generation is used in each branch and bound tree node’s model solving process until integer solution is reached. In the last, a case of some airlines is given to verify whether the promoted model and algorithm are effective.