Abstract
This paper establishes a theoretical foundation for the aircraft routing problem, specifically addressing maintenance constraints. It proves that for standard maintenance intervals ($\gamma \le 4$ days), a feasible daily flight schedule always permits an "absolutely periodic" solution. Furthermore, the study demonstrates that the general finite-horizon version of the problem is NP-complete for $\gamma \ge 4$, while providing a polynomial-time algorithm for "quiet night" scenarios with fixed fleet sizes.
Introduction
Aircraft routing involves assigning specific flight legs to individual aircraft while ensuring each plane visits a maintenance base at least once every $\gamma$ days. This problem is typically approached through two lenses: periodic schedules (daily fleet assignment) and finite-horizon schedules (specific lists of flights over a set period). Historically, researchers assumed that a feasible daily schedule implies a periodic solution, but this remained unproven. This paper fills these gaps by analyzing the complexity and structural properties of these routing problems.
Methods and Graph Modeling
The authors utilize graph theory and computational complexity analysis. They model the problem using Eulerian directed graphs where vertices represent airports and arcs represent "Lines of Flying" (LOFs). To prove the existence of periodic solutions, they construct specialized bipartite graphs and leverage the total unimodularity of linear programming. For the "quiet night" scenario, a combinatorial "pebbling game" tracks aircraft distributions and maintenance counters.
The Periodicity Guarantee
A major contribution is Theorem 1.1, which guarantees that for $\gamma \le 4$, no feasible solutions are lost by enforcing "absolute periodicity." This justifies the industry practice of using periodic schedules. The paper distinguishes between different types of periodic solutions, as illustrated below.
Complexity and Results
The paper clarifies that while the periodic problem for $\gamma \le 4$ is in P (polynomial time), the finite-horizon version becomes NP-complete for $\gamma \ge 4$. However, the "quiet night" version, where maintenance occurs during overnight stays, is solvable in polynomial time relative to the number of airports if the fleet size is fixed ($O(|V|\gamma^{|S|})$).
Conclusion and Future Work
The findings provide a rigorous justification for existing airline scheduling practices while highlighting the inherent complexity of longer-horizon planning. Future work remains to address the open question of periodicity for $\gamma \ge 5$ and to incorporate additional real-world constraints like crew scheduling and stochastic delays.
Summary updated