Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  lynxlynxlynx Jul 26 '12 at 20:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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