MapForums

Hi

would somebody be kind enough to point me to technical articles that explain how a vehicle nav system is able to compute routes between A and Z. basically, i want to understand the algorithms (or heuristics?) that are used.

there has to be some way to determine how much each of (say) the 4 roads leaving "A" improves (or degrades) my "current" route to Z. (and how is that initial route computed??) i assume that there is a quality assigned to each branch leaving A, in terms of whether it increases, or decreases, some "score" for the A ro Z route. and ditto at the next intersection. but this would make my choices multiply rapidly (like chess), even excluding obvious redundancies. so there has to be a pretty effective path-culling calculation, too.

now to the practicalities.

once i have left "A", if i deliberately diverge from the calculated route, my device keeps trying to force me back to (say) highway 1 at intersections C, D, E, etc.

Each of these corrections seem to be optimal in a "micro" sense - they expeditiously get me back on the calculated route - but these corrections are generally suboptimal in a macro sense - i.e., there are better ways to get to Z, *given where i am now*. in other words, it "corrects" me with the two legs of a right triangle, because it cannot "see" the existence of the hypotenuse.

eventually, as i get close to Z, or if i am nearing a choke point such as a bridge where everything converges, my device stops trying to force me onto its intended route, and appears to recompute a best path from my current point to Z.

i know that's long winded, but i hope i've expressed myself.

again, thanks to any and all help; dont hesitate to point me to dense technical or mathematical stuff; i should be able to absorb it.

Vasco

The widely-used name for this set of theorem and heuristics is known as "The Travelling Salesman Problem", and a little googling will get you literally thousands of results.

MapPoint uses four weighted sets of advanced heuristics based on "allowable" paths. The actual algorithms are propireatary in nature, as is the case with most commercial routing software.

There are a multitude of heuristic algorithms in public domain, however.
I'd suggest a starting point of:
TSPBIB Home Page

HTH
Paul

thanks for the leads.. i'll also dig up some patents to flesh out my knowledge.