Vehicule routing problems and industrial application to reduce the ecological footprint

Dans cette thèse, nous nous sommes intéressés à la résolution approchée de problèmes de tournées de véhicules. Nous avons exploité des travaux menés sur les graphes d'intervalles et des propriétés de dominance relatives aux tournées saturées pour traiter les problèmes de tournées sélectives plus efficacement. Des approches basées sur un algorithme d'optimisation par essaim particulaire et un algorithme mémétique ont été proposées. Les métaheuristiques développées font appel à un ensemble de techniques particulièrement efficaces telles que le découpage optimal, les opérateurs de croisement génétiques ainsi que des méthodes de recherches locales. Nous nous sommes intéressés également aux problèmes de tournées classiques avec fenêtres de temps. Différents prétraitements ont été introduits pour obtenir des bornes inférieures sur le nombre de véhicules. Ces prétraitements s'inspirent de méthodes issues de modèles de graphes, de problème d'ordonnancement et de problèmes de bin packing avec conflits. Nous avons montré également l'utilité des méthodes développées dans un contexte industriel à travers la réalisation d'un portail de services mobilité.In this thesis, we focused on the development of heuristic approaches for solvingvehicle routing problems. We exploited researches conducted on interval graphsand dominance properties of saturated tours to deal more efficiently with selectivevehicle routing problems. An adaptation of a particle swarm optimization algorithmand a memetic algorithm is proposed. The metaheuristics that we developed arebased on effective techniques such as optimal split, genetic crossover operatorsand local searches. We are also interested in classical vehicle problems with timewindows. Various pre-processing methods are introduced to obtain lower boundson the number of vehicles. These methods are based on many approaches usinggraph models, scheduling problems and bin packing problems with conflicts. Wealso showed the effectiveness of the developed methods with an industrial applicationby implementing a portal of mobility services