Search code examples
algorithmoptimizationtraveling-salesman

Traveling salesman problem when not all cities are connected and with the possibility of multiple visits

I have a problem to solve that I think is the Traveling Salesman type. I know that the traveling salesman problem most commonly discussed restricts the number of visits in each city to just one visit and that the city must all be accessible from any point. However, in the real world, this is not always possible. For example, let's examine the figure below. enter image description here Solving this problem via the problem of the usual traveling salesman (using the TSP library of R) I have a travel cost of 440 km (A -> B -> C -> D -> A), for example. However, in the second image (trying to simulate the real world) I find a smaller path, with a cost of 400 km (A -> B -> C -> B -> D -> B -> A).

What I would like to do is visit all cities with the shortest possible distance, regardless of the number of visits. There must be something ready about it, but I couldn't find it. Does anyone have any suggestions?

Thanks in advance.

Solution

  • TSP as you describe it is reducible to "real" TSP.

    You have a graph, with the problems being that not every vertex is connected to every other vertex, and the triangle inequality does not hold. That is, even if two vertices are connected, their connection is not necessarily the shortest path between them. Note here that if your graph was complete, and if the triangle inequality held, then we can easily prove that the shortest path never requires visiting the same city twice.

    So, how to transform your problem into the "proper" problem? We simply need to calculate the actual shortest path distance between every two vertices, and set that to be the distance between the two vertices. We can then use any TSP solver, and if we also remembered the shortest paths, we can then transform it back into a solution to the original problem.

    To find the shortest paths I'd recommend Floyd-Warshall. This may not be entirely optimal depending on the exact graph, but that doesn't really matter as solving TSP will be significantly more complex anyway.

    Example for your graph:

    First, we find the shortest paths between every pair of vertices in the graph:

    A-B: 100; A,B
A-C: 150; A,B,C
A-D: 150; A,B,D
B-C: 50;  B,C
B-D: 50;  B,D
C-D: 100; C,B,D

    Now we put these distances into a new graph, feed that into a TSP solver, and we get (for example) the following result:

    A -> B -> C -> D -> A

    Now, we know the shortest paths between any two vertices in our original graph, so we can just substitute these paths for the paths in the TSP result:

    A -> B -> C -> B -> D -> B -> A

    and this is then the actual shortest path that visits all cities, or one of the shortest paths if there are multiple.