<p>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.</p>

<p>You may check these heuristics with the <a href="http://www.math.uwaterloo.ca/tsp/concorde/index.html">Concorde TSP Solver</a> 
which is the best TSP solver I know so far.</p>

<p>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. </p>

CC BY-SA 3.0
2013-11-16T14:44:42.753Z
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.
Aerus
CC BY-SA 3.0
2013-11-16T14:38:26.243Z
2013-11-16T16:37:47.837Z
2013-11-16T16:37:47.837Z
Jennifer Ng
<p>Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the <em>triangle inequality</em> holds. </p>

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

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

CC BY-SA 3.0
2013-11-15T11:05:28.610Z
Genetic algorithms will probably work pretty well. You could also try (stochastic) $k$-opt. Both have worked for me in practice.
Juho
<tsp><heuristics>
Heuristics for tsp without triangle inequality
Aerus
# Heuristics for tsp without triangle inequality

(Asked by: username_0 on 2013-11-15)

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

**Tags:** tsp, heuristics

> **Comments:**
> **username_1**: Genetic algorithms will probably work pretty well. You could also try (stochastic) $k$-opt. Both have worked for me in practice.  

---

## 1 answers

### Answer by username_2 on 2013-11-16. Score: 12 | Accepted answer

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](http://www.math.uwaterloo.ca/tsp/concorde/index.html)
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.

> **Comments:**
> **username_0**: 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 username_1.  

---

