| In the airline industry, an important problem that is confronted during daily operations is aircraft maintenance routing. This problem involves routing a sub-fleet of aircraft to appropriate maintenance stations before violating maximum flying hour limits imposed by the Federal Aviation Administration (FAA). Although airlines create long-term maintenance schedules for their aircraft, uncertainties such as unplanned equipment failures and schedule changes induced by inclement weather create havoc in these long-term plans. To recover from these irregular operations, airlines currently employ heuristic, “off the cuff” solutions. The literature on recovery is also sparse. It is with this in mind that we address the daily operational aircraft maintenance routing problem.; The main goal of our problem is to minimize the total operational maintenance costs for a sub-fleet of aircraft. We attempt to achieve this by solving a surrogate problem involving minimizing each aircrafts cushion time (flying time remaining until an aircraft passes its maintenance limits). In addition, we include some operational constraints such as maintenance man-hours and slot availability at maintenance stations that are missing from most planning models. This problem turns out to be NP-hard.; To solve this difficult problem, we propose a branch-and-price scheme that employs column generation at each node of a branch-and-bound search tree. Column generation is used to solve candidate sub-problems appearing as constrained shortest path problems. In doing so, we introduce two new ideas: (i) a new modification to Yen's kth shortest path algorithm that is used in the Handler and Zang dual method for constrained shortest path problems, and (ii) a new branching scheme that we call “Modified Prioritized Follow-on”.; For our branch-and-price algorithm, we first investigate the effectiveness of several preliminary heuristics on small-scale problems. We then investigate the effects of six factors on our branch-and-price algorithm via a 2-level factorial design. After determining the best configuration for our branch-and-price algorithm, we attempt larger problems and examine the effects of two other features: bound tightening and column deletion. Finally, we compare four approximation methods, an Adaptive method, Yen's Heuristic, 3% Yen's Heuristic and 3% Optimality, against pure optimality to determine the best approach for robustness and effectiveness. |
