Hi jamiew,
The basic strategy is to target the general vicinity of the starting
and destination points, and then try and refine the time by using
faster roads. Some map software/websites provide an option between
"most direct route" and "fastest route", with only the latter
considering the speed limits of the roads involved.
The routes are weighted based on actual or approximated speed limits /
distance to travel. ((M/H) / M) = H
Each exit to exit or street to street (any possible change from one
road to another) is then taken as a edge in what is known as a
weighted graph, i.e. there is a "cost" of 4 minutes associated with
travelling from exit 33 to exit 34, and there is a similar cost of
travelling down a parallel side road over approximately the same
distance of 15 minutes.
The actual algorithm for selection is proprietary in all cases, but is
almost certainly a variant in all mapping software of Dijkstra's
algorithm, the fastest way of solving weighted-graph problems with
non-negative edges. (i.e. since all the distances and thus time-costs
are positive from point-to-point, Dijkstra's algorithm is the fastest
known way to solve this problem.)
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
The basic idea in this algorithm is to start with a source point and
calculate the times to all directly connected points, and then again
to all points directly connected to those points, and so on, and if a
shorter path is found replace the old path with the new one, until we
have the cost of travel to each point in the grid. Total distances are
based on the path taken, and if a distance to a node is made shorter,
all nodes that use it in their paths have their distance shortened
too.
So virtually every possible route to each point is checked, and you
end up with a list of shortest paths to each node from your starting
point, and the distances to each.
I think it much easier to see this algorithm in action than to
understand it in words. There are some links to interactive
explanations at the end of the Wikipedia entry:
http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html
http://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm
http://www.itonsite.co.uk/allanboydproject/section4_2.htm
You should note, however, that they are focused on routing problems
(which is actually exactly the same issue, except distance-times there
are considered in milliseconds, and there are usually far less edges
to consider in the graph).
The proprietary parts that we can safely assume are added by most
mapping sites would likely factor in some biases to ignore or focus on
certain types of roads for different-sized trips in order to speed up
this computation, and also to be able to get from many individual
points to the city and town points undoubtedly stored in their
databases, also to minimize computational costs. So, for example if I
were to check the route for a suburb of Philidelphia to a suburb of
New York, only a few roads would be considered near the ends of the
NYC-Philidelphia path as possibilities for minimizing the route, since
the bulk of the trip can be considered to be approximately the same.
Traffic may also be taken into consideration in some new and
experimental systems to otherwise adjust the "cost" per unit of travel
along the road.
http://en.wikipedia.org/wiki/Route_assignment
Hope this is what you were looking for.
Thanks for your interesting question, and thanks for choosing Google! Answers!
- bookface-ga |
