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

[Steve Horn]

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 at 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/loopspurs.jpg>
> http://www.mapsportal.org/**gregor/tmp/routespurs_trimmed.**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
> ______________________________**_________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.**org <Pgrouting-users at lists.osgeo.org>
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-**users<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>



-- 
Steve Horn
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20120727/13349eb3/attachment-0001.html>