9
$\begingroup$

It seems odd to me that the TSP denies the possibility of repeated cities. The goal of this traveling salesman is to go as fast as possible and visit all of the cities, right? So what if it is faster to travel through a city you have already been to?

$\endgroup$
  • 2
    $\begingroup$ I'm sure it's arbitrary. Only in rare cases allowing repeated cities would make any difference (never in metric TSP). So the problems are hardly different. The reason is probably historic. $\endgroup$ – Karolis Juodelė Nov 9 '13 at 20:19
  • 7
    $\begingroup$ I heard the salesman sells really bad products and it would be unwise to meet his old customers :) $\endgroup$ – ssch Nov 9 '13 at 23:13
3
$\begingroup$

It doesn't matter exactly how you define it because it's just a way of modelling a real-world problem. In TSP, you just have a set of cities and the cost of travelling between each pair of them. That doesn't exclude the possibility that, in the real world situation you're modelling, the best route between B and C might go through A. If that was the case then, yes, the route that is modeled as ABCA in TSP may very well really involve driving through A an extra time on the way from B to C but such detail is abstracted away in the TSP model.

$\endgroup$
  • 1
    $\begingroup$ A valid point, but I would like to point out that TSP is often used in real world situations. Is the no-repetition requirement forgiven when implementing real-world applications? $\endgroup$ – danmcardle Nov 9 '13 at 20:54
  • $\begingroup$ @danmcardle It depends on the application. $\endgroup$ – Tom van der Zanden May 28 '18 at 6:44
2
$\begingroup$

I agree that the constraint looks odd, and for many practical situations, it is not relevant. As pointed out by David in his answer, if you can alter the modeling yourself, then it does not really matter. But given a non-modifiable instance, it will make a difference, because general TSP with this constraint is not approximable within any constant factor, while relaxing the single-visit constraint seems to make it approximable within factor 2 (even though it is not metric). Unless I miss something, by standard arguments, you may first build a minimum spanning tree (of cost say $c$), then visit this tree with the euler tour technique. Clearly, the total cost of your tour is then $2 c$ (twice every edge). By contradiction, if there existed a tour of cost less than $c$, then this tour could be used to infer an MST of cost less than $c$, which is a contradiction.

$\endgroup$
1
$\begingroup$

Given any tour with repetitions, you can come up with a shorter tour that doesn't repeat any city. For example, consider a tour of the form $$ \cdots \to A \to \cdots \to X \to A \to Y \to \cdots, $$ which visits $A$ twice. You can take a shortcut on your second visit to $A$, going straight from $X$ to $Y$: $$ \cdots \to A \to \cdots \to X \to Y \to \cdots. $$

It might be that the shortest way from $X$ to $Y$ goes through $A$, but that is already encapsulated in the edge $X \to Y$. You can think of a mention of $A$ not as "passing through" $A$ but rather "stopping at" $A$. You need only stop at $A$ once, though you might pass through $A$ several times.

Actual algorithms for TSP could have this step of "taking shortcuts", for example Christofides's algorithm. See for example this description or that shorter account.

$\endgroup$
  • 4
    $\begingroup$ You're assuming metric TSP (i.e., that the triangle inequality holds). However, general TSP does not have the triangle inequality. For example, you could have cities $A, X_1, \dots, X_n$, where $d(A, X_i)=1$ and $d(x_i,x_j)=100$ for all $i, j$. The shortest tour with repetitions is $AX_1AX_2A\dots AX_nA$, with cost $2n+1$ but the shortest tour without repetitions is $AX_1\dots X_nA$, with cost $100n-98$. $\endgroup$ – David Richerby Nov 10 '13 at 0:39
  • $\begingroup$ Certainly, but (1) the OP seems interested in real-world applications of TSP, which are metric, and (2) non-metric TSP isn't as interesting (since it's too difficult). $\endgroup$ – Yuval Filmus Nov 10 '13 at 6:25
  • 2
    $\begingroup$ @YuvalFilmus real world TSP are not necessary metric. Some times traveling from A to B will take longer then AC + CB as there are traffic on the road from A to B. $\endgroup$ – Ilya Gazman Nov 10 '13 at 8:56
  • 1
    $\begingroup$ @Babibu The distance on the edge $(A,B)$ is the shortest distance from $A$ to $B$. In your case, the direct road from $A$ to $B$ is not the shortest distance. $\endgroup$ – Yuval Filmus Nov 10 '13 at 21:33
0
$\begingroup$

There's no general answer to this, except "people aren't stupid." They'll apply the solution that is appropriate to their situation. Rarely are people concerned with the traveling salesperson problem itself. Eveb in the classical instance, a real world salesperson would be more concerned with the problem of maximizing their income over a given time period within a specific set of constraints. In this instance of the problem, total distance traveled is only one of a number of different factors that go into finding the optimal answer.

$\endgroup$
0
$\begingroup$

If repetitions are allowed, then you just go examine all connections X -> A -> Y, and if that is shorter than X -> Y then you replace the length of X -> Y with the length of X -> A -> Y, and solve the resulting problem with the standard algorithm. I think you have to repeat the replacement process until there are no changes, because if you find a shorter connection X -> Y this might mean that now X -> Y -> Z is shorter than X -> Y.

Keep track of which connections you changed, go through the connections in the solution, and if the solution contains X -> Y then you replace this with X -> A -> Y.

PS. I think my idea is great, but I'm not very sure at the moment that it is correct. Because X -> A -> Y instead of X -> Y is not just a shortcut, it also covers city A.

$\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.