Finding the shortest path through open spaces is a well-known challenge for pedestrian routing engines. A common solution is routing on the open space boundary, which causes in most cases an unnecessarily long route. A possible alternative is to create a subgraph within the open space. In a recently published paper authors from GIScience Research Group Heidelberg (Hahmann et al. 2017) assess this approach and investigate its implications for routing engines. A number of algorithms (Grid, Spider-Grid, Visibility, Delaunay, Voronoi, Skeleton) have been evaluated by four different criteria:
(i) Number of additional created graph edges,
(ii) additional graph creation time,
(iii) route computation time,
(iv) routing quality.
It is shown that each algorithm has advantages and disadvantages depending on the use case. They identify the algorithms Visibility with a reduced number of edges in the subgraph and Spider-Grid with a large grid size to be a good compromise in many scenarios.
An enhanced version of the visibility algorithm has been implemented in the Open Online Route planning system OpenRouteService.org (Schmitz et al. 2008; Neis & Zipf 2008) using OSM data. The implementation is in particular also useful for e.g. wheelchair routing (Zipf et al. 2016).
You can test the result for pedestrian routing including open areas explicitly labeled as squares in OSM at the recently introduced research platform labs.openrouteservice.org for currently all of Germany.
Hahmann, S., J. Miksch, B. Resch, J. Lauer & A. Zipf (2017): Routing through open spaces – a performance comparison of algorithms.
Geo-spatial Information Science (GSIS). Taylor & Francis. Online First. Issue and pp pending. Open Access. http://www.tandfonline.com/doi/full/10.1080/10095020.2017.1399675
- Neis, P. & Zipf, A (2008): OpenRouteService.org is three times “Open”: Combining OpenSource, OpenLS and OpenStreetMaps. GIS Research UK (GISRUK 08). Manchester.
- Schmitz, S., Neis, P. & Zipf, A. (2008): New Applications based on Collaborative Geodata – the Case of Routing. XXVIII INCA International Congress on Collaborative Mapping and SpaceTechnology, Gandhinagar, Gujarat, India.
- Zipf, A., Mobasheri, A., Rousell, A. ,Hahmann, S. (2016): Crowdsourcing for individual needs – the case of routing and navigation for mobility-impaired persons . In: Capineri, C, Haklay, M, Huang, H, Antoniou, V, Kettunen, J, Ostermann, F and Purves, R. (eds.) European Handbook of Crowdsourced Geographic Information, p. 325–337. London: Ubiquity Press. DOI: dx.doi.org/10.5334/bax.x