Route Optimizer within Virtual GPS?

Question

Does Project-GC have any plans to add functionality to Virtual GPS to build / recommend optimized travel routes based on shortest time or shortest distance?

Answer 1

A test implementation was made several years ago, but in my opinon, there is no good generic way to do it.

There are two ways to implement this.

1. Routing on roads. This will be horrible if the geocaches aren't on roads. At least if the distance between them aren't much greater than how far into the woods they are. 
2. Using the flight distance. If the geocaches are fairly close to each other, ie same city, this won't tell anything about the driving distance.

Thought through or experienced inputs are welcome on the topic.

Comments

Is automatic routing neccecery?
An alternative is to have a possibility to add a manual order and display the route between them on the map. If the path on the map is a straight line och a road path will still be a problem. but only displaying straight line would help or the possibility to chose the routing metod yourself. There also exist more routing alternative like walking and cycling
If could choose routin metod and click on a cache on the maps and the click on the next cache. And the map shows the routing of your choose between the points
Showing parking coordinates on the map and have the possibility to add your own and use the.
And some automatic help function like to select a numer of caches with the lasso tool and connect them wit the shortest flight distance and use the routing och you choose. The result will not always good but you can fix the problem manual.

That would be a nice way plan a trip so you dont have to keep that part of the planing in your head. Just ordering the caches and line between them in order on the map would be relay helpful. If you print the plan as i often do you dont have to reorder the after you export.

For an auto metod will there not always be a execution time problem when a travelling salesman problem i hard. I thing google maps only optimise for 10 nodes
A perhaps unsolvebel part (with existing data) of this is where can you park your car to go to a cache? can you stop along the road och do you need to find a nother place. I dont think possible parking places that i have used along roads in geocaching is marker on maps. I am not sure even the official parking places along roads like in sweden are on maps. Parking coordinates on caches could be used
 I don thin any online routers relay know about parking

---

I don't think there is a sufficiently robust data set available to give you the base info. In order to successfully measure the best optimised route. This is a version of the travelling salesman problem which is a complex to solve, in programming terms it is NP-Hard. There is currently no known algorithm that can efficiently solve the problem. There are plenty of algorithms that provide acceptable solutions however they rely on having solid data sets of the time it takes to travel between each node on the graph.

I don't think that it is possible for many caches to know how long it takes to get to them, from another point. For some it's fairly simple eg: road based caches for others the datasets just won't exist. Eg: time takes to climb through forest with no tracks. Without data the guys at project-GC would struggle to be able to produce sensible results.

However the biggest problem is that it would generate a whole new class of complaints about how the result of any "does lots of caches but not off road/path ones" algorithm didn't produce an answer that the user was happy with. You'd get the "everyone knows that if you go up the I5 and turn off at junction X then you'd get a better route".

So I think the biggest issue is lack of data sets to user, the secondary issue is getting an algorithm that doesn't just swallow up all the processing power and kill the rest of the site, and finally the user expectation of quality of a result due to lack of understanding of the problem complexity.

All said its not something that there is probably the resources to tackle. I've been looking at a similar project to produce an iso-chrone map of caches from a home location. Ie: a map shaded by travel time to caches from a set location and came across similar issues. In theory you could do it using public APIs such as Google's mapping and travel time API but for off road caches you run into difficulties with a lot of caches.

---

As the comments above suggest this is not a straightforward question to answer.  However just a quick two cents to add to this, chasing the perfect may not be the correct solution either.  For some folks a 80% solution may be good enough.

Not to start a holy war, GSAK has a CacheRoute3 macro that uses google maps as a backend for computing distance. This has been very useful to me in computing routes to complete Delorme challenges and other similar challenges in the states. It is not without drawbacks but is still very helpful.

Drawbacks include the list above. As the traveling salesman is NP hard, somewhere around 100 caches, the performance becomes very slow. Optimal is not required but something close to it would be nice. Also the use of parking coordinates (or multiple parking coordinates) are not considered.

Beyond that, there have been complaints when I use it in a group that it does not consider the side of the street.

That said, with all the faults and shortcomings, it is a useful tool. But as said above, is it better to scratch everyone's itch or only some folks itch from a support point of view?