Exact and heuristic methods to optimize maintenances and flight schedules of military aircraft
Institution:
Toulouse, ISAEDisciplines:
Directors:
Abstract EN:
This thesis studies the long term Military Flight and Maintenance Planningproblem. First, we evaluate the complexity of this optimisation problem. Then we propose aMixed Integer Programming (MIP) model to solve it. We develop an instance generator anda heuristic to generate initial solutions. Furthermore, we apply Machine Learning to improvethe performance of the MIP model by using valid cuts generated on the basis of initialconditions and learned cuts based on the prediction of characteristics of optimal solutions.These cuts are applied to a new MIP model. This results in reductions in the solutiontime with little losses in optimality and feasibility in comparison to alternative matheuristicmethods. Finally, we present a new matheuristic to efficiently solve large instances. Themethod employs a Variable Neighborhood Descent that combines Dynamic Programming(DP) and Rolling Horizon neighborhoods. The DP is applied to a graph representation of thesolution space for a single aircraft. This results in fast good quality solutions and an efficientscaling for very large instances.
Abstract FR:
Cette thèse étudie le problème de planification de vol et de la maintenancedes avions militaires. D’abord, nous étudions la complexité de ce problème d’optimisation.Puis, nous proposons un modèle de programmation linéaire en nombres entiers (PLNE) pourle résoudre. Nous construisons un générateur d’instances et une heuristique pour générer dessolutions initiales. Ensuite, nous appliquons l’Apprentissage Automatique pour améliorer laperformance des modèles PLNE en utilisant des coupes valides générées à partir des conditionsinitiales et des coupes apprises à partir de la prédiction des caractéristiques de solutionsoptimales. Ces coupes sont appliquées à un nouveau modèle PLNE. Le résultat est une réductiondu temps de résolution avec peu de pertes d’optimalité et de faisabilité par rapport auxméthodes matheuristiques alternatives. Finalement, nous présentons une nouvelle matheuristiquepour résoudre efficacement des grandes instances. La méthode utilise une descente àvoisinage variable qui combine la programmation dynamique (DP) et l’horizon glissant. LaDP exploite une représentation en graphe de l’espace des solutions de chaque avion. Le résultatest des solutions rapides et presque optimales, et un passage à l’échelle efficace pourdes instances de très grande taille.