[Routing] How to Establish Road Hierarchy

[Nic Roets]

On Wed, Dec 12, 2012 at 10:44 AM, Dennis Luxen <dennis.luxen at gmail.com>wrote:

>
> Avoiding traffic jams is a much more delicate topic, because the naive
> method of adding a penalty and recomputing a new path usually fails. Also,
> you want to have some guarantee on alternative path quality and also on
> runtime. A* does not guarantee anything.
>
>
A* guarantees that the route is optimal for the given metric of cost. I
assume that CH gives the same guarantee for the same metric and will
therefore give exactly the same route.

Furthermore, as computers get cheaper and devices get faster, the
> difference in speed between A* and CH is becoming insignificant.
>
>
> Plain wrong. A* does not scale.
>

I'm talking about real life routing:
(A) In 2007 a mobile device typically had only 64MB RAM and a 300MHz
processor. So, if you didn't have a routing hierarchy, it would take a
minute or two to compute the average route a commuter would take. But now
you have many phones and tablets with 1GB RAM and a 1GHz processor, so A*
can buffer all the static data in RAM and only takes a few seconds.
(B) Furthermore, most devices are now Internet enabled and long routes can
be calculated in the cloud using A*. I have demonstrated on many occasions
that the longest routes in OpenStreetMap can be calculated fairly quickly
on reasonable hardware e.g. only 30 seconds on a Xeon processor with 16 GB
RAM. If a normal driver calculates all his routes with A*, the
computational cost will be less than one hundredth of a cent per kilometre.
Insignificant compared to the cost of fuel, man hours, mobile bandwidth etc.




>
> All these tradeoffs are firmly in favour of A* for most applications.
>
>
> Also wrong. Especially in applications you want to have small search
> spaces and also compute many (sub-)paths.
>

>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>
>


-- 
Regards,
Nic
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20121212/a2a49254/attachment.html>