algorithm - Are there any intelligent travelling salesmen?

Jokes aside, I have had a routing problem that is almost a travelling salesman problem (TSP):

• the starting point is defined



• the end point coincides with the starting point


• each node has to be visited


• the total cost should be minimised

Two years ago I thought TSP would be a perfect match, so I ran some sample data through tsp_solve and Concorde. Luckily, it was quickly obvious that the TSP shortest path is not the real shortest path, since the problem is made easier by unrealistically requiring the nodes be visited exactly once. This picture is just a one-step manual attempt at optimisation of the computed solution and already it saves about the distance of the longest used edge.

The problem resurfaced, as I'm trying to find optimal routes to subsets of mapping/monitoring sites. Location and road network data is both pretty accurate and precise, so an exercise like this makes sense.

I've looked at generalisations of the TSP, but didn't find an appropriate algorithm. Minimum spanning trees don't account for returning from branches (the 1st solution here costs 3 more). From what I understand, the shortest path problem eventually only cares about two nodes and those out of the optimal path would be left out. A special case of the vehicle routing problem seems to fit best, though I don't know if it considers non-direct paths.

My question: is there any settled name, definition for this kind of problem (family)? What algorithm and tool would you use to solve it?

I'm sure it would be computationally heavy, but I'm interested in both general (infinite resources) and practical answers.

Answer

This is TSP. You just haven't defined a valid distance metric because it does not satisfy the triangle inequality: if there is a route from A to C through B which is shorter than the stated distance from A to C, then the stated distance from A to C is, quite simply, wrong. The solution is to update the distance matrix by setting the length from A to C to be the shortest length of all routes from A to C.