Question for the mapping wizards

[protoceratops]

Sounds like CS folks...real mathematicians would never test a solution against "real life" !

disclaimer:  I are one...

[ScottM]

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.

Taking trains all day?  Boring... 

Riding bikes all day to test a solution?   

You do bring up a good point.  Adding other constraints (one way trail, difficulty, fun factor, steepness), as others have suggested, would further complicate the problem and likely render other approximation approaches to TSP unusable.  At this point I'm just looking for the minimum length tour that covers all trails, though.

Still, in your example they are looking at hitting every station, not hitting every inch of track in the network.

[stevage]

>Still, in your example they are looking at hitting every station, not hitting every inch of track in the network.

I know nothing of graphing theory, but I suspect these are just variations on a theme. The specifics of the algorithms will change, but the concept is the same.

Is there an online map of this area? I'm thinking a couple of hours with pen and paper would yield pretty good results

[protoceratops]

Yes, weighting the various aspects of the individual segments makes the number of variables grow considerably.  
Pretty soon you are looking at O(100!) ms.  Or more.

Yikes!

And what you get back may very well be like computer-generated music.  Logical, but not much fun.

+1 to the pencil and paper idea...

[ScottM]

I know nothing of graphing theory, but I suspect these are just variations on a theme. The specifics of the algorithms will change, but the concept is the same.

I think so, though I haven't fully convinced myself of it yet.  It is, however, enough of a variation that any traveling salesman code will not give a useful solution.

Is there an online map of this area? I'm thinking a couple of hours with pen and paper would yield pretty good results

Yep.  I am thinking of offering it as a challenge in our local trail system here.  Exact shortest solution - not computable and perhaps still not the fastest.  Come up with your best guess / preferred route, and see how long it takes.  Shortest ride time "wins."  Ride / race it any day.  I like it that it's not clear at all which route is best.

One problem, also, is remembering what the intended route actually is and being sure you actually cover every trail once out there!  Just uploading a track to a GPS won't cut it, due to the inevitable backtracking.  A route following a series of waypoints might do it, or just the old fashioned way - print out a map, number the trail intersections and then write down a sequence of numbers.

[FeloniousDunk]

Whoa guys, this is exciting and I don't have a clue what you're talking about, but it sounds like a plan is coming together, or not, but it's fun to try.    Thanks for entertaining my inquiry so far!

Yep.  I am thinking of offering it as a challenge in our local trail system here.

ScottM that's basically the same thing I was thinkering on when I posed this question.  Given my lack of original ideas I figured some others must have been thinking about similiar things

Mike B,     

Is there an online map of this area? I'm thinking a couple of hours with pen and paper would yield pretty good results

True, true, but where's the fun in that?   Actually, I've poured over maps the old fashioned way a lot and for a big pile of trails it takes a surprising amount of time.  Some of that work has resulted in a couple adventurous though less than ideal bikepacking trips through NC and VA exploring for a long east coast route.  Maybe such a tool could have helped that.  Though, that's not exactly what I'm looking for right now.  Primarily, I'm looking for the shortest way to cover every trail in an area and if we can sort by some quality standards then GREAT!

But of course I might be able to do the old fashioned way in this particular case because I am thinking of a particular trail system, but if someone wanted to do this same exercise for other areas, I think an automated tool would be nice to have.  Plus, my 20 trail-200 mile goal could expand a lot if I had a good tool that could assist.  This particular area doesn't have one online map that covers all the trails, but between a combination of stuff I have such as Nat. Geo. software maps, Forest Service shapefiles, a very few gps tracks, and hard copy maps that I could probably digitize into shapefiles, I think I can get everything into one format.

I don't think either of those programs will do what the OP is looking for.  Unless I am missing something and either of those can compute this problem?

ScottM, thanks for an analysis of those tools because I started reading about them and couldn't figure out how to do what I wanted with them, but honestly that was primarily because they look way above my CS rank!  If I'm wrong about their abilities, someone please let me know.

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

drwelby, thanks for the link and idea.  ArcMap frequently amazes me by what it has "hiding" in the background.  I'm fairly proficient with it for what I do regularly but Network and Spatial Analysis are not one of those things.  At the moment, I glance at that tutorial and am a bit overwhelmed with the idea of trying to learn it.  I went through this before with 3D Analysis just to find that my computer would crash every time I tried to run it at the scale I needed it to be useful.  I kind of don't want to do that again.  So, at the risk of sounding lazy, do you know of a link in that tutorial or elsewhere that shows an example of the final results of this sort of problem solved with these extensions?


If I can help in a practical way to develop something like this, as opposed to asking a lot of questions, let me know.  Thanks guys and looking forward to more brainstorming. 

[jhl99]

Another vote for paper and pencil or your favorite computer mappping tool.  I've found AutoCAD useful for digitizing trails from topo maps (DRGs) and adding track/waypoint data.

FD:  can you identify where this 200 mile network of trails is?

"Some of that work has resulted in a couple adventurous though less than ideal bikepacking trips through NC and VA exploring for a long east coast route.  Maybe such a tool could have helped that"  FD

I see only limited benefit from this route finding excercise (besides the challenge of solve the 'problem').   The issue of an Eastern Route (or having the most fun in a given riding area), is not necessarily finding the shortest route (even in a racing scenario) , but accumulating the first hand  (or info from a good source) knowledge about the suitability of the trails for the intended use and linking the desirable points of interest. 

**
This whole thing reminds me of a conversation I had a rest stop on the interstate many years ago.  This was the early days of MapQuest.  I was offering assitance to a couple with car difficulties.  We where at a rest stop  due S of Pittsburgh, PA  I asked the driver where they from and where they where going.  They told me they where from the DC area and they where headed to NE of Pittsburgh.  I asked them why they picked the route they took because they probably added 100 miles to there route compared to the most direct, interstate route.  The answer they gave is that they hadn't checked a map and where just following the MapQuest directions.

edit=added Mapquest story

[FeloniousDunk]

FD:  can you identify where this 200 mile network of trails is?

Absolutely, and I see it'll be helpful to be more specific about what I'm trying to do.  I specifically have the Pisgah National Forest here in Western North Carolina in mind.  I only think that's one example of where this could be done, therefore a tool that could automatically repeat the process would be nice.

Here is specifically what got me thinking about this question.  Our local hiking club has a few standing challenges that I think are cool for many reasons.  Two of the challenges are to hike every trail in the Pisgah National Forest - Pisgah District and one for the Smoky Mountains National Park. 

During a tiny storm in my brain I decided it'd be cool to have just such a challenge presented by our local mountain biking club to ride every bike legal trail in the Pisgah National Forest.  The Pisgah that most people hear about is just one of three Districts in the Pisgah National Forest.  It's called the Pisgah District.  That's where most, but not all, the Pisgah trails are.  Some are in the Grandfather and the French Broad Districts as well.  Some of us locals have ridden the Pisgah Districts' 300 or so miles of bike trail enough that we could lay out decent routes to cover it all, but that doesn't go for the other two Districts.  Of which I'm very roughly estimating there's approximately 20 trails and 200 miles.  I originally thought about a Pisgah District Challenge, but why not make it interesting to even the hardiest of riders and include all the Districts in the Forest.

The hiking clubs challenge designates no time limit nor specific route.  As a result, most people section hike them over years, which is cool, but a very few go for it as fast as they can in one push, also cool.  For some reason I think if such a challenge was presented to the mtb community some of the first people to try it would try it as one push.  And if that first person was me, starting with an idea of the shortest route to connect them all would be a great asset to start planning from. 

BTW, jhl99, your help in laying out a track for my trip up through VA last summer was a good help.  I think a linear route, utilizing only some of the available trails in an area, like that route, is only vaguely related to what I'm thinking about here.

[ScottM]

Thanks for the background on what sparked your interest in this.  I like the idea of a standing challenge of this nature, whether on foot or wheels.  I hadn't thought of making it something you could do over a long period of time.  E.g. ride all trails in the Tucson area.  Cool.

So, I stopped speculating on the problem and started looking it up.  Once I starting reading a bit the "Chinese postman problem" started to ring a bell, and sure enough:

http://en.wikipedia.org/wiki/Route_inspection_problem

It is solvable in polynomial (reasonable) time in the most simple case -- that where the graph is undirected with the same weight for each trail, regardless of direction.

Here is a bit of further info, for those inclined:

http://eie507.eie.polyu.edu.hk/ss-submission/B7a/

If you add directional constraints, it becomes much harder and in the same class of problems as traveling salesman (see http://www.itl.nist.gov/div897/sqg/dads/HTML/chinesePostman.html)

The solution seems elegant and straightforward enough at first glance.  I will have to dig into the details and see how hard it would be to add to TF.  One additional constraint I thought of is that in a trail network you can only start at certain nodes (trailheads).  Unless you have a helicopter at your disposal.  I am not sure if this affects the computation of the optimal Euler tour.  Also, the ending node may be a consideration.  For the challenge I have in mind it'd be nice to end up on the same 'side' of the area that you started.  Shuttles =  , and riding a bunch of pavement to get back doesn't make it very optimal.

[Majcolo]

For some reason I think if such a challenge was presented to the mtb community some of the first people to try it would try it as one push.

This project sounds way fun.

[jhl99]

I think that adding the direction component would be critical given the area of interest is the Pisgah.

FD:  I might be able get you a little data, but you might already have it.  Here is what I definitely have in vector format:  http://home.windstream.net/JHLange/PNF_OverviewMap.pdf

I might have some data on the Wilson Creek Area (not sure which district that is), but I'd have to check at home.

[FeloniousDunk]

FD:  I might be able get you a little data, but you might already have it.  Here is what I definitely have in vector format:  http://home.windstream.net/JHLange/PNF_OverviewMap.pdf

I might have some data on the Wilson Creek Area (not sure which district that is), but I'd have to check at home.

Interesting map jhl.  Is that something you made? 

Wilsons is in the Grandfather District.  I don't have much in the way of digital maps on it.

[FeloniousDunk]

So, I stopped speculating on the problem and started looking it up.  Once I starting reading a bit the "Chinese postman problem" started to ring a bell, and sure enough:

http://en.wikipedia.org/wiki/Route_inspection_problem

It is solvable in polynomial (reasonable) time in the most simple case -- that where the graph is undirected with the same weight for each trail, regardless of direction.

I just learned a lot in those links.  I should have know, but didn't, that this is a mathematical problem as much as a "mapping" problem.  Coincidentally, I have two math professor friends.   One advises some masters students and has even asked if I had some mathematical problems (through my work) which they may be able to help on for projects.  I'll ask if this sort of thing is with in their realm.  Hum?

[bmike-vt]

free college labor!

seems that since folks have found the red balloons so the military can figure out how to tap into our social networks... they should have plenty of time to solve a mapping / math problem!