[Routing] answers to questions about A* on mobile devices

[Graham Asher]

On 12/12/2012 10:57, routing-request at openstreetmap.org wrote:
>> I'm just not getting these problems with A* on mobile devices.
> Tiny data set?
No - map files of up to 1Gb (e.g., whole of NW Canada) with hundreds of 
thousands of roads.
>
>> >  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.
> Define large.
Stockholm is another good example. London is fine too. And a moment ago 
I loaded a map of Ireland in and calculated a route from Dublin to 
Limerick in a couple of seconds. The map of Ireland (derived, of course, 
from OSM data, is about 45Mb in size in CTM1 format.
>
>> >  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
> Yes, that's the problem. You just can't load everything into RAM on a
> handheld-device beyond small'ish road networks of a couple thousand edge
> segments.
Well actually you can. Perhaps a Galaxy Nexus with 1Mb of RAM is an 
unfair example - I don't know - but there are plenty of mobile devices 
with similar amounts of memory. One internet commentator says "In a 
world where you can't find an Android device out there with less than 
1GB of RAM..."
>
>> >  not to do any heap memory allocation during the routing process; all
>> >  data manipulations are done in place.
> This implies that during routing you will always use linear memory, i.e.
> the size of your priority queue depends on the number of nodes.
Which is correct. All the nodes are in memory, and each node has space 
for the links and other information needed by the priority queue.
>> >  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
>> >
>> >
>> >