Variation of TSP which visits multiple cities

Question

I am looking to discuss branch and bound solution for TSP with multiple visits.(that is every city needs to be visited atleast once , instead of just once)

Edit:

Removed the doubt as it was not relevant as pointed by Jitse. Now the question is more clear.

Answer 1

Simply augment the graph by adding, for each pair of nodes A and B, an edge 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. Once you've done this, use a standard TSP branch and bound technique. This site has some information from Applegate's book, which discusses branch and bound for TSP according to the Wikipedia TSP entry.

Answer 2

I'd rather submit this as a comment on Martin Hock's answer because I'm addressing a possible oversight that would be easy to make implementing his suggestion.

The branch and bound algorithm needs to be combined with an algorithm for reconstructing least cost paths given the output of the Floyd-Warshall algorithm. The branch and bound algorithm is the outer loop, and it selects unvisited nodes. Then you use the least cost path reconstruction algorithm to actually add edges and nodes to your cycle. Nodes should be marked as visited by the least cost path reconstruction algorithm, not just by the branch and bound part.