For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

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?

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.

StackExchange Computer Science Q#112807, answer score: 8