[Routing] How to Establish Road Hierarchy

[Dennis Luxen]

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

See here for results on a mobile implementation.

http://algo2.iti.kit.edu/1264.php

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

Simpler on more than one level. For one, the code is much more usable. Second, the heuristics used to order nodes are much simpler and data structures have nicer interfaces. Then the Monav/OSRM implementation exploits multiple cores. And so on ;-)

--Dennis