[OSGeo-Discuss] Discussion on Routing

[Claude Philipona]

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: 314 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/discuss/attachments/20081112/b0dd63df/attachment.vcf>