Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Routing through open spaces - a performance comparison of algorithms

 
: Hahmann, Stefan; Miksch, Jakob; Resch, Bernd; Lauer, Johannes; Zipf, Alexander

:
Volltext (PDF; )

Geo-spatial information science 21 (2018), Nr.3: Special Issue: Crowdsourcing for Urban Geoinformatics, S.247-256
ISSN: 1993-5153
ISSN: 1009-5020
Englisch
Zeitschriftenaufsatz, Elektronische Publikation
Fraunhofer IVI ()
OpenStreetMap

Abstract
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. This paper assesses this approach and investigates 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. We show that each algorithm has advantages and disadvantages depending on the use case. We 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.

: http://publica.fraunhofer.de/dokumente/N-477126.html