Solving Aircraft Schedule Recovery Problems Using a Distributed Computation Approach to Integer Programming

Abstract

Disruptions are prevalent phenomenon that prevent airline from operating as originally scheduled. In this situation, the airline must be able to return to the original schedule by producing a recovery plan as quickly as possible to prevent massive flight cancelations and delays. Considering the airline schedule consists of three elements namely the aircraft schedule, crew schedule and passenger schedule, the total airline disruption problem should comprise aircraft schedule recovery, crew schedule recovery and passenger schedule recovery. Each of these three problems can be very complex, so this thesis will focus on the aircraft recovery problem, which has the greatest effect on airline disruption.

A distributed implementation of an iterative method of integer programming is proposed in this thesis to deal with the aircraft recovery problem. The problem is modeled here as two subproblems: feasible flight routes generation and aircraft reassignment. For the first subproblem, two different models are proposed to generate feasible flight routes. One is formulated from a airport connection network, and the other is based on the Traveling Salesman Problem (TSP) model. Before solving either two model, the solution space is divided into any number of independent segments by two division methods. Then a distributed computation is proposed to generate feasible flight routes using an iterative approach to integer programming among these divided segments. The obtained feasible flight routes are used to construct an aircraft reassignment which is the second subproblem.

The generation of new feasible flight routes proceeds in two directions from the original flight routes in the first subproblem. This produces flight routes that are always larger than the original flight routes in the lexicographical order in one direction, and will also produce flight routes that are always smaller than the original flight routes in the reverse lexicographical order in another direction. Any feasible flight routes generated at a later stage are larger than the feasible flight routes generated at an earlier stage in the lexicographical order, and any feasible flight routes generated at a later stage are smaller than the feasible flight routes generated at an earlier stage in the reverse lexicographical order. Thus, feasible flight routes obtained at an earlier stage deviate less from the original flight routes than those obtained at a later stage. For a large aircraft recovery problem, it is impossible to generate all feasible flight routes in a reasonable amount of time. Only partial feasible flight routes are generated in each segment.

All flight schedules that appeared in Argüello et al., Argüello, Thengvall, Liu et al., Babic et al. and Andersson and Värbrand are used to evaluate our approach. Comparisons between the partial feasible flight routes generated by the iterative method to integer programming and by CPLEX CP Optimizer show that our approach is more capable of generating feasible flight routes that can constitute a solution for the aircraft reassignment problem than CPLEX CP Optimizer. Comparisons between the results for the second subproblem obtained by our approach and the results of the same schedule in the literature show that not only the same solutions to the second subproblems can be computed, but also solutions that are better than those in the literature can be found.

Date of Award	26 Jun 2013
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chuangyin DANG (Supervisor)