Skip to Main content Skip to Navigation

Programmation en nombres entiers pour les diagrammes d'influence et les problèmes de maintenance d'une compagnie aérienne

Abstract : This thesis develops algorithms for stochastic optimization problems such as Markov Decision Processes (MDPs) or Partially Observable Markov Decision Processes (POMDPs), and uses them to give solution for the airplane maintenance problem at Air France. The research was conducted throughout a scientific chair between Air France and École des Ponts Paristech.We introduce a generic predictive maintenance problem for systems with several components evolving over time when a decision maker chooses dynamically which components to maintain at each maintenance slot. His actions are based on partial observations of each component and are linked by capacity constraints. The objective is to find a “memoryless” policy,which is a mapping from observations to actions, minimizing the expected failure costs and maintenance costs over a finite horizon. We formalize such a problem as a weakly coupled POMDP, that models each component as a POMDP. Finding an optimal memoryless policy for the weakly coupled POMDP is difficult for two reasons. First, even when the system has a single component, the problem is already NP-hard. Second, due to the curse of dimensionality, when the number of components grows the POMDP becomes quickly intractable. Our main contributions are mixed integer linear formulations for POMDPs that give an optimal memoryless policy, as well as valid inequalities that are based on a probabilistic interpretation of the dependencies between the random variables. In addition, we introduce a mixed integer linear formulation that breaks the curse of dimensionality and that induces a “good” policy for weakly coupled POMDP.In fact, the MDPs and POMDPs lie in the broad class of stochastic optimization problems where the uncertainty is assumed to satisfy a given structure called influence diagram. More precisely, given random variables considered as vertices of an acyclic digraph, a probabilistic graphical model defines a joint probability distribution via the conditional probability distribution of vertices given their parents. In influence diagrams, the random variables are represented by a probabilistic graphical model whose vertices are partitioned into three types: chance, decision and utility vertices. The decision maker chooses the probability distribution of the decision vertices conditionally to their parents in order to maximize his expected utility. Ourmain contributions are mixed integer linear formulations for solving the maximum expected utility problem in influence diagrams, as well as valid inequalities, which lead to a computationally efficient algorithm. It generalizes our results on POMDPs to any influence diagrams.We also show that the linear relaxation yields an optimal integer solution for instances that can be solved by the “single policy update”, the default algorithm for addressing the maximum expected utility problem in influence diagrams.The airplane maintenance problem at Air France is a predictive maintenance problem with capacity constraints. Applying the weakly coupled POMDP policy produced by our algorithm on the airplane maintenance problem at Air France requires to estimate the weakly coupled POMDP parameters. Based on a dataset of historical sensor data, we propose a statistical methodology to cast the airplane maintenance problem as a weakly coupled POMDP. Our approach has the advantage of being interpretable by the maintenance engineers. The numerical experiments show that our approach reduces the number of failures and maintenance costs
Document type :
Complete list of metadata
Contributor : ABES STAR :  Contact
Submitted on : Thursday, October 28, 2021 - 10:58:36 AM
Last modification on : Thursday, May 12, 2022 - 10:21:00 AM
Long-term archiving on: : Saturday, January 29, 2022 - 6:45:39 PM


Version validated by the jury (STAR)


  • HAL Id : tel-03406968, version 1



Victor Cohen. Programmation en nombres entiers pour les diagrammes d'influence et les problèmes de maintenance d'une compagnie aérienne. Modélisation et simulation. Université Paris-Est, 2020. Français. ⟨NNT : 2020PESC1034⟩. ⟨tel-03406968⟩



Record views


Files downloads