[pgrouting-users] Generating route loops, Removing sticking-out bits

[Greg Allensworth]

Hey all.

I'm using pgRouting to do basic point-to-point routing, and that's gone 
well. We have a second need, though, that's working reasonably well but 
not great. Maybe you have some ideas.

See graphics here:
http://www.mapsportal.org/gregor/tmp/loopspurs.jpg
http://www.mapsportal.org/gregor/tmp/routespurs_trimmed.jpg

- We want to generate loops, so one can go for a walk and wind up back 
where they started. I made up a heuristic for this: basiclaly, pick some 
semi-random waypoints at a distance, do a TSP to sort them, then route 
between each set of waypoints. The results are pretty acceptable a large 
part of the time.

- But, many of the loops include waypoints for which the route to the 
next waypoint is back the way we came. Effectively, you'd walk up a path 
to a waypoint, do a U-turn, and walk back down that same path to get to 
the next waypoint. See WP #5 in the first picture.

So, any ideas on how I can improve my selection of waypoints or the 
routing between them? Is there a new development in pgRouting to do 
multi-waypoint routing with avoidance of backtracking?


Using the current WP-to-WP method, I came up with one idea for removing 
spurs, but it's less than great (see the second image). This looks over 
the segments (edges) and removes any that are present twice (by ID#), as 
they obviously mean backtracking. But this leaves gaps in the middle, 
and eliminates the "trailhead" (making a point that some spurs are good, 
making the question even trickier).


I'm mentally toying with another idea right now:

Keep track of the segments' GIDs, and at each phase attempt a route with 
a "WHERE gid NOT IN ()" clause to see if a route is possible to the next 
WP without touching any previous WPs. If it comes up empty, try again 
but without the GID clause. It seems that this wouldn't eliminate spurs 
entirely, but would greatly reduce them where possible.

In the case of the graphics, you see that without backtracking the route 
from WP 5 to 7 would use that diagonal road, but from 7-9 would take 
some even broader path off the edge of the screenshot. Such meandering 
is entirely acceptable in this case.


Any other ideas?

-- 
Greg Allensworth, Web GIS Developer
BS  A+  Network+  Security+  Linux+  Server+
GreenInfo Network - Information and Mapping in the Public Interest
564 Market Street, Suite 510  San Francisco CA 94104
PH: 415-979-0343 x302  FX: 415-979-0371    email: gregor at greeninfo.org
Web: www.GreenInfo.org     www.MapsPortal.org

Subscribe to MapLines, our e-newsletter, at www.GreenInfo.org