Le problème du voyageur de commerce

Un autre problème pratique dont la solution exacte est en dehors de la portée de méthodes analytiques est celui du voyageur de commerce. Le problème est le suivant : on veut visiter villes separées par des distances , et revenir à la ville de départ en parcourant la moindre distance possible. L'espace des tournées pour ce problème est l'espace

Cet espace est isomorphe au groupe symétrique sur éléments . En effet, chaque tournée est déterminée par la donnée d'une permutation , la signification de étant la ville qui succède à la ville . Par conséquent, . La minimisation de la longueur de tournées est donc un problème NP-complet et la solution exacte est inaccessible dès que est de l'ordre de 20.

En introduisant un hamiltonien qui associe à chaque tournée sa longueur

où est la distance entre les villes et , on peut utiliser un algorithme de recuit simulé pour obtenir une solution approchée du problème. Pour cela, on propose un changement de configuration de la manière suivante.