Dans l'organisation de ses vols, une compagnie aérienne doit prendre en compte des contraintes de maintenance de ses avions, qui doivent passer au moins une nuit tous les D jours dans une base de maintenance. Ce problème est connu sous le nom de aircraft routing en Recherche Opérationnelle. 

Les modélisations de ce problème fluctuent dans la litérature. En particulier, une version anciennement utilisée, l'aircraft rotation problem, considère des plannings de vol qui se répètent chaque jour, et impose une contrainte supplémentaire: chaque avion doit réaliser chaque vol au bout d'un certain nombre de jours. Si la difficulté de l'aircraft rotation problem a été cernée (polynomial pour D < 4 et NP-dur pour D=4), la difficulté de l'aircraft routing, bien que considérée comme avérée, ne semble pas avoir été prouvée formellement. Nous proposons une modélisation formelle de l'aircraft routing tel qu'il est pratiqué ces quinze dernières années. Puis, nous démontrons son NP-difficulté pour D> 1 et sa polynomialité à nombre d'avions fixé. 

Ce travail théorique nous permet de plus de proposer une formulation sous forme d'un PLNE avec moins de 2nD variables et moins de n contraintes, où n est le nombre de vols. Les formulations classiques de ce problème font appel à une génération de colonnes: nous démontrons que notre formulation a le même relâché continu que l'approche classique par génération de colonnes. Des tests numériques sont en préparation pour valider la pertinence de cette approche.

Rapport de recherche : http://cermics.enpc.fr/~parmenta/ROADEF/Rapport_MPRO_Axel_Parmentier.pdf