Variation of TSP which visits multiple cities

views:

203

answers:

+1 Q:

Variation of TSP which visits multiple cities

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.

+3 A:

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 2009-09-22 06:34:07

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 2009-09-22 06:39:37

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 2009-09-22 06:54:38

Martin, i have edited the question, for explaining myself in a better way.thanks

Kazoom 2009-09-22 07:16:49

ansaurus

tags:

views:

answers:

Variation of TSP which visits multiple cities

related questions