5
$\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?

Improve this question
$\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, 2021 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, 2021 at 11:03
  • $\begingroup$ Yes indeed, excellent point ! $\endgroup$
    – Kuifje
    Jan 18, 2021 at 11:22

1 Answer 1

Reset to default
9
$\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.

Here is the algorithm applied to the graph @byteherder suggested. After the preprocessing has run a vanilla DSP solution is as good as the suggested best solution.

enter image description here

Improve this answer
$\endgroup$
5
  • $\begingroup$ This answer is incorrect. Consider the problem when you want to go from a->b but to meet the constraints of TSP you need to go a->c->d->e->b. Now if you had the ability to go from a->f->b that would be shorter. Why didn't we go through node f in the TSP? Because node f had already be visited once and the constraint in TSP does not allow it to be visited again. $\endgroup$
    – byteherder
    Aug 12, 2022 at 20:40
  • 1
    $\begingroup$ I think your counter example fails. If a->f->b would be the shortest path between a and b, so would a->b by my weight updating procedure, so even if f was previously visited. a normal TSP solver would not be constrained from going a->f->b again by going a->b instead, which is as good if not better. I am open to counter examples though. If you present a graph with non negative edges, which after my edge weight updating rule (which applies to all paths, not just paths with exactly one stop in between) makes no changes has TSP longer than a tour you suggest which visits every city once i listen $\endgroup$
    – worldsmithhelper
    Aug 12, 2022 at 21:21
  • $\begingroup$ Here was the example I was thinking of. Consider a complete graph with vertices 1,2,3,4 and edge costs c12=c13=c14=1 and c23=c24=c34=100. TSP distance = 202 (1 -> 2 -> 3 -> 4 -> 1). TSP with Repeated City Visits distance = 6 (1 -> 2 -> 1 -> 3 -> 1 -> 4 -> 1) $\endgroup$
    – byteherder
    Aug 12, 2022 at 21:28
  • 1
    $\begingroup$ @byteherder please that a look at the updated message that gives a bit more explanation how my approach works and why your "counter" example doesn't work. $\endgroup$
    – worldsmithhelper
    Aug 12, 2022 at 21:55
  • $\begingroup$ I understand your algorithm reweights the edges that violate the triangle inequality. The new graph isn't the original TSP but a new equivalent one. The repeated visits form the weights for the new edge. So now we have transformed our original TSP with repeated visits into a TSP equivalent problem. Did I get that correct? My original thought upon reading your answer was that a triangle inequality could not be constructed. I had a counter example to that but I now see that you mean after transformation. $\endgroup$
    – byteherder
    Aug 12, 2022 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.