Invisible <voi### [at] devnull> wrote:
> I have no idea what kind of CPU powers this device, but what I can tell
> you is this: When I ask it to plot a route, it can seemingly analyst
> tens of thousands of roads and quickly find a suitable route. (Typically
> takes less than 10 seconds.)
>
> That doesn't *sound* very impressive... until you sit down and try to
> think of a way to program such a thing yourself. How would you do that??

These days, the algorithms usually use an approach like a human would - using a
hierarchical network. Just like you wouldn't consider every byway in all of
Eurpoe when planning a route from, say, 12 Via di Avanti, Assisi, Italy to 42
Rue de Baguette, Beauvais, France, neither does your TomTom.

Theoretically, an exhaustive brute-force approach would be necessary to find the
best route. In practice, a common-sense approach can easily eliminate something
like 99.999% of all roads.

So a typical approach would look like this:

- Find out the best ways from 12 Via di Avanti to the nearest town centers,
using any roads available; this will get you to the town center of Assisi.

- Find out the best ways from Assisi to the nearest bigger cities, ignoring
byways; this will probably get you to Perugia or Terni.

- Find out the best ways from Perugia or Terni to the nearest metropoles, using
only major roads. This will almost inevitably get you to Rome. Make a mental
note to go via Terni, because it gets you faster to Rome than via Perugia.

- Find out the best ways to 42 Rue de Baguette from the nearest town centers,
using any roads available. This will give you the town center of Beauvais.

- Find out the best ways to Beauvais from the nearest bigger cities, ignoring
byways. This will probably give you Amiens, Rouen or St-Denis.

- Find out the best ways to Amiens, Rouen or St-Denis from the nearest
metropoles, using only major roads. This will almost inevitably give you Paris.
Make a mental note to go via St-Denis, because it gets you from Paris fastest.

- Find out the best way from Rome to Paris, using only highways.

- Try out a few alternatives near Rome to check if you can come up with a faster
way. You'll find out that you can eliminate Rome altogether.

- Try out a few alternatives near Terni to check if you can come up with a
faster way. You'll find out that you can eliminate Terni, too, and go via
Perugia.

- Try out a few alternatives near the town center of Assisi. You may find out
that 12 Via Avanti is close enough to the road to Assisi that you don't have to
go via the town center either.

- Similarly, try out a few alternatives near Paris, St-Deniz and Beauvais - only
to find out that you can't optimize much there because the french road systm is
too centered on Paris to come up with any reasonable alternatives ;)

(Actually, TomTom will most likely not operate on town centers, major cities and
metropoles, but rather more generic "traffic nodes" of different hierarchies;
however, the basic concept is the same.)

The common sense behind this approach is that byways and even major roads won't
get you from Italiy to France in any acceptable time.


This approach often may *not* give you the optimal route. However, given that it
will only very rarely be significantly worse than the optimal one, it is
definitely good enough.

Post a reply to this message