When there is a perturbation in a carefully planned flight schedule, e.g. an aircraft breakdown, it is important to minimize the negative consequences of this disturbance. In this thesis, a model and a number of solution strategies for the Flight Perturbation Problem is presented. Based on a connection network, a mixed integer multicommodity flow model with side constraints is developed. Cancellations, delays and aircraft swaps, both within the same fleet and between different aircraft types, are used to take care of the perturbation. The model also assures that the schedule returns to normal within a certain time.
Six different solution strategies arc used to solve the model; the first based on a Lagrangian relaxation of the mixed integer multicommodity flow model. Four strategies are based on Dantzig-Wolfe decomposition and in two of them all feasible points are generated by a tree search algorithm before the master problem is solved, while the other two are column generation based. The last strategy is based on the metaheuristic tabu search.
The computational tests with real problem data show that the Dantzig-Wolfe based strategies and the tabu search strategy arc very promising, and especially the tabu search strategies could be used in a real problem application that could provide airlines with solutions to complex perturbation problems.