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
    Commented Jul 25, 2012 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. Commented Jul 25, 2012 at 23:03

1 Answer 1


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.

  • Great, this makes it pretty easy. For small graphs it's probably not even worth iz to precalculate the new distance matrix, but doing it on the fly instead. Commented Jul 26, 2012 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.