# 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 < number of nodes eligible to be swapped - 1; i++) {
for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
new_route = 2optSwap(existing_route, i, k)
new_distance = calculateTotalDistance(new_route)
if (new_distance < 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?

• What research have you done? There's been lots of work on heuristic for solving the TSP. I suggest doing a literature search to track down the state-of-the-art, and show in the question a summary of what you've found so far and a survey of the literature that you're aware of. You might start with crypto.stackexchange.com/q/8316/351 and en.wikipedia.org/wiki/… and the references at the end of that article. And welcome to CS.SE! – D.W. Mar 15 '18 at 23:06
• Thank you for the comments, I edited the post and removed the code. THe problem is that what I need is not a way of solving TSP but rather a heuristic (like 2 opt) to perform on every child, or some kind of other improvement since I'm using GA and I need to stick with it. I'll try to do some more research like you said – Haytam Mar 16 '18 at 10:57

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.