[RouterGeocoder] Re: [OSGeo-Discuss] Discussion on Routing

[Stephen Woodbridge]

Anton Patrushev wrote:
> Hi Steve,
> 
> Let me clarify some things.
> There is no conflict here - we all want to have the same things to be done.
> But Daniel is talking about a library while you are talking about an
> application.

Yes, I can see that and it makes sense for it to have a wide 
applicability. And I hope to be one of the early adopters of it :)

> Yes, we have Boost Graph Library and (surprise! surprise!) pgRouting uses it.
> Our goal is not to reinvent the wheel, but to create a tool everybody
> can use. For example, I was quite surprised when last year at FOSS4G
> 2007 I met a guy who was trying to use pgRouting to simulate forest
> fires. Amazing! Who knows, probably somebody is dying without having
> river network navigation tool. Or who knows what else.

Yup makes perfect sense to me. I was just hoping to get a better 
understanding of the other applications that might want to utilize the 
library.

> What about shortest paths calculated in 2 seconds for 30 million edges
> - it is possible right now! No kidding! Just buy Cray and precalculate
> all possible paths between all possible node pairs :)
> But to say seriously, it is application side.

I think numbers like this are achievable. For example, pgRouting already 
extracts a subset of all the node/segments to solve only in a bounding 
box subset. This is one good trick. Another might be organizing the data 
into pages based on spatial locality. Oracle Spatial solves routes in 
North America (27M segments) on average in few 100 ms, but it is not 
doing a Dijkstra solution on the whole thing. A route from Key West, FL 
to Anchorage, AK takes a little longer, but is still in the 1-2 sec 
range IIRC. They use a local search from the start and end points to the 
nearest major road then route on the major road network using an A* 
search, but they also have options to avoid highways.

> Of course it doesn't mean that we don't need to think about
> application side. No! It is important.
> But I think we should start with a core (having some possible
> applications in mind).

Agreed. So please take my rants as a mixture of application needs, and 
ideas for the implementation of some features both core and applications 
levels. I try to organize the ideas but sometimes there are too many of 
them and it is all a jumble. I could be wrong, but I think 80-98+% of 
your users will be doing navigation applications.

> By the way, I found your ticket (pretty old) at the pgRouting Trac
> about the way how to store turn restriction rules (with rules divided
> by semicolon). It makes a lot of sense! Thanks, man! I will use it for
> sure.

Oh great! yeah, I forgot that I wrote that.

Best regards,
   -Steve

> 
> Anton.
> _______________________________________________
> Routergeocoder mailing list
> Routergeocoder at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/routergeocoder