CODEWITHSUNDEEP
graph-theorytraveling-salesman
user10323570
user10323570

Reputation:

How to solve Modified Travelling Sales-Man Problem?

The classic travelling salesman problem says you can visit every node exactly once.

I saw this interesting problem which says that you can revisit nodes if this can mean a shorter path.

Ie graph of

1-2-3 (in a triangle. undirected edge weights: 1-2 1

1-3 1

3-2 500

The best path would be going from 1 then to 2 then back to 1 then to three.

The algorithm to solve this I can't quite figure out. If the regular tsp was used, it will lead to infinite cycles.

Upvotes: 2

Views: 923

Answers (1)

LarrySnyder610
LarrySnyder610

Reputation: 2397

You can just replace the distances with the shortest-path distances between each pair of nodes. So in your example, the distances would be: 1-2: 1 1-3: 1 2-3: 2 Then you solve a normal TSP on this instance. The model "thinks" it is visiting every city only once, even though one of the edges actually takes it "through" a city for a second time.

Upvotes: 1

Related Questions