Framework for exact solutions and heuristics for approximate solutions to airlines' irregular operations control aircraft routing problem

Airline irregular operations occur when a reduction in the flight resources or station capacity necessary to operate a flight schedule is encountered. This dissertation addresses the rerouting of aircraft in response to groundings and delays. The objective of this work is to reroute aircraft so as to minimize the cost to the airlines. In some cases cancellations will be necessary due to insufficient aircraft resources. The aircraft routings generated by the methods presented here implicitly delay flights and explicitly cancel others if necessary.; This dissertation presents a framework for exact solutions and heuristics for approximate solutions. Two mathematical representations are developed. These are difficult to solve but serve as motivation for the alternate modeling and solution methods presented later. These consist of a time-band optimization model and a greedy randomized adaptive search procedure (GRASP). Complete solution methodologies are presented for both of these methods.; The time-band model is constructed by transforming the routing problem into a time-based network in which the time horizon is discretized. The resulting formulation is an integral minimum cost network flow problem with side constraints. Conditions for which an exact solution to the model represents an optimal solution for the original problem are stated. The transformation procedure is polynomial with respect to the number of stations and flights in the schedule. Computational experience shows that the underlying network structure of the transformed problem often leads to integral solutions when solved with a standard linear programming code. Empirical results demonstrate that the solutions obtained are either provably optimal or no more than a few percentage points from the lower bound.; In the GRASP, the neighbors of an incumbent solution are generated and evaluated, and the most desirable are placed on a restricted candidate list. One is selected randomly and becomes the incumbent. The process is repeated until stopping criteria are encountered. The heuristic is polynomial with respect to the number of flights and aircraft. Empirical results demonstrate the ability of the GRASP to quickly explore a wide range of solutions and, in some cases, to produce high quality solutions.