Traveling Salesman problem without restriction on the number of visits

Question

I have a problem similar to Traveling Salesman (TSP). I found some libraries to solve the Traveling Salesman problem. However, I would like to remove the restriction of visiting each city only once. How do I find the shortest path that visits each city at least once?

Answer 1

One simple way is through preprocessing. Replace each c(i,j) by the length/cost of the shortest path between i and j. Now apply standard tsp. When reporting, insert these shortest paths in the solution. This may result in cities being visited multiple times.