Routing through open spaces-A performance comparison of algorithms  

作　　者：Stefan Hahmann Jakob Miksch Bernd Resch Johannes Lauer Alexander Zipf 

机构地区：[1]GIScience Research Group,Institute of Geography,Heidelberg University,Heidelberg,Germany [2]Fraunhofer IVI,Fraunhofer Institute for Transportation and Infrastructure Systems,Dresden,Germany [3]Department of Geoinformatics-Z_GIS,University of Salzburg,Austria [4]Center for Geographic Analysis,Harvard University,Cambridge,MA,USA [5]HERE GmbH&Co KG,Schwalbach am Taunus,Germany

出　　处：《Geo-Spatial Information Science》2018年第3期247-256,共10页地球空间信息科学学报（英文）

基　　金：supported by European Commission[grant number 612096(CAP4Access)].

摘　　要：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.

关 键 词：OpenStreetMap ROUTING open space NAVIGATION PEDESTRIAN POLYGON 

分 类 号：O15[理学—数学]