1

I'm trying to develop my own algorithm for solving Travelling Salesman Problem (TSP) I tested it (in its current state) on the "att48" instance of the TSPLIB and got following results:

enter image description here

As we can see more than 3/4 of results are within 110% of the optimal route length. But in scientific literature they report for over 20 decades that their algorithms solve like 99% of the TSPLIB instances to 1% of the optimal distances (though where are their GIS implementations?!). So I wonder if there is for example a commonly acceptable threshold for the algorithm output to determinate whether it is garbage or can be used in real life? Or there are exists other means of TSP solver assessment?

Improve this question
4
  • 1
    You cannot conclude anything about the general performance of an algorithm when you apply it to only one problem instance! Your plots merely describe the performance of a randomized algorithm on a single dataset. (Because it is randomized, it produces a distribution of outputs rather than a single unvarying result.) If you would like to address the performance overall then you need to replicate this study for a large number of varied inputs.
    – whuber
    Commented Nov 13, 2014 at 15:37
  • @whuber, of course it should be tested on more problems (and it will be after performance tweaks), but the question remains - is there a threshold to distinguish good and bad algorithms for a problem of the given size? I didn't catch your point about randomisation - most of heuristic algorithms are randomisation-based. Even if output is always the same we can say that 100% of results are within n% of the optimal length.
    – SS_Rebelious
    Commented Nov 13, 2014 at 16:30
  • The points about randomization were made to explain the varying nature of your results and to distinguish variation in the application to one problem from variation in the application to a suite of problems. There cannot possibly be a universal threshold, as you ask, because whether an algorithm is suitable for you depends on much more than how closely it approaches the optimum: it depends on the costs of implementing and running the algorithm, what your accuracy needs are, and the consequences when the algorithm produces a suboptimal result.
    – whuber
    Commented Nov 13, 2014 at 16:41
  • @whuber, I found a methodology - see my answer.
    – SS_Rebelious
    Commented Nov 13, 2014 at 18:13

1 Answer 1

Reset to default
0

Ok, I found a recent article where they tested and compared several TSP algorithms. They made tested algorithms find their solutions under 100 seconds time limits for several datasets. For my luck 'att48' was amongst them. Here is one of comparison tables (distanced are divided by 100):

enter image description here

So I have a good news for myself - my solutions were found under 100 seconds (85-95) of the real time (not CPU time), and the only algorithm in this table that outperforms mine for the 'att48' is simulated annealing.

Improve this answer
6
  • This is nice for you--but it does not appear to answer the question you posed! It is not valid to take such a table of comparisons as being any kind of evidence of "commonly acceptable thresholds."
    – whuber
    Commented Nov 13, 2014 at 18:17
  • @whuber, the question is in the title - 'How to assess quality of the TSP algorithm?' Threshold was my hypothesis of quality assessment.
    – SS_Rebelious
    Commented Nov 13, 2014 at 18:23
  • So you didn't really mean it when you concluded your post with "I wonder if there is a commonly acceptable threshold for the algorithm output to determinate whether it is garbage or can be used in real life?"
    – whuber
    Commented Nov 13, 2014 at 18:25
  • @whuber, again - treshold was my idea of the TSP algorithm assessment. I'm not bold enough to think that my ideas are [always] the best.
    – SS_Rebelious
    Commented Nov 13, 2014 at 18:30
  • I am not challenging your ideas: I am merely asking you, in my role as moderator, to make sure your question is sufficiently clear to be well understood by your readers. I have already commented on issues that I think are important concerning the question you seem to have asked, but only you really know the question you intended to ask.
    – whuber
    Commented Nov 13, 2014 at 18:34

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.