|
|
 |
|
Jeudi 6 Novembre
| Heure: |
10:30 - 12:00 |
| Lieu: |
Salle D215, Université de Villetaneuse |
| Résumé: |
Aircraft routing: periodicity and complexity |
| Description: |
Frédéric Meunier The aircraft routing problem is one of the most relevant problems of operations research applied to aircraft management. It involves assigning flights to aircraft while ensuring regular visits to maintenance bases. This work 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 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 established.
Joint work with Axel Parmentier and Nour ElHouda Tellache |
|
|
