Using 2-opt Heuristic in a Genetic Algorithm for TSP I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (https://arxiv.org/ftp/arxiv/papers/1209/1209.5339.pdf) and I saw in the same paper that he uses the 2-opt heuristic (and the 3-opt one) on every new child, so I went ahead and did the same.

Using this definition of the 2-opt (https://en.wikipedia.org/wiki/2-opt) I implemented their following pseudo-code:

  repeat until no improvement is made {
       start_again:
       best_distance = calculateTotalDistance(existing_route)
       for (i = 1; i &lt; number of nodes eligible to be swapped - 1; i++) {
           for (k = i + 1; k &lt; number of nodes eligible to be swapped; k++) {
               new_route = 2optSwap(existing_route, i, k)
               new_distance = calculateTotalDistance(new_route)
               if (new_distance &lt; best_distance) {
                   existing_route = new_route
                   goto start_again
               }
           }
       }
   }


The problem with my class is that it takes way too much time when tested on a 51 cities instance (not to mention that 1 generation takes more than 20 minutes in the a280 instance)..

Is there a better approach to this algorithm? A faster/more robust way of improving the new children?
One optimization to your pseudo-code is to calculate the new cost of a route after performing a 2-opt move by:

cost = cost - d[b(i)][i] - d[i][a(i)] - d[b(k)][k] - d[k][a(k)] + d[b(i)][k] + d[k][a(i)] + d[b(k)][i] + d[i][a(k)]


with $b(x), a(x)$ being the node before and after node $x$ on your current route.