All geek questions in one place

Change TSP that visits several cities

I want to discuss the branch and related solution for TSP with several visits (i.e. each city needs to be visited at least once, and not just once)

Edit:

Doubt resolved as it didn't matter as pointed out by Jitse. Now the question is clearer.

+3
source share
2 answers

Simply increase the graph by adding an edge for each pair of nodes A and B, representing the shortest path from A to B. The Floyd-Warshall algorithm allows you to do this in O (n ^ 3), which is much faster than any TSP algorithm. After you have done this, use the standard TSP branching and binding technique. This site contains some information from the Applegate book , which discusses the branch and is tied to the TSP according to the entry on the Wikipedia TSP .

+6
source

I would rather present this as a comment on Martin Hawk's answer, because I am addressing a possible oversight that would be easy to do by implementing his proposal.

The branching and binding algorithm should be combined with the least cost path restoration algorithm taking into account the output of the Floyd-Warsall algorithm. The branch and bound algorithm is an outer loop, and it selects invisible nodes. Then you use the least cost recovery algorithm to actually add edges and nodes to your loop. The nodes should be marked as visited by the least cost recovery algorithm, not just the branch and related part.

+2
source

Source: https://habr.com/ru/post/1432523/

More articles:


All Articles