3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Kuifje Jan 18 at 11:01
  • 2
    $\begingroup$ @Kuifje This only holds if your travel distances between nodes follow the triangle inequality. (Just for completeness sake.) $\endgroup$ – worldsmithhelper Jan 18 at 11:03
  • $\begingroup$ Yes indeed, excellent point ! $\endgroup$ – Kuifje Jan 18 at 11:22
6
$\begingroup$

If the distance between your nodes follows the triangle inequality (you can never travel faster between two points by adding an intermediary step), then the shortest path visits each node only once.

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.

In summary, TSP with Repeated City Visits without additional constraints (such as carrying packages) is equivalent TSP and only the slightest bit interesting when you violate the triangle inequality.

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