TSP with Repeated City Visits

Suppose that we have a standard TSP, except that it is required to visit each city at least once instead of exactly once. The challenge is: how to transform this problem to a standard TSP? To that end, one construct a new network with arcs representing the shortest paths between each pair of nodes.

Now the TSP with multiple city visits is equivalent to a standard TSP defined on the new network.

Q: Can somebody explain why TSP with multiple city visits on the original network is equivalent to a standard TSP defined on the new network?

• If you need to visit each city at least once, and that you are minimizing cost, then the optimal solution will visit each city exactly once. Each extra visit is extra cost (if costs/distances are positive). Or in other words, you cannot save money by going to some city more than once. – Kuifje Jan 18 at 11:01
• @Kuifje This only holds if your travel distances between nodes follow the triangle inequality. (Just for completeness sake.) – worldsmithhelper Jan 18 at 11:03
• Yes indeed, excellent point ! – Kuifje Jan 18 at 11:22

However, if your network has nodes $$a$$, $$b$$, $$c$$ such that $$d(a,b) \geq d(a,c) + d(c,b)$$ any path that goes from $$a$$ to $$b$$ will always go through. So you can mark all the edges where this is the case and just use the length of the path of the shortest path between $$a$$ and $$b$$. For example, $$d(a,b) := d(a,c) + d(c,b)$$ Solve the TSP using these updated weights (which no longer violate the triangle inequality) and in your solution, when you travel over the marked edge $$\vec{ab}$$, add the intermediary nodes along which the path is shortest.