[pgrouting-dev] Fwd: Old discussion on turn restrictions

[Stephen Woodbridge]

Jay,

Here is another thread that discusses turn restrictions.

-Steve

-------- Original Message --------
Subject: [RouterGeocoder] Re: [OSGeo-Discuss] Discussion on Routing
Date: Tue, 18 Nov 2008 15:44:44 -0500
From: Stephen Woodbridge <woodbri at swoodbridge.com>
To: Anton Patrushev <anton.patrushev at gmail.com>, 
routergeocoder at lists.osgeo.org

Anton Patrushev wrote:
> 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.

Hi Anton,

Did you get subscribed to the new list?

I have been thinking about this a lot. While I have a gap in my
knowledge about how this information needs to be accessed and used
inside the routing engine, I do have some ideas on how we might want to
describe it.

1) Granted everyone does not have access to Navteq data, but using a
schema similar to Navteq's or something that can be generated easily
from Navteq's description would be good.

Why should we care about what Navteq does?
a) It is a well thought out model that is used by a very large number of
companies the license Navteq data for vehicle navigation and companies
the license it for routing applications.
b) As a result, it is mature and probably has already solved 99% of the
problems that we might not think about initially but users, especially
Navteq users, will run into in the future.
c) I am not advocating that we violate any copyrights or what not, but
if we were to translate Navteq data into our format, what type of data
and fields would we need to account for.
d) I think this generally can be extended to include an appropriate
analysis of TeleAtlas also so we can support routing using either of
these data sets.
e) We may want to take a phased approach to implementing these features
in the routing engine, but having a robust description of the routing
data model will probably be helpful.

2) I think that the above information can be represented as tables that
can be linked to either NODEs or EDGEs in the model. Assume that every
NODE and EDGE has a UID, then these tables could be linked via the UID
and maybe addition info if needed.

3) For a NODE based model like Dijkstra, a turn restriction can easily
be represented as a list of NODE_IDs

    +--2--7--...
6--5--4--3--...
    +--4--9...


TURN_RESTRICTION
------------------
NODE_ID | ANCESTRY
    5    | 4,3
    5    | 2

In this example, I am evaluating NODE_ID=5, and if my parent node is 2,
then I am not allow to proceed to node 5 and it is pruned. Likewise, if
my parent is 4 and grandparent is 3, then I would be retricted and prune
the tree, but if my parent is 4 and my grandparent is 9, then I would be
allowed to proceed.

I think you already implement something similar using edges with
shootingstar model in pgRouting. This same model could be applied to
edges. If I understand the Boost terminology, we would implement a
visitor on the edge or the node that would check the appropriate table
for restrictions.

Some more thoughts, on street network versus routing graph. While the
street network is geometry based and the router only needs a graph to
solve, we still need to maintain a link between the graph edges and the
street segments and nodes so we can extract the route geometry, driving
directions, etc. after the routing is complete. Also, there is a close
correlation between euclidean space of nodes and connectedness of nodes.
As such, we can optimize data storage, by clustering nodes that are
physically close into a physical page storage system, so that when you
fetch a data page for any given node there is a high probability that
most of all of the nodes connected to it are also located on the same
page. With an efficient page management system for data storage and a
little caching, we can avoid a HUGE amount of IO.

Thoughts?

-Steve

> Anton.

[snip]
_______________________________________________
Routergeocoder mailing list
Routergeocoder at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/routergeocoder