Which approach produces the shorter tour in the TSP problem: nearest neighbour or genetic algorithms?

Question

Over the last few days I have noted a few web sites that demonstrated TS solution using genetic algorithms.

Which is approach produces the shorter tour in the TSP problem: nearest neighbour or genetic algorithms?

Answer 1

Since neither technique guarantees an optimal solution, your mileage will vary. With a little luck, either technique can out-perform the other. Both techniques have pros and cons.

Nearest neighbor: +fast, +simple, -usually not optimal

Genetic algorithm: -slower, -more complex, +solutions trend toward optimal over time

The big difference is that randomized algorithms like simulated annealing and genetic algorithms may continue to improve over time - the longer you let them run, the more chances you have for an optimal solution(though there are no guarantees).

Since NN is fast, there's nothing stopping you from combining the techniques. Run NN to find a possibly-better-than-random starting solution. Then, feed that solution into your genetic algorithm and let it run as long as you feel is appropriate.

If you're interested in optimal solutions, check out the Lin-Kernighan heuristic and Linear Programming. Both were used to find optimal solutions for large tours including this solution for a 85,900 city tour and a 24,978 city Sweden tour.

The Georgia Tech TSP site is a great resource.