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

[Steve Coast]

On 27 Sep 2007, at 13:41, Marcus Wolschon wrote:
>>> 1)
>>> Routes are optimized for a specific metric like "shortest",
>>> "fastest", "fuel-efficient" and every metric can be parametized
>>> like "use less Autobahn", "use no maut-streets", "use no ferries",
>>
>> I think these are edge-cases but even so just multiply by 5 or 6.
>
> Please clarify what you mean here. A route from A1 to A10
> via A2-A9 would be a route from A1 to A10 via B2-B21 if
> I change the metric or the parameters of the metric.
>
> The most fuel-efficient route (that's what I am using in
> my commercial navigator every day) is often very different
> from the shortest one and the shortest usually different from
> the fastest (use motorways or the direct-path through primary
> and secondary roads).

I mean if you have more than one type of route, you're just  
multiplying the the total dataset size by the number of types.

>>> There are things like traffic-jams, temporary building-sites, ...
>>> where a road is either blocked or to be avoided.
>>
>> We don't have that data
>
> But a routing- and navigation-application has that data.
> e.g. from a TMC-receiver in every second GPS-receiver around
> here (Germany).

Sorry, I'm talking about OpenStreetMap.

>>> The map is dynamic. Every time you change a road (every minute)
>>> there are millions of routes that may change or be added.
>>
>> No, every week. And the same infrastructure that may provide  
>> updates to
>> re-render only changed areas can re-compute the route too.
>
> So: We have a database of size N where we run into load-problems just
> keeping it on a single server and you really want to precompute
> O(N^2) routes? good luck!

Thanks

> I simply cannot see a way to make this work.

I've heard that a few times before.

have fun,

SteveC | steve at asklater.com | http://www.asklater.com/steve/