# Heuristics for tsp without triangle inequality

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

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