Optimisation du routage des avions sous contraintes de maintenance par génération de colonnes

La maintenance des avions constitue un enjeu à la fois économique et stratégique dans le secteur aéronautique, influençant directement la sécurité, la fiabilité ainsi que la rentabilité des opérations. Par conséquent, les compagnies aériennes se concentrent sur l’optimisation des coûts afin de concilier les normes de sécurité avec la disponibilité des appareils. Pour assurer une navigabilité continue, la planification de la maintenance doit être adaptée aux spécifications des avions tout en tenant compte des contraintes logistiques des installations de maintenance. Une caractéristique clé du problème de routage de maintenance des avions sur le niveau opérationnel (OAMRP) est la gestion des fenêtres de maintenance flexibles. Chaque contrôle de maintenance doit être réalisé dans un intervalle de tolérance défini par un moment le plus précoce autorisé, un moment idéal pour l’utilisation optimale des ressources et une limite réglementaire absolue. L’exécution de la maintenance en dehors de cet intervalle en-traîne des pénalités. Celles-ci sanctionnent soit une maintenance trop précoce, entraînant une sous-utilisation de l’appareil, soit une maintenance trop tardive, augmentant le risque de perturbations opérationnelles. De nombreux travaux ont étudié l’OAMRP, proposant diverses formulations et approches. À notre connaissance, aucun modèle existant ne prend en compte simultanément, dans une formulation unique, l’ensemble des exigences opérationnelles, les intervalles de tolérance, la capacité de la main-d’œuvre et les horaires d’ouverture des stations. De plus, la plupart des modèles ne traitent qu’une flotte unique, alors qu’en pratique, plusieurs sous-flottes inter-agissent en partageant les mêmes ressources de maintenance. Dans cette étude, nous abordons l’OAMRP, qui consiste à construire des routes pour une flotte hétérogène afin de couvrir un ensemble prédéfini de vols sur un horizon de planification donné (par exemple, deux semaines). Les routes doivent satisfaire les exigences de maintenance en termes d’heures de vol, de nombre d’atterrissages et de jours écoulés depuis la dernière maintenance, respecter les contraintes de capacité des stations de maintenance et minimiser la somme des coûts opérationnels et des pénalités liées à la maintenance. Pour résoudre ce problème, nous proposons une heuristique basée sur la génération de colonnes, reposant sur des sous-problèmes de plus court chemin avec des contraintes de ressources. Les sous-problèmes sont résolus à l’aide d’un algorithme d’étiquetage intégrant explicitement des pénalités bilatérales pour les écarts par rapport aux cibles de maintenance prédéfinies. De plus, une heuristique de réduction de taille de réseau est appliquée aux sous-problèmes afin de réduire le temps de calcul. L’approche proposée est validée sur un ensemble d’instances issues de cas réels, comprenant de 10 à 84 avions, 228 à 1 598 vols et jusqu’à 3 millions de connexions entre vols. Le jeu de données est divisé en trois catégories : petites, moyennes et grandes instances. Les expériences montrent que la limitation du nombre d’étiquettes par nœud et l’application de l’heuristique de réduction de taille de réseau, soit séparément, soit dans le cadre d’une stratégie hybride, ont un impact significatif. Ces techniques d’accélération permettent de réduire le temps de calcul de 13 % à 94 %, tout en maintenant un écart par rapport à la solution optimale inférieur à 1,5 %. Pour les grandes instances, la méthode a permis une réduction de 76 % du temps de calcul avec un écart de seulement 0,04 %.