Approches par décomposition pour des problèmes réels de planification et de tournées de véhicules

Different players in the industry face every day new optimization problems involving decisions to be made either at a tactical level, such as determining the best warehouses’ location intended to cover a given geographical area, or at an operational level, such as improving efficiency of a production process. The objective of this 'Cifre' thesis is to propose solution approaches while focusing on planning and vehicle routing problems faced by industrial customers. We will highlight first the main difficulties that can be encountered in aiding decisions process with the industrial customer, and then address three case studies of complex problems that we have dealt with during the thesis. We mainly use decomposition approaches to solve these problems due to their complexity and large size of the corresponding instances. To assess the performance of some solution methods, we compare them to the best bounds obtained by relaxing some constraints and to optimal solutions of similar problems existing in the literature when possible.Différents acteurs du monde de l'industrie rencontrent quotidiennement des problèmes d'optimisation impliquant des décisions à prendre soit à un niveau tactique, comme pour déterminer le meilleur emplacement d'entrepôts à installer pour couvrir une zone géographique donnée, ou bien à un niveau opérationnel, comme pour améliorer le rendement d'un processus de production. L'objectif de cette thèse Cifre est de proposer des approches de résolution en se focalisant sur des problèmes de planification et de tournées de véhicules issus de clients industriels. Dans un premier temps, nous mettrons en lumière les principales difficultés que l'on peut rencontrer dans le processus d'aide à la décision avec le client industriel, pour ensuite aborder trois cas concrets de problématiques complexes que nous avons traités durant cette thèse. Nous utilisons essentiellement des approches par décomposition pour résoudre ces problèmes au vu de leur complexité et à la taille des instances industrielles traitées. Pour valider l'efficacité de certaines méthodes de résolution, nous les comparons aux meilleures bornes obtenues en relaxant certaines contraintes et aux solutions optimales de problèmes similaires existants dans la littérature lorsque cela s'avère possible