[Routing] generalized routing format

[flo Detig]

Hi

I agree too
it would be nice to have a common format for routing
(or at least the compilers to generate that derived data)

Staying somewhat close to commercial formats seems reasonable too.
Having a higher-level routing-graph of 'elementary arcs' while still 
remaining the ability
to 'paint' or describe the exact route (with all the degree-2-node 
nuances) sounds interesting.
Do you mean something like this?   'WAY' -> has_many 'ARCS' -> has_many 
'NODES' ?
For routing just nodes that offer a choice to go ahead (like junctions) 
are relevant

Greetings from munich,
flo detig


ps: some random thoughts:
What about even more layers?
In case of greedy (dijkstra-/a*-style) BFS you could start 'searching'
until the first higher-layer-node appears, for instance a 
residential-junction.
After that stay on that layer and only examine 'arcs' to other junctions
until you reach the first 'secondary-layer-junction', after which you 
can ignore
junctions to residential (lower-level) streets and move on in bigger steps.
Once you arrive at the motorway-level you search on that layer / graph
that solely consists of arcs between 'motorway-junctions' (german 
Autobahnkreuz)..
(could be implemented by adding an integer for layer to the nodes table
and computing shortest paths between neighbouring nodes in each layer
resulting in a edges-/arcs-/pgrouting-table with source-target-cost)
But how get 'down' again to find the final destination node?

Please excuse if this sounds stupid. I'm just loud thinking..
Probably this is this too complicated.
Any opinions?




Tristram Gräbener wrote:
> Hi
>
> I agree that it would be nice to have some general format for routing.
>
> Wouldn't it be nice to have a format somewhat close to the formats
> available for commercial databases (like Navteq or Teleatlas) ?
>
> I have (limited) experience with Navteq:
> The arcs are traditionnal (source, target) but also have a "geometry"
> property allowing to represent graphically the link (a string of many
> points). The limitation is that the properties are "hard coded" and
> makes extension more difficult.
>
> I am working (but you know... never enough time :'( ) on a parser to
> postgis (massively based on osm2pgrouting). From that database it will
> be possible to export it to quite many different common formats (using
> ogr2ogr). This would allow to use the data as a drop-in in many GIS
> that weren't designed for osm data (osm2postgis works quite well, but
> doesn't split the ways in elementary arcs, thus is quite useless for
> routing). PGrouting only requires a table with source, target, cost,
> [rcost] so, nothing very complicated.
>
> I have the feeling that there are two approaches generaly used :
> * splitting ways into elementary arsc
> * merging nodes of degree 2
> I don't know if one approach is better than another... If you have any
> opinion on that question I'm interested.
>
>
> Greetings from Toulouse
>
> On Thu, Oct 9, 2008 at 4:26 PM, Frederik Ramm <frederik at remote.org> wrote:
>   
>> Hi,
>>
>> flo wrote:
>>     
>>> Are there any approaches to 'normalizing' or 'layering'?  (like freeway-
>>> / primary- / secondary Graphs)?
>>>       
>> Every routing software/project does their own preprocessing. Navit has
>> its own compiler, gosmore has a built-in compiler for creating an
>> indexed tree file, openrouteservice uses unreleased code to create their
>> routing graph inside a database.
>>
>> At one time I thought about making general preprocessed routing graphs
>> available on the Geofabrik web site in regular intervals but I then
>> decided not to as every routing software has its own style anyway, doing
>> different things in the preprocessing step.
>>
>> (If, however, members of this list come up with some generalized format
>> for an OSM routing graph plus the algorithm that creates it, then I'd be
>> happy to look into providing such a routing graph available to all on a
>> regular basis. Does pgrouting have something like a recommended general
>> graph structure that would be suitable an usable to many?)
>>
>> Bye
>> Frederik
>>
>>
>>
>> _______________________________________________
>> Routing mailing list
>> Routing at openstreetmap.org
>> http://lists.openstreetmap.org/listinfo/routing
>>
>>     
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>
>