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".<div>
<br></div><div>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).</div>
<div><br></div><div>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?</div><div><br></div><div><br>
<br><div class="gmail_quote">On Fri, Jul 27, 2012 at 12:30 PM, Greg Allensworth <span dir="ltr"><<a href="mailto:gregor@greeninfo.org" target="_blank">gregor@greeninfo.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hey all.<br>
<br>
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.<br>
<br>
See graphics here:<br>
<a href="http://www.mapsportal.org/gregor/tmp/loopspurs.jpg" target="_blank">http://www.mapsportal.org/<u></u>gregor/tmp/loopspurs.jpg</a><br>
<a href="http://www.mapsportal.org/gregor/tmp/routespurs_trimmed.jpg" target="_blank">http://www.mapsportal.org/<u></u>gregor/tmp/routespurs_trimmed.<u></u>jpg</a><br>
<br>
- 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.<br>
<br>
- 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.<br>
<br>
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?<br>
<br>
<br>
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).<br>
<br>
<br>
I'm mentally toying with another idea right now:<br>
<br>
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.<br>
<br>
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.<br>
<br>
<br>
Any other ideas?<br>
<br>
-- <br>
Greg Allensworth, Web GIS Developer<br>
BS A+ Network+ Security+ Linux+ Server+<br>
GreenInfo Network - Information and Mapping in the Public Interest<br>
564 Market Street, Suite 510 San Francisco CA 94104<br>
PH: <a href="tel:415-979-0343%20x302" value="+14159790343" target="_blank">415-979-0343 x302</a> FX: <a href="tel:415-979-0371" value="+14159790371" target="_blank">415-979-0371</a> email: <a href="mailto:gregor@greeninfo.org" target="_blank">gregor@greeninfo.org</a><br>
Web: <a href="http://www.GreenInfo.org" target="_blank">www.GreenInfo.org</a> <a href="http://www.MapsPortal.org" target="_blank">www.MapsPortal.org</a><br>
<br>
Subscribe to MapLines, our e-newsletter, at <a href="http://www.GreenInfo.org" target="_blank">www.GreenInfo.org</a><br>
______________________________<u></u>_________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.<u></u>org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-<u></u>users</a><br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br>Steve Horn<br><br>
</div>