[Routing] [OSM-dev] pre-compute routing

[Frederik Ramm]

Hi,

> Almost every route is going to be something like "take street a,b,c,
> get on a motorway, come off and do streets d,e,f". That is, almost
> every route is going to be fairly simple.

I think there's still a certain appeal to pre-routing at least for  
mainstream routes - usually any city will have only a handful of  
"exits" that you will definitely pass through on any journey longer  
than 100km. Identify these, then pre-package routes from (a) any  
point in the city to these exits and (b) nationwide from each exit of  
every city to each exit of every other city. This gives you a very  
reduced graph on which to do your final routing.

I used to think that this is how one *must* do it because everything  
is too slow otherwise. Then I saw gosmore and was surprised how fast  
routing can be done even on 1,000km distances and without any extra  
hints and precomputing. Of course it is one thing to have gosmore  
running on your private CPU, and another having a CPU shared through  
a web service with hundreds of parallel users.

Pre-routing can also be made to blend nicely with custom routing.You  
could have one graph with the full OSM network, and merge that with a  
number of pre-calculated "edges" (e.g. one that connects Marble Arch,  
London to Buchanan Bus Station, Glasgow and carries with it a length  
in kilometres and fixed routing info). These extra edges will be  
picked up automatically by the routing algorithm.

Sure, pre-routing cannot take traffic jams or roadblocks into account  
(but still a pre-routing generated route could be checked against a  
list of roadblocks and if it clashes, it could be rebuilt dynamically).

The biggest challenge to any pre-routing scheme is probably the  
required re-calculation once the network changes. For each change  
being made to the OSM database, we would have to somehow find out  
which pre-calculated routes need to be invalidated due to this, and  
re-do those.

Bye
Frederik

-- 
Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00.09' E008°23.33'