[OSGeo-Discuss] Discussion on Routing

[Anton Patrushev]

Hi Steve,

Good points, thank you!

However some of them are up to data and application.
PgRouting is full of "hysterical raisins" and too much bounded with
PostgreSQL - there is almost no border between pgRouting as library
and wrapper functions which is application side already.

I'm still thinking on good turn restriction data model.
And that's one more topic to think about - how to make routing library
not only data source independent, but also convenient to use with
different data sources?
In other words - we need to think about the data structure (how to
store turn restrictions, cost, reverse cost etc) in a way which suits
to different data sources.

Anton.


On Wed, Nov 12, 2008 at 3:19 AM, Stephen Woodbridge
<woodbri at swoodbridge.com> wrote:
> (Orkney)Toru Mori wrote:
>
> [snip]
>
>> p.s. Anybody want to talk about routing?
>
> [changing subject line was: RE: [OSGeo-Discuss] Anyone interested in
> geocoding and routing?]
>
> 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.
> _______________________________________________
> Discuss mailing list
> Discuss at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/discuss
>