But be aware! It is not always the fastest route. The software is
optimizing up to a certain level. I found this out when I planned a
1500km trip and wanted to include a point to visit that was not on
the found route. The result was an amazing faster route. The longer
your route is the more this might happen.
Thibaud Chabot
At 12:20 21-07-2008, Chris Lusby Taylor wrote:
Hi Doug,
The task of finding the shortest/quickest route from A to Z along a network
of roads is not the same as the Travelling Salesman Problem, nor its
generalisation the Vehicle Routing Problem, unless you also say you want to
go via C, D, E etc in no particular order but without visiting any of them
twice.
Your GPS is usually solving the very much simpler problem of merely finding
the shortest/quickest route from A to Z.
To do this, all it needs to do is to find the distance to all the crossroads
you can reach directly from A, then the minimum distance to all the
crossroads you can reach from them, and so on until you find yourself at Z
by one route and all other routes that haven't yet reached Z are already
longer.
By the way I'm sure it does use vectors, not bitmaps, to draw the route, and
a table of the properties of all road segments.
This may still be a substantial task, and there are ways to direct the
search to improve the chances that the first route you try will be the best.
For instance, you can use a 'meet in the middle' approach - fan out from
both A and Z until you find paths that meet.
Either way, it can then use a critical-path type analysis to see which
is/are the shortest route(s). For instance, if C is 20 miles from A, D is 25
miles from A but the road CD is 6 miles long, it cannot be on the shortest
route.
However, I do have a GPS that can tell me how to get from A to Z via B and
C, where B and C are visited in any order to minimise the total journey.
That is the Travelling Salesman Problem, near enough.
Best wishes
Chris
----- Original Message -----
From: "Gordon Uber" <[EMAIL PROTECTED]>
To: "Douglas Bateman" <[EMAIL PROTECTED]>; "Sundial List"
<sundial@uni-koeln.de>
Sent: Monday, July 21, 2008 12:45 AM
Subject: Re: Knowing where we are
> Hi Doug,
>
> Look up "vehicle routing problem" and the following:
>
> http://www.sintef.no/static/am/opti/projects/top/vrp/
>
> Here is a list of research papers available on line:
> http://www.sintef.no/static/am/opti/projects/top/vrp/bibliography.html
>
> Your assumption is basically correct. The solution must be searched
> for. In general, given a table of nodes/intersections and the
> distances between them, one can search all paths for the shortest
> path. Since this usually takes too long, one takes shortcuts
> (heuristics or guesses), sometimes not even attempting the best solution.
>
> (I was looking at this in about 1963 for finding the shortest length
> of wire to interconnect a set of electrical terminals. I have not
> kept up in the field.)
>
> Gordon
>
>
> At 01:34 PM 7/20/2008, Douglas Bateman wrote:
> >Sundiallists always know where they are, but do they know where they
> >are going?
> >
> >This rather rhetorical question is slightly off topic and directed to
> >our computer experts: the question is how does my satellite
> >navigation (Sat Nav) system in my car, or hand held, know where it is
> >going and how to get there when I give it an address?
> >
> >A search in Wikipedia or Google under satellite navigation talks about
> >the satellites, timing, position, etc, but NOT what is in my little box.
> >
> >I assume that the memory holds some form of map (vector storage, or
> >bit map?) and a series of nodes for every single road intersection
> >(and plans thereof). A route finding algorithm must exist for testing
> >all the nodes between and A and B. I also assume each link between
> >any two nodes must obey some rules about speed limits, preferences for
> >motorways, etc.
> >
> >Then, I assume that the incoming signal for latitude and longitude
> >must cause the map to 'place itself' under this lat long so that you
> >can see a real time display of where you are and where you are going.
> >
> >It would be nice to know more! Any advice please.
> >
> >Regards, Doug (who sometimes still get lost)
> >---------------------------------------------------
> >https://lists.uni-koeln.de/mailman/listinfo/sundial
>
> ---------------------------------------------------
> https://lists.uni-koeln.de/mailman/listinfo/sundial
>
---------------------------------------------------
https://lists.uni-koeln.de/mailman/listinfo/sundial
----------
Th. Taudin Chabot, . [EMAIL PROTECTED]
---------------------------------------------------
https://lists.uni-koeln.de/mailman/listinfo/sundial
