OSM Routing Data Layer

OSM Routing Data Layer is a concept document specifying a "data layer" specifically for routing.

This document is only within concept stage. Please contribute.

Use cases

1. Visualization of routing data
2. Tiles based generation of routing data
3. ...

Goals

Besides satisfying the additional requirement below, it should be a generic usable format for routing data.

1. Visibility
   1. Make routing relevant information derived from the collected data visible (e.g. as maps or on a navi)
   2. Visualizing routing options and problems on e.g. maps.
2. Hierarchical
   1. Routing data shall only be derived from the collected mapped data (ways, nodes and their attributes)
   2. The format shall preserve the structure and traceability to the real data it represents (streets, crossings, turn indications..)
3. Allow iterative routing data update:
   1. Iterative calculation of routing data;
      1. When a node is added, deleted or changed, only the affected routing data shall have to be updated
      2. When a way is added, deleted or changed, only the affected routing data shall have to be updated
   2. Iterative update of the routing data
4. Tile based calculation of routing data
   1. E.g. should work osmarender-like with tiles@home (needs some further study)
5. Shall be usable for:
   1. Defining routing data bases
   2. Defining routes
   3. Mapping routing information to tiles, streets and nodes.
6. Allow different routing types:
   1. Server based routing
      1. The server has the complete routing data
      2. The calculated route is transmitted to the client
      3. Optionally the ways and nodes may be retrieved from the server
   2. Client based routing
      1. The client has the complete routing data
   3. Client / server based routing (with e.g. wireless connection in between)
      1. The route is computed on a server and transmitted to a client
      2. For client-server based routing, not all routing data has to be in sync, however only the data relevant for certain route
      3. Out of sync data my be uploaded on the fly
   4. Client-Client based real-time routing:
      1. The route is computed on person A's client and sent to the client of person B
      2. The route may be continuously updated in real-time
      3. If person B does not have of all relevant nodes, ways referenced by the routing data received from person A, then person B may download exactly those missing or outdated items from OSM
7. Efficiency:
   1. The format shall be efficient on updating
   2. The format shall be efficient on transmission
   3. Might be further optimized for certain dedicated use-cases by adding additional intermediate transformation step or preferably subsequent transformation steps
   4. The format shall preserve the structure and traceability to the real data it represents (streets, crossings, turn indications..)
8. Encoding type independent:
   1. The format shall be encoding type independent.
   2. The information may be encoded in XML or in any other encoding scheme (binary, database, etc.)
   3. Subsequent encoding optimization could be used, in order to further reduce data size

Resulting requirements

1. All nodes, ways including the pre-calculated routing data needs to be identified by a version or timestamp
2. The version of nodes shall be updated, if the nodes location is changed or the nodes attributes are changed.
3. The version of the way shall be updated, if any nodes identified by their unique node ID are added or removed
4. The pre-calculated routing data shall be re-calculated, if any of the concerning nodes or ways has changed.
5. The the version of the pre-calculated routing data (e.g. section) increased, only if the result has changed from the previous calculation

Transformation steps for transforming OSM data into Routing graph data

Here the OSM Data from which in the following the the Routing graph, called OSM Routing Data Layer, is generated'.

The original OSM Data might look as following:

<way id="1" >
   <nd ref="1"/>
   <nd ref="2"/>
   <nd ref="3"/>
   <nd ref="4"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="secondary"/>
 </way>
<way id="2" >
   <nd ref="8"/>
   <nd ref="3"/>
   <nd ref="5"/>
   <nd ref="6"/>
   <tag k="highway" v="residential"/>
 </way>
<way id="3">
   <nd ref="4"/>
   <nd ref="7"/>
   <tag k="highway" v="primary"/>
 </way>
<way id="4">
   <nd ref="6"/>
   <nd ref="9"/>
   <nd ref="6"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="primary"/>
 </way>
<way id="5">
   <nd ref="10"/>
   <nd ref="4"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="primary"/>
 </way>
<way id="6">
   <nd ref="7"/>
   <nd ref="10"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="primary"/>
 </way>
<way id="7">
   <nd ref="12"/>
   <nd ref="8"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="primary"/>
 </way>
<way id="8"">
   <nd ref="11"/>
   <nd ref="12"/>
   <tag k="highway" v="primary"/>
 </way>
<node id="1" lat="51.674714" lon="8.3470936">
   ..
 </node>
...
<node id="11" lat="51.674716" lon="8.3470934"">
   ..
 </node>
...
<node id="12" lat="51.674719" lon="8.3470931">
   <tag k="highway" v="gate"/>
   <tag k="access" v="no"/>
 </node>

Please note:

1. all ways may be used by cars
2. all ways are oneway, execpt of the ways Way2, Way3 and Way8, which are bidirectional
3. node 12 is a gate with no access for cars
4. turn restrictions are not shown here. The current restriction scheme does not seem to be unambiguous. (more to follow)

Transformation step 1

Definitions:

1. A section shall be uniquely identified by its section Identifier
2. As the secton Identifier shall be globally unique without access to a global data base, the section Identifier shall be derived from the node Identifier of the sections first node and the node Identifier of the sections last node separated by a '-' character
3. A node within a way can be referenced using the reference to the ways identifier and the nodes index within that way
4. The first node of a way shall have the node index '0'
5. The second node of a way shall have the node index '1', etc.
6. A node may occur multiple times within a way. When referring to a node within a way, the nodes index shall exactly refer to the position of that node with that way.
7. A way can uniquely be referenced using its way identifier
8. A section can be identified as a sequence of way segments
9. A section is uniquely referenced using the ways way identifier, the index of the start node of that section within the way and the index of the last node of that section within the way
10. If the index of the start node is greater than the index of the end node, then the direction of the way section is in reverse direction of the referenced way
11. Start nodes are tagged with 'fromIndex'
12. End nodes are tagged with 'toIndex'

Transformation procedure:

• For each route:

1. all ways shall be split into sections:
   1. the first section shall start at the first node of the way.
   2. the last section shall end at the last node of the way.
2. the last node a section shall be the first node the following section
3. if the last node of a section is last node of the way, then no further sections shall follow
   1. a node shall be the last node of a section, when:
      1. the node is a crossing
      2. the node is tagged as as a gate
      3. the node is the last node of the way

1. the total length of a segment shall be calculated as the sum of the distance of the sections segments
2. the distance shall be calculated in km (tbd.)
3. the distance shall be stored using the the attribute 'distance'
4. the section shall reference to the original way using its way identifier
5. the start node of the section shall be referenced using its node index within the original way
6. the end node of the section shall be referenced using its node index within the original way

The structured data may look as following:

<section id="1-3" distance="3.34">
   <wayref ref="1" fromIndex="0" toIndex="2"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="secondary"/>
 </section>
<section id="3-4" distance="2.78">
   <wayref="1" fromIndex="2" toIndex="3"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="secondary"/>
 </section>
<section id="8-3" distance="10.7">
   <wayref ref="2" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="3-6" distance="101.767">
   <wayref ref="2" fromIndex="1" toIndex="3"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="4-7" length = "32.30">
   <wayref ref="3" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="6-6" length = "13.45">
   <wayref ref="4" fromIndex="0" toIndex="2"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="10-4" length = "23.3">
   <wayref ref="5" fromIndex="0" toIndex="1"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="7-10" length = "3.30">
   <wayref ref="6" fromIndex="0" toIndex="1"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="12-8" length = "2.40">
   <wayref ref="7" fromIndex="0" toIndex="1"/>
   <tag k="oneway" v="yes"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="11-12" length = "6.31">
   <wayref ref="8" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>

Transformation step 2

Transformation procedure (Example for car routing):

1. Nodes which are tagged as a gate are split into n subnodes
   1. Where n is the nunber of incoming and outgoing sections
   2. The subnodes shall become assigned a unique subnode index which uniquely identifies the subnode within the node
   3. The first subnode shall have the index '0'
   4. The subnode index shall be increased for each subnode by '1'
   5. Each subnode can be uniquely identified using its node identifier and the subnode index
2. For each route, according to the procedure defined below it shall determined whether cars are allowed to drive forwards, backwards or in both directions of that route.
3. Bidirectional routes are represented by:
   1. One section for the forward direction
   2. One section for the backward direction.
4. Unidirectional routes are represented by a section for the forward direction
5. Oneway tags become obsolete and are removed.

The structured data may look as following:

<section id="1-3" distance="3.34">
   <wayref ref="1" fromIndex="0" toIndex="2"/>
   <tag k="highway" v="secondary"/>
 </section>
<section id="3-4" distance="2.78">
   <wayref="1" fromIndex="2" toIndex="3"/>
   <tag k="highway" v="secondary"/>
 </section>
<section id="8-3" distance="10.7">
   <wayref ref="2" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="3-8" distance="10.7">
   <wayref ref="2" fromIndex="1" toIndex="0"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="3-6" distance="101.767">
   <wayref ref="2" fromIndex="1" toIndex="3"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="6-3" distance="101.767">
   <wayref ref="2" fromIndex="3" toIndex="1"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="4-7" length = "32.30">
   <wayref ref="3" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="7-4" length = "32.30">
   <wayref ref="3" fromIndex="1" toIndex="0"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="6-6" length = "13.45">
   <wayref ref="4" fromIndex="0" toIndex="2"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="10-4" length = "23.3">
   <wayref ref="5" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="7-10" length = "3.30">
   <wayref ref="6" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="12:0-8" length = "6.31">
   <wayref ref="7" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="11-12:1" length = "2.40">
   <wayref ref="8" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="12:1-11" length = "2.40">
   <wayref ref="8" fromIndex="1" toIndex="0"/>
   <tag k="highway" v="primary"/>
 </section>

Transformation step 3

Transformation procedure:

1. For each node, which is not a crossing and not a gate, however part of 2 different sections with identical routing relevant attributes (*) for the same directions (**) through that node, the sections shall be merged and the node shall be removed.
2. The distance of the merged section shall be calculated as the sum of the distance of the merged sections

(*): The routing relevant attributes are vehicle type dependent (by foot, by bike, by car, .), but also a superset applicable for all vehicle types together could be used. (**): This applies for unidirectional ways and bidirectional ways, which have been split in 2 pieces before. (In some cases step 3 might be better already applied between step 1 and step 2).

The structured data may look as following:

<section id="1-3" distance="3.34">
   <wayref ref="1" fromIndex="0" toIndex="2"/>
   <tag k="highway" v="secondary"/>
 </section>
<section id="3-4" distance="2.78">
   <wayref="1" fromIndex="2" toIndex="3"/>
   <tag k="highway" v="secondary"/>
 </section>
<section id="8-3" distance="10.7">
   <wayref ref="2" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="3-8" distance="10.7">
   <wayref ref="2" fromIndex="1" toIndex="0"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="3-6" distance="101.767">
   <wayref ref="2" fromIndex="1" toIndex="3"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="6-3" distance="101.767">
   <wayref ref="2" fromIndex="3" toIndex="1"/>
   <tag k="highway" v="residential"/>
 </section>
<section id="4-7" length = "32.30">
   <wayref ref="3" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="7-4" length = "32.30">
   <wayref ref="3" fromIndex="1" toIndex="0"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="6-6" length = "13.45">
   <wayref ref="4" fromIndex="0" toIndex="2"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="7-4" length = "26.60">
   <wayref ref="6" fromIndex="0" toIndex="1"/>
   <wayref ref="5" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="12:0-8" length = "6.31">
   <wayref ref="7" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="11-12:1" length = "2.40">
   <wayref ref="8" fromIndex="0" toIndex="1"/>
   <tag k="highway" v="primary"/>
 </section>
<section id="12:1-11" length = "2.40">
   <wayref ref="8" fromIndex="1" toIndex="0"/>
   <tag k="highway" v="primary"/>
 </section>

Note:

1. Section 7-10 and Section 10-4 have been merged, as:
   1. as they share the common node 10 and
   2. node 10 is not a crossing and
   3. both sections point into the same direction
   4. both are from type highway=primary (tbd.)

1. there are 2 alternative ways from node 7 to node 4
   1. Alternative 1 via way 3 node index 1 to node index 0 has the length 32.30 km
   2. Alternative 2 via way 6 node index 0 to node index 1 and way 5 node index 0 to node index 1 has the length 26.60 km

Alternative 2 is the shorter way.

This might be structured as following:

<section id="7-4">
   <alternative id="1" length = "32.30">
     <wayref ref="3" fromIndex="1" toIndex="0"/>
     <tag k="highway" v="primary"/>
   <alternative/>
   <alternative id="2" length = "26.60">
     <wayref ref="6" fromIndex="0" toIndex="1"/>
     <wayref ref="5" fromIndex="0" toIndex="1"/>
     <tag k="highway" v="primary"/>
   <alternative/>
 </section>

Defining routes by referencing to the ways sections

If the routing data layer is available, by referencing the sections of the routing data layer a route can be efficiently described using references to the routes section identifiers.

Here is the route description for the above shown route between node 12:0 and node 10:

<route>
   <sectionref ref="12:0-8"/>
   <sectionref ref="8-3"/>
   <sectionref ref="3-4"/>
   <sectionref ref="4-7"/>
   <sectionref ref="7-10"/>
 </route>

Note: In some cases it might additionally be required to include:

1. version identifiers or timestamps of the section references
2. information on the way to the first routing node (e.g. when starting from a non-crossing node)
3. the id of an section alternative, if there should be several alternatives sections between two nodes.

--- rest is under construction -----------

For each traffic type (car, bike, foot, horse) the following orthogonal attributes are derived from the OSM data layer.

• Permission: Defines whether that traffic type is allowed to use that route at all
  • allowed: It is allowed to use that route.
  • forbidden: It is forbidden to use that route.
  • permissive Permission is required to use that route.

• Direction: Defines in which direction that traffic type may use that route:
  • forward: It is allowed to use that route in forward direction
  • backward: It is allowed to use that route in reverse direction

• Speed limitations (tbd.)
  • Number: Speed limit according to traffic sign
  • Street type speed limit: Speed limit according to country specific street type specific speed limit

• Height limitations (tbd.)

• Width limitations (tbd.)

• Weight limitations (tbd.)

Step 3a for cars: Car permission assignment

The car_permission on a route defines whether a car may drive on a route.

The key car_permission may be assigned to the following values:

• allowed: Cars are permitted to drive on that route.
• forbidden: Cars are not permitted to drive on that route.
• permissived: Cars require a permission to drive on that route.
• ERROR: Invalid tag combination occurred.
• AMBIGUOUS: An ambiguous tag combination occurred.

Data Layer	Data Layer	Routing Data Layer
key and value of data primitive WAY	key and value of data primitive WAY	Transformed to key and value for routing layer primitive ROUTE
highway == { motorway or motorway_link or motorway_junction or trunk or trunk_link or primary_link or primary or secondary or tertiary or unclassified or unsurfaced or track or residential or living_street or service }	motorcar == { empty or yes }	car_permission = allowed
same as above	motorcar == { no }	car_permission = ERROR
same as above	motorcar == { private or permissive or unknown }	car_permission = restricted
highway == { bridleway or cycleway or footway or pedestrian or bus_guideway }	motorcar == { empty or no }	car_permission = forbidden
same as above	motorcar == { yes }	car_permission = allowed
highway == { steps }	motorcar == { empty or no }	car_permission = forbidden
same as above	motorcar == { yes }	car_permission = ERROR

Step b for cars: Car direction assignment

The car_direction tag on a route defines on while directions a car may drive on a route.

The key car_direction may be assigned to the following values:

• forward: Cars are permitted to drive in same direction as the route's vector.
• backwards: Cars are permitted to drive in the opposite direction that the route's vector.
• ERROR: Invalid tag combination occurred.
• AMBIGUOUS: An ambiguous tag combination occurred.

Data Layer	Data Layer	Data Layer	Routing Data Layer
key and value of data primitive WAY	key and value of data primitive WAY	key and value of data primitive WAY	Transformed to key and value for routing layer primitive ROUTE
highway == { motorway or motorway_link or motorway_junction or trunk_link or primary_link }	car == { empty or yes}	oneway == { empty}	car_direction = forward
same as above	car == { no }	any	car_direction = ERROR
highway == {trunk or motorway or motorway_link or motorway_junction or trunk or trunk_link or primary_link }	car == { empty or yes}	oneway == { empty}	car_direction = AMBIGUOUS
same as above	car == {empty | yes}	oneway == { yes | true | 1 | +1}	car_direction = forward
same as above	car == {empty | yes}	oneway == { no | false | -1}	car_direction = backward
same as above	car == {no}	any	car_direction = ERROR
highway == { primary or secondary or tertiary or unclassified or unsurfaced or track or residential or living_street or service }	car == { empty or yes}	oneway == { empty}	car_direction = forward, car_direction = backward
same as above	car == {empty | yes}	oneway == { yes | true | 1 | +1}	car_direction = forward
same as above	car == {empty | yes}	oneway == { no | false | -1}	car_direction = backward
same as above	car == {no}	any	car_direction = ERROR

Step 3a for bikes: Bike permission assignment

The bike_permission on a route defines whether a bike may drive on a route.

The key bike_permission may be assigned to the following values:

• allowed: Bike are permitted to drive on that route.
• forbidden: Bike are not permitted to drive on that route.
• permissived: Bikes require a permission to drive on that route.
• ERROR: Invalid tag combination occurred.
• AMBIGUOUS: An ambiguous tag combination occurred.

Data Layer	Data Layer	Routing Data Layer
key and value of data primitive WAY	key and value of data primitive WAY	Transformed to key and value for routing layer primitive ROUTE
highway == {motorway or motorway_link or motorway_junction or trunk or trunk_link or primary_link }	any	bike_permission = forbidden
highway == { primary or service or secondary or tertiary or unclassified or unsurfaced or track or residential or living_street }	bike == { empty or yes }	bike_permission = allowed
same as above	bike == { no }	bike_permission = forbidden
highway == { cycleway }	bike == { empty or yes }	bike_permission = allowed
same as above	bike == { no }	bike_permission = ERROR
highway == { bridleway or footway or pedestrian or steps }	bike == { empty or no }	bike_permission = forbidden
same as above	bike == { yes }	bike_permission = allowed

Step 3b for bikes: Bike direction assignment

The bike_direction tag on a route defines on while directions a bike may drive on a route.

The key bike_direction may be assigned to the following values:

• forward: Bikes are permitted to drive in same direction as the route's vector.
• backwards: Bikes are permitted to drive in the opposite direction that the route's vector.
• ERROR: Invalid tag combination occurred.
• AMBIGUOUS: An ambiguous tag combination occurred.

Data Layer	Data Layer	Data Layer	Routing Data Layer
key and value of data primitive WAY	key and value of data primitive WAY	key and value of data primitive WAY	Transformed to key and value for routing layer primitive ROUTE
highway == {motorway or motorway_link or motorway_junction or trunk or trunk_link or primary_link}	any	any	bike_direction = { empty }
highway == { primary or service or secondary or tertiary or unclassified or unsurfaced or track or residential or living_street }	bike == { empty or yes}	oneway == { empty}	bike_direction = forward, bike_direction = backward
same as above	same as above	oneway == { yes | true | 1 | +1}	bike_direction = forward, bike_direction = AMBIGUOUS
same as above	same as above	oneway == { no | false | -1}	bike_direction = AMBIGUOUS, bike_direction = backward
bike == { no }	bike == {no}	any	bike_direction = { empty}
highway == { cycleway }	bike == { empty or yes}	oneway == { empty}	bike_direction = forward, bike_direction = backward
same as above	same as above	oneway == { yes | true | 1 | +1}	bike_direction = forward
same as above	sama as above	oneway == { no | false | -1}	bike_direction = backward
same as above	bike == {no}	any	bike_direction = ERROR
highway == { bridleway or footway or pedestrian or steps }	bike == { empty or yes}	oneway == { empty}	bike_direction = forward, bike_direction = backward
same as above	same as above	oneway == { yes | true | 1 | +1}	bike_direction = forward
same as above	same as above	oneway == { no | false | -1}	bike_direction = backward
same as above	bike == {no}	any	bike_direction = { empty }

References

The OSM Routing Data Layer has references to the ways and the nodes of the the OSM Data Layer.

Example DTD describing the structure of the routing layer data:

(work in progress) <!ELEMENT osm_route ((route_node |route_way)*)> <!ATTLIST osm version (0.5) #REQUIRED> <!ATTLIST osm generator CDATA #REQUIRED> <!ELEMENT route_node (tag*)> <!ATTLIST route_node id_ref CDATA #REQUIRED> <!ELEMENT route_way (tag*, r_nd, tag*, nd)> <!ATTLIST route_way id_ref CDATA #REQUIRED> <!ELEMENT r_nd EMPTY> <!ATTLIST r_nd nd_ref CDATA #REQUIRED> <!ELEMENT tag EMPTY> <!ATTLIST tag k CDATA #REQUIRED> <!ATTLIST tag v CDATA #REQUIRED>

Routing data for routing

To determine the fastest route, only a certain part of road level routing data is needed. This routing data is called here 'Macro-level Routing'.

Routing data for turn directions

To provide detailed driving directions detailed routing data is needed. This routing data is called here 'Micro-level Routing'.