2
$\begingroup$

Traditionally, the traveling salesman problem has you visit a city at least once and at most once.

However, if you were an actual traveling salesman, you would want the least cost route to visit each city at least once, and you wouldn’t be bothered visiting a city 2, 3, or more times. For given city, you might stop and hawk your wares only once, and on subsequent visits, only drive through the city without stopping.

Consider an undirected graph having a city incident to exactly two edges. The cost on one of these edges is only 10 units, while the cost on the other is 99,999,999,999. If you insist on visiting each city at most once, then you are forced to incur the cost of the high cost edge. However, if you allow yourself to visit cities multiple times, then you simply leave the way you came in (on the low cost edge). The low cost edge leads you back to a city you've passed through before.

The traveling salesman problem is highly contrived for an actual traveling salesman. I want to give students an application for which there's a real incentive to visit each city at most once. For what applications is visiting each city a critical aspect of the problem?

$\endgroup$
  • $\begingroup$ It's a problem in graph theory, and it is quite natural as the vertex version of an Eulerian tour with edge weights (which are also an usual feature of graph-theoretic problems). I doubt the original motivation was actually trying to make the lives of traveling salesmen easier in any way. $\endgroup$ – dkaeae Aug 16 at 14:08
  • 1
    $\begingroup$ @dkaeae There must be some application besides a literal traveling salesman. Otherwise, the problem has no reason to be well studied. $\endgroup$ – Toothpick Anemone Aug 17 at 2:23
  • $\begingroup$ @ToothpickAnemone I suspect that it's well-studied partly because it was one of the first "real-world" problems to be proven to be NP-complete, so it shows that NP-completeness isn't just some theoretical property that only applies to abstract maths problems. I believe another application is in programming robots to attach components to circuit boards: the robot needs to place, e.g., resistors at points $x_1, \dots, x_k$ on the board and you want to find the shortest path that visits all those locations. $\endgroup$ – David Richerby Aug 17 at 10:06
6
$\begingroup$

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not.

In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that includes every vertex exactly once, and which therefore doesn't repeat any edge. That's just the definition; it's a problem about graphs and it may or may not correspond to any particular problem in the real world.

In TSP, we are given the cities and the matrix of distances between them. That's all the values are: distances. In particular, there is a distance between every pair of cities, regardless of what the road network looks like. You need to visit each city and your job is to choose the order in which to visit them, to minimized the total journey length. For example, consider the following distances:

                 B    P    W
Baltimore        -   100   40
Philadelphia    100   -   140
Washington DC    40  140   -

The shortest route is to, say, start in Philadelphia, drive to Baltimore, drive to DC, then drive back to Philadelphia. If the distances look a bit strange, it's because I-95 runs from Philadelphia to DC and passes through Baltimore. This means that "then drive back to Philadelphia" means passing through Baltimore again. This doesn't matter, because TSP isn't modelling that. It's just modelling visiting each city and completely ignores what happens en route between cities, except for the distances.

In contrast, if you represented this as the graph

    40       100
W ------ B ------- P

then there is no Hamiltonian cyle at all. This doesn't correspond well to the idea of travelling between cities: as you rightly ask, why not allow yourself to drive back through Baltimore? Should we add in a road from Washington to Philadelphia that doesn't go via Baltimore? That seems weird, as it would be longer. Why force yourself to do that? TSP isn't Weighted Hamiltonian Cycle.

The formal relationship between the two problems is that TSP is the restriction of weighted Hamiltonian path to the case where the graph is complete. Alternatively, you can associate a weighted Hamiltonian path instance as corresponding to the TSP instance where there's one city per vertex and the distance between two cities is the length of the shortest path between the corresponding vertices.

Note that, in the above, I've referred to the "distance" between cities. Even more formally, one should talk about an abstract "cost". The distinction is that distance sounds a lot like it ought to be symmetric and obey the triangle inequality, which corresponds to metric TSP. Cost isn't necessarily either of those things.

$\endgroup$
  • $\begingroup$ I am not sure why you say the graph being complete is a big difference between the TSP and the problem of finding a least cost Hamiltonian Cycle. Suppose C is a complete undirected graph. Let VS(C) denote the vertex set of C and let ES(C) denote the edge set of C. Let Ck be a mapping from the edges of C to costs taken from the set ℝ+ ∪ {+∞}. Suppose that {e1, e2, and e3} ⊆ ES(C) and for all E in {e1, e2, and e3}, Ck(E) = +∞. Let NC be a non complete graph such that the vertices of NC are the verities of C, and VS(NC) = ES(C)/{e1, e2, and e3}. $\endgroup$ – Toothpick Anemone Aug 16 at 22:48
  • $\begingroup$ If you have a complete graph having edge weights of ∞, and you remove the edges having weight ∞, then the result is, for all intents and purposes, equivalent to the original graph. The resultant graph is incomplete, but who cares? You can also go the other direction: take a graph which is incomplete, and add edges until it is complete. Then make the weights on the new edges each be +∞. $\endgroup$ – Toothpick Anemone Aug 16 at 22:53
  • $\begingroup$ Suppose that you have a weighted graph G. Each vertex of G models a real-world city. An edge in G models a road between two cities not passing through any other cities in vertex set.Now, the vertex set of graph H is the same as the vertex set of graph G.However, the weight on an edges of H are different. For all verticies v, w in H the weight on edge {v, w} is the summed weight of the shortest path from v to win G. Thus, an edge in H might model a road passing through a dozen different cities.You say H is what the TSP problem uses? $\endgroup$ – Toothpick Anemone Aug 16 at 22:57
  • $\begingroup$ @ToothpickAnemone "If you have a complete graph having edge weights of ∞" I don't. I have a complete graph with finite, positive weights. Or, rather, I could have infinite weights, but that's not going to correspond to any TSP instance, because the distance between any two cities is going to be finite. $\endgroup$ – David Richerby Aug 17 at 10:00
  • $\begingroup$ @ToothpickAnemone Yes, TSP is min cost Ham cycle on the graph you're calling $H$. TSP abstracts away from roads and routing and just looks at distances. It doesn't specify whether the route from A to B happens to go through C; it just knows how far A is from B. In terms of explaining it to students, it might help to distinguish between actually visiting a city (stopping there to sell stuff) versus merely passing through on the way to somewhere else. $\endgroup$ – David Richerby Aug 17 at 10:02
0
$\begingroup$

The question is whether the distances between cities fulfil the triangular equation: For any three A, B and C, is distance (A, B) ≤ distance (A, C) + distance (C, B)?

In your example, where distance (A, B) = 10, distance (C, B) = 1,000,000,000 and distance (X, B) = infinite (or very, very large) for all other X: Yes, it seems that going A->B->A avoids the long distance from B->C. However, if your distances fulfil the triangular equation, then we must have distance(A, C) ≥ 999,999,990, and distance (A, X) for any other X must be huge. So it is not at all obvious anymore that A->B->A is actually of any advantage.

Actually, if you find the shortest tour starting at A, visiting each city at least once and returning to A: Find a B that is visited twice if there is one. There will be some connection X->B->Y. With triangular equation, the distance X->B->Y is not shorter than X->Y, so you can replace X->B->Y with X->Y, and get a tour that is not longer, and which still visits every city at least once. Therefore, with triangular equation, being allowed to visit cities twice doesn't improve the optimal solution.

I'm not quite sure what happens if you give me a list of distances, and I can enforce that they are triangular, by replacing distance (A, B) with the shortest distance of any path going from A to B, visiting any number of cities in between.

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