Nouvelle heuristique pour la résolution du Problème du voyageur de commerce

Abstract

Dans ce mémoire, nous jetons les bases et ouvrons la voie _a une nouvelle heuristique de complexité polynomiale pour la résolution du célèbre problème du voyageur de commerce en introduisant une nouvelle représentation graphique de l'espace total de solutions, sous forme d'un graphe condense, pondère, oriente et acyclique, ainsi qu'une méthode de parcours de ce nouveau graphe inspirée de l'algorithme de recherche de chemin point-_a-point de Dijkstra.