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

[Tim Thornton]

Hi

On 9/27/07, Marcus Wolschon <marcus at wolschon.biz> wrote:
>
>
> You cannot do precomputed routing for 3 simple reasons:


Well, you can, but I understand what you're saying. It might work as a cache
for the common case though, so I wouldn't dismiss it.

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",
> ... .
>
> 2)
> There are things like traffic-jams, temporary building-sites, ...
> where a road is either blocked or to be avoided.
>
> 3)
> The map is dynamic. Every time you change a road (every minute)
> there are millions of routes that may change or be added.


I would be really interested to see if we can build a picture of actual
average road speed for a given time/day from the data collected so far. I'm
not sure that we could at the moment, given the emphasis is on building a
complete map rather than collecting "redundant" points. Nonetheless, could
make routing ETAs very good. Thoughts?

Tim

Steve Coast schrieb:
> > (please reply to the new routing list, sent to dev so that you know
> > it's there)
> >
> > We have about 4 million ways.
> >
> > The total disk space to store all routes is therefore
> >
> > ~= 4 * 10e6 * (L * B) * N
> >
> > I'm going to go out on a limb here, and almost any route I've got
> > directions for is about 10 steps. Some will be more of course, but
> > many will be much less.
> >
> > ~= 4 * 10e6 * (10 * 2) * 3 ~= 240 million bytes.
> >
> > This, I'm told, is exactly what Google do. But their dataset is a bit
> > bigger.
>
> Google is a very bad routing-application.
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFG+53Mf1hPnk3Z0cQRAjsMAKCHmvfWpsHzFER24r9MMEKuxdbeFgCguvqo
> OZmASGhkijauPQ3BdAUSt/k=
> =jPOZ
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20070927/220c903c/attachment.html>