3,894
Views
1
CrossRef citations to date
0
Altmetric
Articles

Routing through open spaces – A performance comparison of algorithms

, , , &
Pages 247-256 | Received 04 May 2017, Accepted 03 Sep 2017, Published online: 24 Nov 2017
 

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.

Additional information

Funding

This work was supported by European Commission [grant number 612096 (CAP4Access)].