The four-day aircraft maintenance routing problem

Federal aviation regulations require that all aircraft undergo maintenance after flying a certain number of hours. Most major U.S. airlines observe the maintenance regulations by requiring that aircraft spend a night at maintenance station after at most three or four days of flying. In addition, some airlines require that every aircraft goes through a special maintenance station for what is commonly called a balance check. Airlines usually schedule routine maintenance only at night so as not to cut into aircraft utilization. The maintenance routing problem is to find a routing of the aircraft that satisfies the short-term routine maintenance requirements. Earlier, we modeled this problem as one of generating an appropriate directed graph (called a line-of-flight-graph), and of finding a special Euler Tour called the h-day Maintenance Euler Tour (k-MET, for k=3, 4, ...) in that directed graph, for finding a maintenance routing in which the aircraft would spend at most k days of flying before overnighting at a maintenance station and have an opportunity for a balance check. In the same paper we gave a polynomial-time algorithm for finding a 3-MET, if one exists, in the directed graph. In this paper we consider the routing problem when the requirement is to overnight at a maintenance station after at most four days of flying and to undergo the balance check every n days, where n is the number of planes in the fleet of the equipment type under consideration. We show that this problem is NP-complete; in fact, that the K-Met problem is NP-complete for all k greater than or equal to 4. When the number of maintenance stations is exactly one, we show that the 4-MET problem can be solved by solving an appropriate bipartite matching problem; and hence in polynomial time. As a corollary to this result, we show that when there is no balance check station visit requirement, the four-day routing problem, in a given LOF-graph, can be solved (without any restrictions on the number of maintenance stations) in polynomial time. We show how our polynomial-time algorithms for the 3-MET problem and the restricted 4-MET problem can be used to design effective heuristics for the 4-MET problem.