[Routing] speed of A* on mobile devices

[Graham Asher]

On 11/12/2012 23:39, routing-request at openstreetmap.org wrote:
> Yes. My CH implementation replaced a unidirectional A* implementation and it was a lot faster, overall, at long-distance routing. A footnote though: from a users' perspective it did not seem faster, because my A* code provided an initial "guess route" to the user within 5 seconds, so they could start driving (it didn't work correctly if the final route had to go around a large body of water, but we had no customers in that circumstance.) A CH cannot provide any directions until the route unpacking stage begins, which in my case took up to 20 seconds to reach.

I'm just not getting these problems with A* on mobile devices. My 
A*-based system (used in CartoType) will give a correct route in a 
second or two for a large city on an Android Galaxy Nexus. It takes 
account of routing restrictions and uses customisable profiles so that 
you can favour or disfavour different road types and set estimated 
speeds. I believe the key to the problem is to load the entire route 
network into memory, using a suitably parsimonious representation (and 
of course re-use it; it is loaded only once); and not to do any heap 
memory allocation during the routing process; all data manipulations are 
done in place. Another thing I found that gave a worthwhile speed-up was 
to use a carefully optimised priority queue for the list of open nodes.

I'll be releasing a demo of this system as a free Android app very soon 
so that people can see for themselves. Anyone who wants to try it right 
now on Windows can download the CartoType .NET SDK, which is free for 
non-commercial use.

Graham Asher

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20121212/44fb0d5b/attachment.html>