VRP recherche locale heuristique

Question

Je suis en train de créer une heuristique de recherche locale pour résoudre le TSP, et ce processus semble échouer. J'ai généré un cycle hamiltonien aléatoire et je l'ai stocké dans sortant [] avec sortant [i] indiquant le sommet duquel pointe l'un des bords provenant de i. distances [a] [b] désigne la distance du sommet a au sommet b. Cependant, chaque fois que je lance ce code, au lieu d'optimiser le cycle hamiltonien que je passe en sortant, l'algorithme crée simplement le nouveau cycle 0-> numcities-2-> 1-> numcities-1. Il devrait simplement changer les sommets sortants à plusieurs reprises s'il peut s'améliorer sur la distance d'un sommet à son sommet sortant. Je néglige probablement quelque chose de mineur, mais je ne peux tout simplement pas comprendre ce que j'ai fait de mal. Je vais courir cela plusieurs fois en passant, et c'est ce à quoi le booléen changé est utilisé.

for(int i = 0; i < numcities; i++) 
{ 
    for(int j = i+1; j < numcities; j++) 
    { 
     if(distances[i][outgoing[i]] + distances[j][outgoing[j]] > distances[i][outgoing[j]] + distances[j][outgoing[i]] && i != outgoing[j] && j != outgoing[i]) 
     { 
     changed = true; 
     int temp = outgoing[j]; 
     outgoing[j] = outgoing[i]; 
     outgoing[i] = temp; 
     } 
    } 
} 

Answer 1

Le problème est que lorsque vous échangez outgoing[i] et outgoing[j], vous créez deux subtours - deux cycles plus petits.

Supposons par exemple que numcities=6 et votre tour de départ est 0 1 2 3 4 5. Supposons que votre déclaration if est vrai pour i=1, j=3. Votre code définit outgoing[1] = 4 et outgoing[3] = 2. Donc, le code pense que la tournée est maintenant 0 1 4 5 depuis outgoing[1] = 4. Ce n'est pas précisément la tournée que vous obtenez, mais je pense que c'est la même idée de base.

Pour résoudre ce problème, vous devez penser à la tournée en 3 parties - (A) la partie jusqu'à et y compris la ville i, (B) la partie entre i et j (y compris j) et (C) la partie après j. Quand vous changez les bords, vous devez reconfigurer le tour de sorte que (A) soit le même que précédemment, alors la partie (B) est inversée, alors la partie (C) est intacte. Donc, dans mon exemple, la partie (A) est 0 1, la partie (B) est 2 3 et la partie (C) est 4 5. Après avoir cassé les bords 1-2 et 3-4, et réattaché, vous obtenir la visite 0 1 3 2 4 5.

Ce que vous implémentez ici est appelé 2-opt. Vous trouverez plus d'informations à ce sujet dans beaucoup d'endroits.