Disrupted airline schedules dispatching based on column generation methods

The dispatching of disrupted airline schedules is a very complicated real-time network optimization problem,which belongs to NP-complete problem.Considering the situation caused by both the shortage of aircraft resources and the closure of airports,this paper adopts time-space network technique to construct the recovery network for each aircraft.Based on this,the problem is considered as a multicommodity integer minimum cost flow with the side constraints,so a mathematic model of multi-commodity network flow is established.Column generation methods are introduced to solve this large integer programming problem,and the branch and bound algorithm is used to handle the non-integer solutions.Finally, a given instance analyzed in details validates the correctness and efficiency of the method.