5
$\begingroup$

I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current record for optimality is held by 'Concorde' which found a solution for a graph containing 85,900 cities. I've also found benchmarking data for Concorde, as well as data pertaining to the current best performance for a world map.

Is this data still accurate? It looks like a lot of this hasn't been updated since the early 2000s.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ I don't think that asking for a summary of the state of the art in TSP solvers is a very broad question so I disagree with the close vote. $\endgroup$
    – David Richerby
    Jul 31, 2014 at 21:00
  • $\begingroup$ What do you mean by "accurate"? The data, the timings, or which is the best algorithm today? $\endgroup$
    – Raphael ♦
    Jul 31, 2014 at 21:20
  • 1
    $\begingroup$ @Raphael all I really need to know for now is whether or not the current record for optimality is still 85,900 cities and whether or not the information on the current best performance for the world map is current. Also, is there a ruling body for this sort of thing? $\endgroup$
    – snerd
    Jul 31, 2014 at 21:25
  • 1
    $\begingroup$ Ten years later, it's be surprising if that was the record. Sheer increase in computational power is likely to beat that, even without algorithmic improvements. If anybody bothers to perform and publish benchmarks. $\endgroup$
    – Raphael ♦
    Jul 31, 2014 at 21:27
  • $\begingroup$ What research have you done? Have you done a literature search? Have you looked for papers that discuss the Concorde result, and then used Google Scholar to find every paper that cites them? That seems like the obvious place to start. $\endgroup$
    – D.W. ♦
    Jul 31, 2014 at 22:12

1 Answer 1

Reset to default
-1
$\begingroup$

TSP has many variants under study eg Euclidean vs noneuclidean, exact vs approximations, interrelated but also at times separate threads of research. heres a recent nontechnical survey from early 2013 on TSP by an expert mathematical writer Klarreich, Computer Scientists Take Road Less Traveled that sheds some insight on recent improvements/ theoretical advances & can be mined for some refs. an old approximation algorithm by 1976 Christofides has been unrivalled for decades but some minor theoretical improvements have been made recently. as indicated in the article some theoretical TSP research that is not nec (practically) implemented veers into what is referred to as Galactic algorithm territory by expert RJ Lipton.

as a more applied resource/ angle, also a leading group/ site for benchmarking is DIMACS, NSF center for discrete math & CS, which also has a TSP page with algorithms/ benchmarks updated 2013.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Being myself incompetent on this topic, I would appreciate it if downvoters would explain what is wrong with this answer, so that I might have a chance to learn something. $\endgroup$
    – babou
    Aug 3, 2014 at 7:36
  • $\begingroup$ @babou I guess because most of the answer is a digression on algorithms to solve TSP, unrelated to the question, and written in a way to maximize legibility to boot. Only the last sentence is relevant, and it's only a couple of links. The links (with proper identification) technically are enough here because the question is calling for resources, which makes this an answer but a low-quality one. $\endgroup$
    – Gilles 'SO- stop being evil'
    Aug 3, 2014 at 10:26
  • $\begingroup$ the question is not narrowly written. the answer responds in a correspondingly not-narrow way. DR interprets the question is asking for some summary in the state of the art TSP solvers. am eagerly awaiting reading any superior answer rather than vague/ unconstructive criticism of this one. $\endgroup$
    – vzn
    Aug 3, 2014 at 15:10
  • $\begingroup$ @vzn thank you for your reply! yes or no - is the current TSP record still held by Concorde for solving to optimality a graph containing 85,900? $\endgroup$
    – snerd
    Aug 3, 2014 at 21:37
  • $\begingroup$ DD glad you found something useful. unfortunately its not a black or white issue as the DIMACS pg reveals. it depends on what algorithmic category is chosen and what degree of approximation vs exact results are acceptable etc.; Concorde is defn a leader as listed in the results page. some of these questions are answered by competition results. unf the latest DIMACS competition for TSP apparently was from ~2002. here is another slide show by Johnson summarizing the results. $\endgroup$
    – vzn
    Aug 4, 2014 at 3:15

Your Answer

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

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