Les méthodes de résolution du problème du voyageur de commerce

Algorithme "2-opt"

Cet algorithme est simple et relativement efficace.

Le principe est le suivant :

• On génére un trajet initial aléatoirement (ou par une autre méthode).
• On applique à ce trajet une transformation simple (la plus simple possible).
• Si la transformation améliore le trajet, on garde cette transformation, sinon on l'annule.
• Puis on répète l'opération jusqu'à ce que l'on ne puisse plus améliorer le trajet.

Le mieux est d'effectuer une recherche systématique (par exemple tester toutes les permutations possibles sur un trajet).

Quelle transformation utiliser ?
L'expérience montre que les transformations les plus simples sont les plus efficaces.

Prenons par exemple le trajet suivant.

0-4-5-3-6-7-8-2-1-9

La première transformation qui vient à l'esprit est d'échanger deux villes :

0-4-2-3-6-7-8-5-1-9

Mais en regardant ce que cela donne sur le parcours, on se rend compte que la modification est importante, car on "casse" quatre liens (ou arêtes) entre les villes. Une transformation plus simple est le renversement du trajet entre deux villes, qui ne casse que deux liens :

0-4-2-8-7-6-3-5-1-9

Voici ce que ça donne graphiquement :

    0-4-5-3-6-7-8-2-1-9
  

    0-4-2-3-6-7-8-5-1-9
  

    0-4-2-8-7-6-3-5-1-9
  

Comment améliorer l'efficacité de l'algorithme ?

On peut tester des renversements au hasard en prenant par exemple 2 villes au hasard.

Une solution plus efficace (mais il en existe peut-être d'autres) est de tester toutes les permutations comme ceci :

Pour Ville_1 allant de 1 à N
  Pour Ville_2 allant de Ville_1 + 1 à N
    Renverser parcours entre Ville_1 et Ville_2
    Si le renversement raccourcit le trajet Alors on garde le renversement
    Sinon on ne garde pas le renversement
  FinPour
FinPour

Comment améliorer la rapidité de l'algorithme ?

Plutôt que de calculer la logueur de trajet à chaque fois, il est plus rapide de calculer le "gain", c'est à dire la différence de coût entre la solution initiale et la solution avec la portion de trajet retournée.

La formule est la suivante :

Si i < j :
  Gain = Distance(Ville(i), Ville((j+1)%Nb_Villes) )
         + Distance(Ville((i+Nb_Villes-1)%Nb_Villes), Ville(j) )
         - Distance(Ville((i+Nb_Villes-1)%Nb_Villes, Ville(i) )
         - Distance(Ville(j), Ville((j+1)%Nb_Villes) )

L'algorithme devient donc :

Pour Ville_1 allant de 1 à N
  Pour Ville_2 allant de Ville_1 + 1 à N
    Renverser parcours entre Ville_1 et Ville_2
    Si Gain(Ville_1, Ville_2) < 0 Alors renversement entre Ville_1 et Ville_2
  FinPour
FinPour

Il est intéressant de noter que l'on peut également calculer le gain pour la transformation "échange de 2 villes" :

Si i+1 < j-1 :
  Gain = Distance(Cities[(i+Nb_Villes-1)%Nb_Villes), Ville(j))
         + Distance(Ville(j), Ville((i+Nb_Villes+1)%Nb_Villes))
         + Distance(Ville((j+Nb_Villes-1)%Nb_Villes), Ville(i))
         + Distance(Ville(i), Ville((j+Nb_Villes+1)%Nb_Villes))
         - Distance(Ville((i+Nb_Villes-1)%Nb_Villes), Ville(i))
         - Distance(Ville(i), Ville((i+Nb_Villes+1)%Nb_Villes))
         - Distance(Ville((j+Nb_Villes-1)%Nb_Villes), Ville(j))
         - Distance(Ville(j), Ville((j+Nb_Villes+1)%Nb_Villes))

Idées de prolongation de cet algorithme :

• Dans quel ordre effectuer ces permutations pour ne pas arriver trop rapidement à un minimum local ? Commencer par celles qui offrent le plus grand gain ? Le plus petit ? Un gain minimum et maximum à chaque itération ?
• Afin de ne pas favoriser les villes du début, faire commencer l'algo à une ville différente de 1
• Mixer l'algo 2-opt avec renversement et avec échange de villes
• Méthode de Monte-Carlo : une fois que la solution ne peut plus être améliorée, la "perturber" avec par exemple 2 échanges de villes (ou plus), puis relancer le 2-opt. Cela permet de sortir des minimum locaux (testé dans mon programme tspgen, assez efficace).

J'ai implémenté un 2-opt assez simple et rapide pour une aide à la Coupe de France de Robotique 2004