Traveling salesman problem: why visit each city only once?

10.1k Views Asked by At

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.

2

There are 2 best solutions below

0
On

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.

1
On

The TSP (and related problems, such as capacitated vehicle scheduling) usually assumes complete graph to be given as an input. This might not be the case in real life, but you might convert the initial graph to a complete graph with calculating minimal distance algorithms (Floyd-Warshall, etc).

In that case, there is no need to visit the same city once. And the objective function obviously discourages you from visiting the same city more times, so I believe it is a "hint" restriction rather than a tight one.