Solving Aircraft Schedule Recovery Problems Using A Distributed Computation Approach To Integer Programming

Disruptions are prevalent phenomenon that prevent airline from operating as orig-inally scheduled. In this situation, the airline must be able to get back to the original schedule by producing recovery plan as quickly as possible to prevent massive flight cancelations and delays. Considering the airline schedule consists of three parts that are aircraft schedule, crew schedule and passenger schedule, the total airline disruption problem contains aircraft schedule recovery, crew schedule recovery and passenger schedule recovery. Each of the three problems can be very complex, so this thesis mainly research the aircraft recovery problem which is the most important one for the whole airline disruption problem.A distributed implementation of an iterative method to integer programming is proposed to deal with aircraft recovery problem in this thesis. The problem is mod-eled as two subproblems in this paper:feasible flight routes generation and aircraft reassignment. For the first subproblem, two different models are proposed to gener-ate feasible flight routes respectively. One is formulated based on a station connection network, and the other is constructed based on the Traveling Salesman Problem (TSP) model. Before solving any one of the two models, the solution space is divided in-to 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. These obtained feasible flight routes are used to construct an aircraft reassignment which is the second subproblem.The generation for new feasible flight routes proceeds in two directions from the original flight routes in the first subproblem. It produces flight routes that are always larger than the original flight routes in the lexicographical order in one direction, and also it can produce flight routes that are always less than the original flight routes in the lexicographical order in another direction. Any feasible flight routes generated in a later stage are increasing in terms of the lexicographical order than the feasible flight routes generated in an earlier stage in one direction, and any feasible flight routes gen- erated in a later stage are decreasing in terms of the lexicographical order than the feasible flight routes generated in an earlier stage in another direction. Thus feasible flight routes obtained in an earlier stage are less deviated from the original flight routes than those obtained in a later stage. For a large aircraft recovery problem, it is impos-sible 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 Arguello et al.[1], Arguello [2], Thengvall [3], Liu et al.[4], Babic et al.[5] and Andersson and Varbrand [6] are used to eval-uate our approach. Comparisons between the partial feasible flight routes generated by the iterative method to integer programming and those 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 of second subproblem obtained by our approach and the results of the same schedule in literature show that not only the same solutions of the second subproblems in literature can be computed, but also solutions that are better than those in literature can be found.