标题： 飞机路径规划：周期性与复杂性 显示英文标题

标题： Aircraft routing: periodicity and complexity

摘要： 飞机路径规划问题是运筹学在飞机管理中研究最多的几个问题之一。 它涉及将航班分配给飞机，同时确保定期访问维修基地。 本文探讨了该问题的两个方面。 首先，我们研究了周期性实例（航班每天相同）与周期性解之间的关系。 文献中隐含地假设——没有讨论——周期性实例需要周期性解，甚至需要一种更强形式的周期性解，其中每两架飞机执行完全相同的循环航班序列，或者完全不相交的循环航班序列。 然而，强制这种周期性可能会排除可行解。 我们证明，当每隔最多四天需要一次定期维护时，总是存在这种形式的周期性解。 其次，我们考虑了该问题的计算难度。 尽管该领域许多论文提到飞机路径规划问题的NP难性，但这样的结果仅在文献中的周期性实例中可用。 我们建立了非周期性版本的NP难性。 还证明了一个特殊但自然的情况的多项式性。 显示英文摘要

摘要： The aircraft routing problem is one of the most studied problems of operations research applied to aircraft management. It involves assigning flights to aircraft while ensuring regular visits to maintenance bases. This paper examines two aspects of the problem. First, we explore the relationship between periodic instances, where flights are the same every day, and periodic solutions. The literature has implicitly assumed-without discussion-that periodic instances necessitate periodic solutions, and even periodic solutions in a stronger form, where every two airplanes perform either the exact same cyclic sequence of flights, or completely disjoint cyclic sequences. However, enforcing such periodicity may eliminate feasible solutions. We prove that, when regular maintenance is required at most every four days, there always exist periodic solutions of this form. Second, we consider the computational hardness of the problem. Even if many papers in this area refer to the NP-hardness of the aircraft routing problem, such a result is only available in the literature for periodic instances. We establish its NP-hardness for a non-periodic version. Polynomiality of a special but natural case is also proven.