Modélisation et résolution de problèmes généralisés de tournées de véhicules

摘要: Le probleme de tournees vehicules est un des problemes d’optimisation combinatoire les plus connus et difficiles. Il s’agit determiner optimales pour une flotte afin servir ensemble donne clients. Dans classiques transport, chaque client normalement servi a partir d’un seul nœud (ou arc). Pour cela, on definit toujours nœuds arcs) obligatoires visiter ou traverser, recherche la solution cet arcs). Mais dans plusieurs applications reelles peut etre nœud, arc), generalises qui en resultent sont complexes. but principal cette these d’etudier trois vehicules. premier tournee sur arcs suffisamment proche (CEARP), comporte application reelle interessante routage le releve compteurs distance ; deux autres problemes, couvrantes multi-vehicules (mCTP) generalise (GVRP), permettent modeliser conception reseaux transport niveaux. resoudre ces nous proposons approche exacte ainsi que metaheuristiques. developper methode exacte, formulons comme programme mathematique, puis construisons algorithmes type branchement coupes. Les metaheuristiques basees ELS Evolutionary Local Search) GRASP Greedy Randomized Adaptive Search Procedure). De nombreuses experimentations montrent performance nos methodes.