[Routing] How to Establish Road Hierarchy

[Ben Abelshausen]

I'm just a beginner here trying to follow this discussion. I also did a
(pretty naive) implementation of CH.

I guess even when A* would be ok 'in the could' or on a mobile device isn't
it always better to use a more efficient algorithm considering battery
life, the environment and the hosting costs of any routing solution?
Computational power isn't free, even if users would be willing to pay for a
solution like this someone else implements it smarter and better and you
would have to keep up.

I use CH's for logistical optimization, it's very fast on many-to-many
calculations, another use case where dykstra or it's variant A* is way too
slow for any practical usage except maybe small areas with only a few
customers.

Regards,

Ben

On Wed, Dec 12, 2012 at 1:12 PM, Dennis Luxen <dennis.luxen at gmail.com>wrote:

> 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.
>>
>
> Not necessarily true. There may be distinct path with equivalent weight.
> It will return a path of equal length but not necessarily the same one.
>
> Speaking of guarantees, I was thinking of search space sizes. A* is not
> able to give any assertion that it is indeed faster than Dijkstras
> seminal algorithm or uses less RAM.
>
>
>  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.
>>
>
> We are mixing up terms here. Hierarchy can mean a number of distinct
> things. Most people speak of hierarchy when they simple prune the
> search, i.e. take only motorways at a certain point in the search.
>
>
>  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.
>>
>
> If and only if the data fits into RAM. And thats going to deliver a
> rather crappy user experience when a user has to quit other apps just to
> have enough RAM.
>
>
>  (B) Furthermore, most devices are now Internet enabled and long
>> routes can be calculated in the cloud using A*.
>>
>
> A place where you certainly don't want 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.
>>
>
> 'Fairly quickly' is a debatable term, here. Even for naive routing
> algorithms, this is a lot of computation.
>
>
>  If a normal driver calculates all his routes with A*, the
>> computational cost will be less than one hundredth of a cent per
>> kilometre.
>>
>
> That's some strange metric and awfully expensive for an online service
> thats mildly popular.
>
>
>  Insignificant compared to the cost of fuel, man hours,
>> mobile bandwidth etc.
>>
>
> Well, 30 seconds is certainly significant when compared to a latency of
> hundred milliseconds or so on the cell network.
>
>
> ______________________________**_________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.**org/listinfo/routing<http://lists.openstreetmap.org/listinfo/routing>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20121212/38d92dd6/attachment.html>