Optimal TSP Tour
I wrote a bacterial evolutionary algorithm for solving TSP problems. I selected instance XQF131 ( http://www.math.uwaterloo.ca/tsp/vlsi/index.html ) to test my algorithm. This problem was solved by Concorde and the optimal tour is 564. But I figured out the optimal tour length and it is 567.2029. ( http://www.math.uwaterloo.ca/tsp/vlsi/xqf131.tour.html ) With my algorithm, I found the best solution 566.4142. My question is, how does the Concorde algorithm work? Does it calculate the optimal solution or approximation?
Thanks for answers!
source to share
Are you sure you have calculated the distances correctly? It seems like you should be getting an integer distance. Indeed, from the site you are citing: "In these examples, the cost of travel between cities is determined by the Euclidean distance rounded to the nearest whole number."
I hope your algorithm still found an optimal solution ...
source to share
According to wikipedia , this page and the wording on the site you posted, what you linked should be an optimal tour, not an approximation, and Concorde should provide optimal solutions.
I would check my calculations to make sure they were really wrong when reporting the length. If so, you can probably post this.
Even if not, your algorithm is probably only slightly worse. If it's faster than Concorde, or at least better than other evolutionary methods, you can probably post something anyway.
Good job and good luck!
source to share