Travelling salesman problem¶
2022 Problem solving
Definition¶
Soit un vendeur, il doit visiter \(N\) villes avec une distance de déplacement minimale.
\[
\sum_{i=1}^{n} \sum_{j \neq i, j=1}^{n} c_{ij}x_{ij}
\]
Instances¶
Des instances sont disponibles TSPLIB95 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/
Exemple¶
Nous nous intéressons à l’instance eil76. Le nombre de nœuds est de 76 dans le plan euclidien. Dans ce cas, nous utilisons un algorithme de recherche locale stochastique: l’algorithme d’amélioration du premier ordre avec un opérateur d’échange de deux éléments.
La figure 1 représente la progression de l’optimisation.
