My younger son, Adam Smith Palmer, is studying computational physics and recently mentioned "the Traveling Salesman Problem" [TSP]. No, the TSP is not a problem involving where or with whom a visiting traveling salesperson must sleep when his/her car breaks down and s/he seeks assistance at nearby farm house. Here, from Wikipedia, is a description of the problem:
Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city?My question is: Why does the problem require or constrain the salesperson to visit each city once and only once?
... It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem.
- I can readily imagine there might be solutions in which it is cheaper, even necessary, for the traveling salesperson to visit some cities more than once to reduce the costs of visiting other cities.
- For example, how can one arrive at a solution if the problem involves a city at the tip of a peninsula with only one road in and out (e.g. Tobermory, Ontario, at the tip of the Bruce Peninsula, ignoring the ferry to Manitoulin Island)? This question reminds me of the old joke about Poland and the Mongol hordes.
- And from the revenue side, the constraint that the formulation of the problem, requiring the salesperson to visit each city no more than once, seems to assume that the incremental or marginal revenue of visiting a city more than once during the grand trip would be zero. Surely it is plausible that visiting some cities more than once and some cities not at all would be more profitable than the constrained solution of visiting each city exactly once.