Using advanced tabu search techniques to solve airline disruption management problems

Disruption Management in the airline industry plays an important role in airline operations. The goal of disruption management is to minimize the costs associated with disruptions while returning to the original schedule. Methodologies using advanced tabu search (TS) were investigated to solve two flight rescheduling problems: the aircraft grounding problem and the reduced station capacity problem. The objectives of both problems were to minimize the schedule recovery costs associated with flight schedule modifications and deviations from the original route, which are composed of the sum of delay costs, cancellation costs and aircraft route swap costs. Reflecting the cost of the deviation from the original route, the swap cost was modeled as a non-linear function of the swaps of aircraft between routes. In each problem, a stand-alone tabu search approach was constructed to holistically minimize the sum of the cost of delays, cancellations and swaps. Next a hybrid method which combined a time-space network flow model with side constraints and a limited tabu search was created which attacked the problem in two steps: first, the total cost of delays and cancellations was minimized by the network flow model; second, a limited tabu search was conducted to minimize the number of swaps. A second hybrid method was then developed, which utilized the result from the first hybrid method as starting solution for the stand-alone tabu search. The results of the experiments performed with the hybrid methods clearly indicate that integrating TS with classical optimization methods has marked potential for improving the results of a disruption management technique.