 |
Caractérisation des arêtes d'une solution optimale du TSP
1 : Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France
Univ. Grenoble Alpes, CNRS, Grenoble INP, F38000 Grenoble, France
2 : Univ. Gustave Eiffel, Univ. Lyon, ENTPE, LICIT-ECO7 UMR T9401, F-69675, Lyon (France)
Univ. Gustave Eiffel, Univ. Lyon, ENTPE, LICIT-ECO7 UMR T9401, F-69675, Lyon (France)
Nous nous intéressons dans ce travail à la caractérisation des arêtes d'une solution optimale du problème du voyageur de commerce (TSP). Ces charactéristiques sont calculées à partir des données du graphe, d'heuristiques et de relaxations du TSP 2-D Euclidien. Les résultats montrent qu'il est possible de drastiquement réduire la taille des graphes et que cela permet de réduire les temps de calculs de manière significative pour des approches exactes du TSP.
