14
$\begingroup$

According to wikipedia, the Traveling Salesman Problem (TSP) is:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Okay, that's a cool problem, but the part about "visiting each city exactly once" makes little sense to me. If I were a traveling salesman, I would just want to minimize the length (time, cost, whatever) of my route, and if visiting the same city $17$ times achieves this (say, because that city has an especially "central" position in the graph) then so be it. There seems to be little sense in restricting attention to Hamiltonian cycles (i.e. cycles in which each vertex occurs precisely once); in particular, I would imagine that this restriction simultaneously makes the problem harder (computationally) and also less applicable (e.g. to problems "from the real world.")

Wikipedia goes on to say that:

The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization.

In light of my previous comments, I find this surprising.

Question. Why has the TSP been so intensively studied, while the variant (which I find more natural) has apparently received much less attention?

In simple terms: why visit each city only once?

Let me just add that according to wikipedia, the general problem does not include the assumption that the triangle inequality holds; that special case is called the metric TSP. In this case, the restriction to Hamiltonian cycles is of course innocuous.

$\endgroup$
  • 1
    $\begingroup$ Forget about the "exactly". One is given a symmetric $(n\times n)$-matrix $[a_{ik}]$ where $a_{ik}$ represents the "distance" between cities $i$ and $k$, and you may assume that the triangle inequality holds. $\endgroup$ – Christian Blatter May 6 '15 at 15:44
  • 3
    $\begingroup$ Angry husbands. $\endgroup$ – Will Jagy May 6 '15 at 18:28
  • $\begingroup$ The same section of the Wikipedia article you cite in your last paragraph points out that if you lift the every-city-exactly-once condition, any non-metric TSP can be reduced to a metric TSP by replacing the distance between any pair of cities with the length of the shortest path between them. Then the triangle inequality holds on the modified problem, and Michael's answer applies. $\endgroup$ – Rahul May 7 '15 at 6:29
  • $\begingroup$ comp.nus.edu.sg/~stevenha/cs4234/lectures/04.TSP.pdf it is shown there that the metric versions are equivalent and are also equivalent to the general repeat version. The genereal exactly one version however is NP-Hard to approximate $\endgroup$ – Chiray Jun 29 at 16:21
  • $\begingroup$ @goblin Actually, the variant you've mentioned has a solution with linear complexity, that's why there was no need to study a solved problem( finding the shortest path ). But, for TSP we don't have a good algorithm. That's why people still studying the problem. $\endgroup$ – tarit goswami Jul 6 at 7:38
6
+50
$\begingroup$

Let's look at an example. Suppose you have four cities, A, X, Y, and Z, and A is at distance $1$ from each of the others, while the distance between any two of X, Y, Z is $100$. Then of course a solution to TSP starting at A is given by A to X to A to Y to A to Z to A – let's write this as AXAYAZA, which has length $6$, and visits A multiple times.

Now let's carry out the construction in Rahul's comment. We form a new problem with the same cities but with the distance between cities replaced by the length of the shortest path between the two cities. So in the new problem, A is still at distance $1$ from each of the others, but the distance between any two of X, Y, Z is $2$. Now the tirangle inequality is satisfied (although the configuration is still unrealizable in any Euclidean space), and a solution is given by AXYZA, length $6$, no city visited twice (except for both starting and ending at A).

So we have taken a problem where the solution has multiple visits to a city, and replaced it with an equivalent problem which doesn't. I hope it's clear that you can carry out this construction for any (finite) set of cities and distances. So you can always replace a problem with an equivalent problem where the triangle inequality is satisfied and no city gets visited more than once. So, there is no loss of generality in assuming the triangle inequality holds and no city gets visited more than once. That's why we can restrict our attention to what looks like, but really isn't, a special case.

$\endgroup$
  • $\begingroup$ Thanks. You've shown that if I want to solve the problem allowing multiple visits, I can change it into an equivalent problem where each node is visited only once. What about the opposite direction? $\endgroup$ – Pedro A Jun 25 at 17:42
  • $\begingroup$ I don't know, offhand. There's probably a way to do it (but why would you want to?). $\endgroup$ – Gerry Myerson Jun 25 at 23:25
  • $\begingroup$ To make sure that both problems (with and without the "only once" restriction) are really equivalent... $\endgroup$ – Pedro A Jun 27 at 1:56
  • $\begingroup$ Can you give any update to address my last comment? Thanks :) $\endgroup$ – Pedro A Jun 30 at 19:32
  • 1
    $\begingroup$ I will give you the bounty anyway, thank you very much :D $\endgroup$ – Pedro A Jul 1 at 11:48
5
$\begingroup$

Suppose there are roads going directly from every city to every other city. That makes the problem simple enough and general enough to work out some theory around it.
The road AC is shorter than AB+BC, (think of the triangle ABC), unless they are in a straight line. So, if you already visited B earlier, visiting B again is a detour that lengthens the total path.

$\endgroup$
2
$\begingroup$

I had the same question because I was considering this as a graph problem where distance between two nodes can be any arbitrary number. But I think TSP really means a geometric, physical problem. That is why if you pick two random nodes, the maximum distance between them is limited by the triangle inequality. But even then this is assuming a perfect plane. What if I have this city surrounded by mountains and you cannot go to any other city directly unless you spend days climbing up and down the mountain, but you have one passage that reaches to one other city and you are connected to the rest of the graph thereon? Since you have to stop at where you have started, you would have to visit one city twice to get the best solution.

In other words, if I haven't misunderstood anything, each city would naturally be visited once if map is planar and distances are determined geometrically. But if distances are not bounded by such rules, anything can happen in the optimal solution in my opinion.

$\endgroup$

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.