1

I want to solve a TSP problem on a set of points from a road network (given N points, find the shortest possible route to visit them all). It seems that pgrouting pgr_tsp function doesn't take into account roads existence - it simply estimates Euclidian distance between the points, so it's like walking by a straight line.

Is there a way to achive what I want with pgrouting? I saw something like tsp_dijkstra function in the old release, but, it's now removed and I cannot find a documentation for it.

Or maybe there're other tools (not pgrouting)?

Thanks.

2

The upcoming release of pgRouting has two TSP functions: one as you describe, using Euclidean distance between points. But the other one takes a distance matrix as an argument, so you can decide yourself if you want (or can) calculate real distances to solve TSP.

See: http://docs.pgrouting.org/dev/src/tsp/doc/index.html

There have been various discussions on the pgRouting mailing list whether the current distance matrix is "user-friendly" or not. So if you try it, feedback is very much appreciated.

1
  • Thanks! Completely forgot this feature (the roads case is even described in official docs). Aug 23 '13 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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