[Routing] How to Establish Road Hierarchy

[David Piepgrass]

> > To avoid such problems, the contraction hierarchy or highway hierarchy
> techniques (derived from Dijkstra rather than A*) can be used. These are
> challenging to implement correctly and efficiently, but do not depend on
> road attributes that are consistently accurate, and a GPL implementation of
> the contraction algorithm is available.
> >
> > http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
> 
> It is _A_GPL. A much simpler, but improved implementation is the basis of
> OSRM [1]. Note that neither implementation is suitable for handheld/mobile
> devices.

Oh, is it AGPL? I see that's a little more restrictive than GPL. But I was referring to the contraction algorithm, which you would run on a server or workstation anyway; with the contracted network prepared, then you just need to some code to convert it to a suitably compact representation for mobile devices--although this can be challenging in itself--and additional code to actually do the routing, tuned for mobile devices.

And I wonder if a CH routing algorithm designed for the desktop might actually be suitable for higher-end (1GHz+) smartphones and tablets. When I was writing for the 400MHz device, the processor was 10-30 times slower than a single thread on my desktop PC, but that wasn't even the biggest bottleneck; the biggest bottleneck was the flash memory, which was below 500 KB/sec IIRC when doing random access to 2 KB blocks. I guess some devices may be 10x faster than that nowadays.

I would be interested to hear how OSRM can be both simpler and improved at the same time.