Question for the mapping wizards

[FeloniousDunk]

Okay, this question comes as a result of my latest pie in the sky mind wanderings so forgive me if it's plum crazy.  But if this exists, it'd be awesome.

Does anyone know of a way to automate the process of selecting the "best", or at least shortest, route when the goal is to cover all bike legal trails in a given area? 

For instance, given a National Forest with 20 bike legal trails that total 200 miles which intersect in many places, is there software or something that will plot a route that is the shortest way to hit it all? 

And best yet would that tool have a way to set up some quality standards like "trail X needs to be riden east to west because of a nice climb/downhill/etc" or even being able to put in some sort of "prediction of least effort expended" equation that would automatically take into account slope, climb length, etc?

BTW, of course we all lay out such routes all the time on our well known trails based on experience with the area.  But in this case I'm looking for a way to lay out a route in a short time frame for an area that is either to big to wrap your head around or an area unknown by you and with little local info. 

Any insight on such a tool?

[ScottM]

Funny, I was just thinking along these lines.  The answer is, no, there isn't anything out there right now.  No one even does routeable trails.  Well, not in any usable or comprehensive way.

I had the thought about writing some code for doing what you are talking about in order to do a somewhat silly (and very long) day ride (one that would cover every single trail in a pretty extensive trail network near Tucson).  This is going to get a bit geeky now, but you ask a geeky question, get a geeky answer.

I am pretty sure this problem is equivalent to the 'traveling salesman' problem, a classic one in computer science.  It is intractable to get the optimal solution for large networks... meaning computers today cannot compute the answer in any kind of reasonable time frame.

On a 200 mile network (or the one I was thinking about) it may be possible to get the answer, and you could add different characteristics and constraints to it, as well, like you described.

So, if you made it this far, it's a hard problem and not one I see anyone trying to tackle soon.  Except maybe me, because these kind of things keep my brain turning late at night, or when out grinding up a big hill somewhere.  For now just take your best shot at it.  If you were to have GPS data for the whole area you could make a network in TF from it, then construct your desired route by clicking each segment on the network in succession. 

[FeloniousDunk]

Scott, thanks for the geeky answer to my geeky question    I kind of thought that might be the case on the potential for a tool like that.  It amazes me what computers today can do but I guess it still amazes me what they can't do.  If you come up with something, I'll be happy to test it for you on a project I've been thinking about.

[bmike-vt]

i think you could have an easier time with this using road / bike path stuff available in the google maps type api... but translating this to trails would be tricky.

you'd need to provide variables for terrain, and options for how to optimize for the terrain - some sort of 'goodnessometer' - a brutal hike a bike that leads to some nice riding, vs perhaps the computer routing you in reverse to avoid the hike a bike but plummet you down a steep section... and little regard to how things could flow together. the machine would have to have criteria for what grades would be optimal for riding in a matrix of length vs pitch vs pretty flower / scenic meter. and my guess would be that 'optimal' might not be shortest or with the least climbing - but somewhere in between that takes terrain - length - water - scenery - etc. into account. something would need to be written that had some generic parameters in place to 'rank' variables in priority for stitching into a final route...

i'm sure UPS and FedEx have complicated routing algorithms for their daily delivery schedules - but they have plenty of knowns that they only have to apply to the unknowns of particular addresses receiving packages within the same route on different days - so the general flow would be optimized maybe once a quarter, and the daily flow would just be programmed based on volume of packages hitting certain areas along a route. (if they do this at all after their initial optimization...)

cool idea though.

back in my youth, without a computer my brother and i walked and ran a paper delivery route. 200+ customers for some junior high kids to lug newspapers around our neck every morning. through trial and error we figured out the fastest approach with each running down a side of the street, overlapping at certain points, and doing the streets in a certain sequence. we probably figured it out in less than 2-3 weeks with plenty of time not focused on efficiency. motivation was simple - how late could we get up (based on the day, as papers varied in weight / volume throughout the week) and still make it in for breakfast / clean up / and walk to school - so we were optimizing for sleep, a good motivator.

[Mike Brown]

Gee, shaun- what could possibly have made you think to ask this question? 

[AZTtripper]

All of the geekyness aside someone still has to have already mapped out the whole system to have all of the data in the first place.

I know Scott has already mapped all of the trails in our local Mountain Park so it would be a simple (easy for me to say since I don't have to write it) matter of writing the code. If you had already ridden the trails in the most fun direction then the program would just link them in the original direction.

But if everything about the trail is a ? how would the program be able to know what is really on the ground. Even if it knew all of the grades for climbing and descent how could it know that one side is nice and solid ride-able up and then the other side of a hill is all loose and only good as a down hill.

Cool idea tho and Scott doesn't need to sleep much anyway.

[Pawel]

I am pretty sure this problem is equivalent to the 'traveling salesman' problem, a classic one in computer science.  It is intractable to get the optimal solution for large networks... meaning computers today cannot compute the answer in any kind of reasonable time frame.

I agree with Scott that this problem is huge even for modern computers. I think that 'traveling salesman' problem is good point to start with programming some procedures for tasks described by FeloniousDunk. Some researchers try to solve 'traveling salesman' problem using genetic algorithm which is much faster than conventional gradient technique. Here is a link to code written in Matlab related to genetic algorithm application for solving 'traveling salesman' problem with some description:

http://www.mathworks.com/matlabcentral/fileexchange/13680-traveling-salesman-problem-genetic-algorithm

Scott, are you familiar with Matlab? That code maybe useful.

[drwelby]

You could do the routing with something like Graphserver:

http://graphserver.sourceforge.net/

or maybe pgRouting:

http://pgrouting.postlbs.org/

The fun and geeky part will be getting the trail data into the right formats for each system.

[dave54]

ArcInfo will do that easily, but very few people have that software at home.

Contact your local college or university that has GIS courses.  Students are always looking for real world problems to solve.

[FeloniousDunk]

ArcInfo will do that easily, but very few people have that software at home.

Dave54, do you think ArcMap 9.2 has the same capability?  I'm a frequent user and owner of it but have no clue how to make it do this. 

[FeloniousDunk]

All of the geekyness aside someone still has to have already mapped out the whole system to have all of the data in the first place.

That's definitly a hurdle to overcome first but someplaces are fully mapped...not necessarily by someone on a bike with a gps, but mapped none the less.

Getting everything in compatable formats may be another story as others have mentioned.

[FeloniousDunk]

Gee, shaun- what could possibly have made you think to ask this question? 

Just thinking 

[stevage]

>I am pretty sure this problem is equivalent to the 'traveling salesman' problem, a classic one in computer science.  It is intractable to get the optimal solution for large networks... meaning computers today cannot compute the answer in any kind of reasonable time frame.

IMHO this is overstating it. Yes, computing the *absolute best* solution for *very large* networks is intractable. But computing a *very good* solution for a typical number of points (say a few hundred) is feasible. The given example of just 20 or so trails (an interesting variation on the problem!) would compute quite quickly, I suspect.

Now, as to the second part of the problem, routable maps. Get into openstreetmap.org - there are certainly hiking and mountain biking trails around the place in there, and the goal is for everything to be mapped eventually. Much better than just sticking a GPS trace on a website somewhere. As soon as my GPS arrives I'm going to be tracing a few routes for exactly this purpose...

[drwelby]

Dave54, do you think ArcMap 9.2 has the same capability?  I'm a frequent user and owner of it but have no clue how to make it do this. 

You would need the Spatial Analyst or Network Analyst extensions, neither of which are included in ArcMap.

[FeloniousDunk]

You would need the Spatial Analyst or Network Analyst extensions, neither of which are included in ArcMap.

Got 'em.  These extensions will allow me to do this if I can get all the trails of interest in a .shp file?  If so, do you know where I can find a tutorial or atleast an example?

[drwelby]

Got 'em.  These extensions will allow me to do this if I can get all the trails of interest in a .shp file?  If so, do you know where I can find a tutorial or atleast an example?

http://webhelp.esri.com/arcgisdesktop/9.3/index.cfm?id=4314&pid=4313&topicname=An_overview_of_Network_Analyst

[ScottM]

You could do the routing with something like Graphserver:

http://graphserver.sourceforge.net/

or maybe pgRouting:

http://pgrouting.postlbs.org/

I don't think either of those programs will do what the OP is looking for.  Shortest path (typical routing) and traveling salesman code both solve a different problem.  The problem is to cover all trails (edges) in a network, not all nodes.  Traveling salesman covers all nodes.

When I said the problem seemed equivalent to traveling salesman, I meant in the runtime analysis, not literally equivalent.  There is probably some transform that given a "cover all edges" problem, you can generate a graph that would solve the same problem via traveling salesman.  But writing that code would be more difficult, IMO, than solving the "cover all edges" to begin with.  It would only be useful for proving NP-completeness / class equivalence.

Unless I am missing something and either of those can compute this problem?

I am not sure about ArcMap's Network Analyst -- maybe they have some code to do this, but I would be a bit surprised.

[ScottM]

IMHO this is overstating it. Yes, computing the *absolute best* solution for *very large* networks is intractable. But computing a *very good* solution for a typical number of points (say a few hundred) is feasible. The given example of just 20 or so trails (an interesting variation on the problem!) would compute quite quickly, I suspect.

Agreed, I think you could get a very good solution in a reasonable amount of time.  If all else fails, just sample randomly and keep the best.  My point was that this is an interesting problem, and that it is hard to get the absolute best solution -- even for 20 trails.  The most obvious approach -- trying every possible combination (O(n!) runtime), blows up very quickly (you don't want to wait 20 factorial milliseconds... ).

There are a lot of tricks out there to getting good approximations to the TSP problem, many of which would apply to this one, but it is a different problem, so it would require some work, and not all would cross over.

Would love to see some literature on this problem.

[drwelby]

Unless I am missing something and either of those can compute this problem?

I'm not sure either! They both do shortest path, I think with Dijkstra's, but they might be able to do other types of analysis too. Since they're open source, you could at least use them as a framework to build your graph and then implement your own analysis on top of it. It would save you some work, and you'd have access to other developers who would be generally be happy to chat about the problem.

[stevage]

I recall a similar problem once studied was how to visit every station on a certain train network (London underground?) in the shortest space of time. That added the extra, interesting variable of time and scheduling. It was studied intensively by some mathematicians or computer scientists, who then went and tested out their solution by taking trains all day.