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

pgRouting pgrouting-users
1

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@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

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

2

I think your idea will work, except the case when you are returning to the starting node. Although that could be easily solved by saying “don’t travel any edges I’ve already traveled, /unless/ my target is my home base”.

Another thought is to possibly remove the edges from the route that are duplicated, and then run shortest_path for the places where you have missing edges (you should be able to query for nodes that do not have 2 connections in the solution graph—except you’d ignore the start point since it will only have 1). (This may solve the problem represented in your second picture).

These solutions may restrict your walking paths too much though. There are some edges in your graph that actually require U-turns. Is it acceptable to exclude those outright?

On Fri, Jul 27, 2012 at 12:30 PM, Greg Allensworth <gregor@greeninfo.org> wrote:

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@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

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

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–
Steve Horn

3

On 7/27/2012 10:56 AM, Steve Horn wrote:

I think your idea will work, except the case when you are returning to
the starting node. Although that could be easily solved by saying "don't
travel any edges I've already traveled, /unless/ my target is my home base".

Hey, good thinking there. That does mean other spurs on the last leg, but that's a lot better; and if I add more waypoints or contrive the last one to be closer to home than the others, the stretchb in which spurs may occur is narrowed further. Thanks for the thought.

Another thought is to possibly remove the edges from the route that are
duplicated, and then run shortest_path for the places where you have
missing edges

Interesting. I'm iterating over the solution vertices anyway to find <2 links, could keep track of the node-IDs of "the last kept node" and then "the first kept node after a series of deleted nodes" Hmmmmm.

And then do a shortest-path from the final node to the start, to close the loop. Double-hmmmmm. Again, thanks for the thought.

These solutions may restrict your walking paths too much though. There
are some edges in your graph that actually require U-turns. Is it
acceptable to exclude those outright?

Yes. The effect of WP #5 there, where it weighted the route but didn't in fact fall into the path, is just great. It's the breaks that we don't like, and the whole missing segments for some other more-complicated cases.

I'll be a few days on other projects before I get back to this one. I'll let you know how it works out. Good food for thought here.

--
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@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

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

4

On 7/27/2012 11:42 AM, Greg Allensworth wrote:

Interesting. I'm iterating over the solution vertices anyway to find <2
links, could keep track of the node-IDs of "the last kept node" and then
"the first kept node after a series of deleted nodes" Hmmmmm.

Errr, slip there: Iterating over the vertices to find "visited > 2" anyway, can keep track of the last-known-good node.

--
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@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

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