Looping Trails– alternate routing for recreational use (cont.)
Posted by smathermather on September 29, 2011
I’ve been thinking more about the recreational looping problem, given a start location and a given range of travel (e.g. 0-3 miles). A way to approach this is to build up loops from a set of nodes to which has been applied a traveling salesman algorithm. To test this on a piece of paper, before digging under the hood of e.g. pgRouting or OpenTripPlanner, I used a pretend park with trails (in green), with a pretend gridded neighborhood (in pale purple) to select 3 random nodes (numbers) to route through from a given starting point just to see what the outcomes of such an approach might look like.
If you notice, I got confused with the red route in that should have passed through point 9. Here’s my random numbers, 3 random numbers for each route, for a total of 4 required nodes:
- 11,4,6 — Solid Black Line
- 7,5,22 — Dashed Black Line
- 9,2,19 — Solid Red Line
Conceptually, if implemented on the client side this could build loops on any API capable of traveling salesman, given an API wrapper around pgRouting or the addition of traveling salesman routing in OpenTripPlanner, or even using routing from the Google Maps API. Alternatively, the loops could be pre-built on the database side (not randomly, but completely), and then manual or automatic loop prioritization could be implemented to give the series of “best” choices, whether best is determined by miles, terrain, loopyness, trail surface type, mode of travel, etc..