# 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.

• Have you looked into graph theory? – nagytech Jul 25 '12 at 22:59
• About as much as the Wikipedia links above and a few links deeper. At uni we only did some trivial LP and decision theory. – lynxlynxlynx Jul 25 '12 at 23:03