2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    Mar 15, 2018 at 23:06
  • $\begingroup$ 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 $\endgroup$
    – Haytam
    Mar 16, 2018 at 10:57

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.