On Sat, 2009-05-23 at 04:10 +0200, Marcus Wolschon wrote: > Frederik Ramm schrieb: > > just played with Google routing from one side of London to the > > other, and found it tends to display the fastest (often M25) route > > first, but then offer a number of "alternatives", seemingly named after > > the road that makes up the largest portion. So in addition to the > > initial M25 route, you immediately get "M4 (xyz minutes)" and others. I > > wonder how it is done, algorithmically. It must be more than just the > > shortest and the fastest route. Does it perhaps store which routes > > people print after playing aroung with via points, and use that, or > > something? > > >From what I could find they seem to > employ a database of fastest sub-routes > to break down routing to their usual > mapreduce-algorithm. > Can`t find the paper right now. > You could do such a thing yourself > using e.g. apache hadoop but it only > makes sense if LOTS of routes are > to be calculated.
It could also be Schultes' Highway Hierarchies algorithm. According to his theory, you can precompute a small number of access points for a map. The fastest route between two points sufficiently far away from each other will use those access points. http://algo2.iti.uka.de/schultes/hwy/ Danny -- Danny Backx ; danny.backx - at - scarlet.be ; http://danny.backx.info _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
