3
$\begingroup$

Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the triangle inequality holds.

Are there heuristics to solve the tsp that don't assume the triangle inequality and still perform well*?
If there aren't, why is that?

*i.e. don't run for a year for 100 cities and get relatively close to the optimum

$\endgroup$
  • 1
    $\begingroup$ Genetic algorithms will probably work pretty well. You could also try (stochastic) $k$-opt. Both have worked for me in practice. $\endgroup$ – Juho Nov 15 '13 at 11:05
12
$\begingroup$

I hope this partly answers your question: Most known heuristics like Greedy, Naerest Neighbor, Lin-Kerninhan etc. perfrom quite well for (symmetric) TSP without triangle inequality.

You may check these heuristics with the Concorde TSP Solver which is the best TSP solver I know so far.

In theory, there is no heuristic for TSP without triangle inequality that performs well (like Christofides for metric TSP). This is due to the well known fact that TSP cannot be approximated within any polynomial time computable function unless P=NP.

$\endgroup$
  • $\begingroup$ Thank you for your reply, I do know they usually still perform quite well but I was looking more for answers like the comment of Juho. $\endgroup$ – Aerus Nov 16 '13 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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