[Routing] How to Establish Road Hierarchy

[Dennis Luxen]

> 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.