Fast a on road networks using a scalable separator-based heuristic

Renjie Chen, Craig Gotsman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Fastest-path queries between two points in a very large road map is an increasingly important primitive in modern transportation and navigation systems, thus very efficient computation of these paths is critical for system performance and throughput. We present a novel method to compute an effective admissible heuristic for the fastest-path travel time between two points on a road map, which can be used to significantly accelerate the classical A∗ algorithm when computing fastest paths. Our basic method-called the Hierarchical Separator Heuristic (HSH)-is based on a hierarchical set of linear separators of the map represented by a binary tree, where all the separators are parallel lines in a specific direction. A preprocessing step computes a short vector of values per road junction based on the separator tree, which is then stored with the map and used to efficiently compute the heuristic at the online query stage. We demonstrate experimentally that this method scales well to any map size, providing a high-quality heuristic, thus very efficient A∗ search, for fastest-path queries between points at all distances-especially small and medium range. We show how to significantly improve the basic HSH method by combining separator hierarchies in multiple directions and by partitioning the linear separators. Experimental results on real-world road maps show that HSH achieves accuracy above 95% in estimating the true travel time between two junctions at the price of storing approximately 25 values per junction.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2020
EditorsAnne Berres, Kuldeep Kurte
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450381666
DOIs
StatePublished - Nov 3 2020
Event13th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2020 - Seattle, Virtual, United States
Duration: Nov 3 2020 → …

Publication series

NameProceedings of the 13th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2020

Conference

Conference13th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2020
CountryUnited States
CitySeattle, Virtual
Period11/3/20 → …

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems
  • Control and Systems Engineering
  • Geography, Planning and Development
  • Transportation

Keywords

  • fastest-path
  • heuristic
  • road map
  • search

Fingerprint Dive into the research topics of 'Fast a on road networks using a scalable separator-based heuristic'. Together they form a unique fingerprint.

Cite this