3

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.

Kazoom
  • 5,659
  • 16
  • 56
  • 69
  • I don't see why Martin's approach wouldn't work. The augmented graph would have an added edge E -> A, corresponding to going from E via C to A (in fact, the augmented graph has an edge X -> Y for any vertices X and Y). The solution of the TSP for the augmented graph is, say, A-B-C-D-E-A, and since E-A in the augmented graph corresponds to E-C-A in the original graph, this corresponds to the solution A-B-C-D-E-C-A in the original graph. – Jitse Niesen Sep 22 '09 at 08:50

2 Answers2

7

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.

Martin Hock
  • 944
  • 4
  • 5
  • thanks, but would not this approach fail where tsp is not possible in a given graph but actually tsp with multiple visit is possible? like consider placement of cities by imaging two triangles sharing exactly one vertex and each vertex is city. TSP cannot be done here as the shared vertex has to be visited only once, but tsp with multiple visit should work, in your approach even the later would fail – Kazoom Sep 22 '09 at 06:39
  • In any multi city TSP, every city must be visited a last time. Just consider the list of cities forming the last time each city is visited. The paths separating those cities must be shortest paths in an optimal multi city TSP. – Martin Hock Sep 22 '09 at 06:54
  • Martin, i have edited the question, for explaining myself in a better way.thanks – Kazoom Sep 22 '09 at 07:16
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.

Jeremy List
  • 1,756
  • 9
  • 16