Client-side route planning: preprocessing the OpenStreetMap road network for Routable Tiles

Harm Delva1, Julián Andrés Rojas Meléndez1, Ben Abelshausen2, Pieter Colpaert1 and Ruben Verborgh1

1 IDLab, Ghent University – imec
2 Open Knowledge Belgium

If most route planners preprocess the same data

Does it make sense to share the results?

  • Linked Data
    •
  • Preprocessing Routable Tiles
  • Using the Preprocessed Data

Linked Geospatial Data

We think that the concept of Linked Data is fundamental to the publishing of spatial data on the Web: it is the links that connect data together that are the foundational to the Web of data.

W3C and OGC, Spatial Data on the Web Best Practices

Linked Data Fragments

Verborgh, R., Vander Sande, M., Hartig, O., Van Herwegen, J., De Vocht, L., De Meester, B., ... & Colpaert, P. (2016). Triple Pattern Fragments: a low-cost knowledge graph interface for the Web. Journal of Web Semantics, 37, 184-206.

OpenStreetMap as Linked Data Fragments

Share the load

Can we do serverless route planning?

Slow but sure

We need to reduce the data requirements
See also: The ethics of performance

  • Linked Data
  • Preprocessing Routable Tiles
    •
  • Using the Preprocessed Data

Moving the load

Pedestrian Areas

We are not the first

Source: Configuring OpenTripPlanner

Transit Tiles

Only retain data that's needed to traverse a tile

Increased effect on higher levels

576 km²

Zoom level 11 $\rightarrow$ Zoom level 10

6.1 MB uncompressed $\rightarrow$ 3.7 MB uncompressed

Contracting unimportant nodes

576 km²

Zoom level 10

3.7 MB uncompressed $\rightarrow$ 2.0 MB uncompressed

  • Linked Data
  • Preprocessing Routable Tiles
  • Using the Preprocessed Data
    •

Urbanization determines effectiveness

Impact on Query Times

Brussels Airport - Bruges
100 km through relatively dense urban areas

Query Time Data Downloaded
Raw Data 3,393 s 214,672 kB
Preprocessed Data 20 s 9,116 kB

Routing data Ecosystem

What's stopping us?

Cost?
Trust?

Conclusion

Serverless route planning seems feasible

We should share more data

hdelva.be/slides/sotm2019/
github.com/hdelva/preprocess_routable_tiles