Optimisation de tournées de véhicules et de personnels de maintenance : application à la distribution et au traitement des eaux

Thèse réalisée en convention CIFRE avec Veolia EauThis research, financed by a research contract with Générale des Eaux,concerns Multiperiod Vehicle Routing Problemwith Time Windows and a limited fleet.We propose several solution approaches. The main approaches are a metaheuristic, an optimal method, and an optimal-based heuristic method. The metaheuristic is based on Evolution Strategies, and MemeticAlgorithms. The optimal method is based on column generation. The very low rate of time windows makes the subproblem very hard to solve. This implies to find new ways to solve this subproblem, which lead us to design the optimal-based heuristic method.In a second stage, applying these methods to real-life inspired scenarios helps us providing decision aid methodology and information.Cette thèse, fruit d'un contrat de recherche avec Générale des Eaux,porte sur le problème de tournées de service multi-périodes avec fenêtres de temps et flotte limitée. Nous proposons plusieurs méthodes de résolution approchées, ainsi qu'une méthode optimale. La méthode optimale est basée sur la génération de colonnes. Une des méthodes approchées est un algorithme mémétique basé sur une heuristique également développée dans cette thèse. Enfin, la méthode optimale est dérivée en méthode approchée par l'utilisation d'une heuristique pour la résolution du sous-problème.Les algorithmes proposés permettent d'apporter des solutions efficaces à des problèmes comportant jusqu'à 300 clients, dans des temps variant de quelques secondes à quelques dizaines de minutes. Dans un second temps, nous appliquons ces méthodes à des scénarios issus de problématiques réelles, dans une logique d'aide à la décision