Le problème du voyageur de commerce : introduction

Depuis mes études en informatique (vers 1995, ça commence à dater), je m'intéresse aux algorithmes génétiques, et à une de ses applications les plus connues, le problème du voyageur de commerce.
Le problème est simple en apparence. Il s'agit de trouver le chemin le plus court entre n villes, qui passe une seule fois par chaque ville. Un peu comme un voyageur de commerce qui parcours la France et cherche à passer le moins de temps possible sur la route.

Simple, semble-t-il, pour un ordinateur : il n'y a qu'à analyser toutes les solutions.
Là où le problème se complique, c'est quand le nombre de villes devient élevé. Le temps de calcul croit de manière exponentielle. A partir de 30 villes, il serait impossible de calculer bêtement toutes les possibilités. Cela prendrait ... plusieurs milliards d'années !

Il faut donc trouver un autre algorithme pour résoudre le problème, qui trouverait dans un temps raisonnable une solution approchée.

Beaucoup de méthodes atteignant ce but ont été développées (dont certaines assez récement) : méthode des plus proches voisins, de Lin-Kernighan, de l'élastique, du recuit simulé, les réseaux de neurones auto-adaptatifs, algorithmes génétiques, tabu search, colonie de fourmis...
Certaines méthodes sont très simples, d'autres très complexes... Ce qui est sûr, c'est que ce problème stimule la créativité !

Parmi ces nombreuses méthodes, une m'a particulièrement intéressée : les algorithmes génetiques...