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

[Andrew Ross]

FWD for history on the new list 

-----Original Message-----
From: discuss-bounces at lists.osgeo.org
[mailto:discuss-bounces at lists.osgeo.org] On Behalf Of Claude Philipona
Sent: November 12, 2008 11:47 AM
To: OSGeo Discussions
Subject: Re: [OSGeo-Discuss] Discussion on Routing

I agree with the needed improvements described by Stephen.

I think the memory issue is big issue too and not well addresses right now.

On the other hand, I don't think that a routing solution should really
strongly depend on a Spatial databases. Actually, the optimization is more
a network optimization type of problem. The geographic data is in fact
important only for the presentation of the path in one specific case of
routing. So I'm really looking to have some datasource independence.

There is also more and more needs for multi-modal routing, not only by cars,
but point to point that can combine walk, bicycle, train, metro, car, ... I
think that Open Source routing could play a role on that field.

For a project sponsored by the french ministery in collaboration with a
partner, we did some investigations combining algorithms for multimodal
routing optimization. I think it is important to include these needs when we
will be thinking on the global architecture, even if the those complex
algorithms won't be the first one to be integrated. We are ready to put some
effort on this.

Claude



> I have started playing with pgRouting and find it to be an impressive 
> start. It was easy to rewrite some of the plpgsql wrappers to better 
> suit my needs. I was able to write a driving directions module the 
> explicates the direction as text and can be configured for multiple 
> languages.
> 
> There are a few limitation that I see:
> 
> 1) poor support for turn restrictions. It supports turn restrictions 
> but if you want to enter multiple restrictions at a given intersection 
> it is difficult to do and not intuitive. I have updated a couple of 
> the wiki pages to add more information. This is really needed to be 
> able to support commercial datasets like Navteq.
> 
> 2) There is no way to optimize fetching of data that is needed for a 
> potential solution other than via the postGIS spatial index which is 
> based on bounding boxes. This is very bad for route that follows 
> basically a 45 degree diagonal path. Another option would be to 
> organize data into squares of a fixed spatial size, these could be 
> loaded and cached as needed.
> 
> 3) The data for the US and Canada or all of Europe has in the ballpark 
> about 27-32 million segments. I would like to see optimization like 
> the above, and/or support for multilevel routing as an option.
> 
> 3a) There is also some very new research that has been done gives 2+ 
> orders of magnitude faster routing by doing some preprocessing of the 
> network. It might be nice to see something like this integrated.
> http://algo2.iti.uni-karlsruhe.de/english/routeplanning.php
> 
> 4) I would like to see a decoupling of the routing engine from the 
> backing stores to support it. PostGIS is nice and I'm happy to work 
> with it, but I can see a lot of situations where not using postgresql 
> could be desirable. It would be nice to have an API that would allow 
> plugable or code-able back end data stores.
> 
> 5) It would be nice to have the ability to set some standard costs 
> like it cost more to make a turn across traffic than with traffic. It 
> costs more to make a turn than to stay on a street, so the cost of the 
> turn must add value to the overall route. This helps to avoid the 
> stair-step routes in a gridded city region. The USPS has save millions 
> of dollars in fuel costs by avoiding left hand turns across traffic 
> unless it is absolutely required.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: claude_philipona.vcf
Type: text/x-vcard
Size: 301 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/routergeocoder/attachments/20081113/cb5908ad/claude_philipona.vcf
-------------- next part --------------
_______________________________________________
Discuss mailing list
Discuss at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/discuss