[OSGeo-Discuss] Discussion on Routing

[Stephen Woodbridge]

(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.