CODEWITHSUNDEEP
algorithm
Muhammad Shoaib
Muhammad Shoaib

Reputation: 11

Travelling Salesman (TSP) Performance

Can anybody tell me, how can I compare TSP Optimal and heuristics? I have implemented TSP but don't know how can I compare them. Infact, how can I find the optimal cost of the TSP? Any method or guess?

Thanks

Upvotes: 1

Views: 877

Answers (2)

user855520
user855520

Reputation:

Check the optimal solution with well-known benchmark instances:

Download the data from TSPLIB here and compare your solutions with the optimal values here

Upvotes: 2

NPE
NPE

Reputation: 500157

Solving the TSP to optimality is an NP-hard problem.

To assess the quality of a heuristic solution, you have several options:

  1. Compare it to heuristic solutions produced by other algorithms. This will give you an idea of which heuristics work better on the given instance, but obviously won't tell you anything about how close you are to the optimal solution.

  2. Compare to the optimal solution. Concorde is probably your best bet for computing this.

  3. Compute a lower bound for the TSP instance, and compare the heuristic solution to that. The two standard approaches are the Held-Karp lower bound and the assignment problem relaxation.

  4. Use instances with known optimal solutions, such as those in TSPLIB.

Upvotes: 1

Related Questions