Efficient Cache-Supported Path Planning on Roads

Ying Zhang, Yu Ling Hsueh, Wang Chien Lee, Yi Hao Jhang

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


Owing to the wide availability of the global positioning system (GPS) and digital mapping of roads, road network navigation services have become a basic application on many mobile devices. Path planning, a fundamental function of road network navigation services, finds a route between the specified start location and destination. The efficiency of this path planning function is critical for mobile users on roads due to various dynamic scenarios, such as a sudden change in driving direction, unexpected traffic conditions, lost or unstable GPS signals, and so on. In these scenarios, the path planning service needs to be delivered in a timely fashion. In this paper, we propose a system, namely, Path Planning by Caching (PPC), to answer a new path planning query in real time by efficiently caching and reusing historical queried-paths. Unlike the conventional cache-based path planning systems, where a queried-path in cache is used only when it matches perfectly with the new query, PPC leverages the partially matched queries to answer part(s) of the new query. As a result, the server only needs to compute the unmatched path segments, thus significantly reducing the overall system workload. Comprehensive experimentation on a real road network database shows that our system outperforms the state-of-the-art path planning techniques by reducing 32 percent of the computation latency on average.

Original languageEnglish (US)
Article number7352325
Pages (from-to)951-964
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number4
StatePublished - Apr 1 2016

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Efficient Cache-Supported Path Planning on Roads'. Together they form a unique fingerprint.

Cite this