7
$\begingroup$

Does a ranking of TSP heuristics exist that is based on the quality of the solutions? For example a paper or another resource that compares the performance of TSP heuristics like the nearest neighbour, nearest insertion, saving algorithm, Christofides or others and gives advice on which one should be preferred?

  1. Edit: For me theoretical results and computational studies are interesting.

  2. Edit: Construction heuristics would be specially interesting for me.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Not sure if such a thing exists. But if you are looking for a very good heuristic, take a look at (webhotel4.ruc.dk/~keld/research/LKH-3). And if you are looking for a very fast exact algorithm (math.uwaterloo.ca/tsp/concorde/DOC/index.html). $\endgroup$
    – Matheus Diógenes Andrade
    Aug 17, 2021 at 17:26
  • 1
    $\begingroup$ Do you want theoretical results, guaranteeing what algorithms always perform better than others, or are you looking for computational studies indicating what algorithms usually perform better than others? $\endgroup$
    – Sune
    Aug 17, 2021 at 20:16

2 Answers 2

Reset to default
5
$\begingroup$

If you are looking for an experimental/numerical comparison (rather than a theoretical one), some experiments are reported in:

D. S. Johnson and L. A. McGeoch. The traveling salesman problem: A case study in local optimization. In E. H. L. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization, pages 215–310. John Wiley & Sons, New York, 1997.

Improve this answer
$\endgroup$
4
$\begingroup$

What you are looking for is the term domination analysis. For instance, see:

  1. Punnen, A., Margot, F., Kabadi, S. (2003) TSP heuristics: domination analysis and complexity. Algorithmica 35(2):111-127. DOI [theoretical results]

  2. César, R. et al. (2011) Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Operational Research. 211(3):427-441. DOI [computational results]

  3. Rosenkrantz, D. J., Stearns, R. E., Philip M. L., II. (1977) An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing. 6(3):563-581. DOI [theoretical results]

These cover performances of several of your listed heuristics (nearest neighbour, Christofides, insertion variants) as well as those developed in recent years.

Improve this answer
$\endgroup$

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.