How do salesman handle objections?

Why is the travelling salesman problem specified the way it is?

• The TSP states that the salesman visit each city exactly once. Surely if a real-world salesman is in city A and needs to get to city B, he will not take some long dirt-road just to avoid passing through city C a second time? If the shortest route is actually A-C and then C-B, you could define that as the pair-wise distance A-B, but then it would seem that you're introducing a superfluous variable into an already big problem, since A-C and C-B is already set. Despite such armchair objections, has the TSP been specified the way it is because of some real-world applications or mathematical or computational practicalities?

• Answer:

  The problem requiring that every city be visited at least once easily reduces to another problem called metric TSP which is just regular TSP with the extra condition that the distances all satisfy the triangle inequality ([math]d_{AB} \le d_{AC} + d_{CB}[/math] for all vertices [math]A, B, C[/math]). The reduction is similar to what you already mentioned; given a graph [math]G[/math] with edge weights we can define another graph [math]H[/math] on the same set of vertices where the distance between [math]x[/math] and [math]y[/math] in [math]H[/math] is equal to the length of the shortest path from [math]x[/math] to [math]y[/math] in [math]G[/math]. The graph [math]H[/math] will satisfy the triangle inequality and the shortest tour in [math]G[/math] that passes through every vertex at least once will have the same length as the shortest tour in [math]H[/math] that passes through every vertex exactly once. Your objection that a real-world salesman would not care much about TSP is valid; he would care about metric TSP.