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

Stephen Woodbridge woodbri at swoodbridge.com
Tue Nov 18 15:44:44 EST 2008


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]


More information about the Routergeocoder mailing list