Continuously monitoring alternative shortest paths on road networks

Lingxiao Li, Muhammad Aamir Cheema, Mohammed Eunus Ali, Hua Lu, David Taniar

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

Abstract

Modern navigation systems do not only provide shortest paths but also some alternative paths to provide more options to the users. This paper is the first to study the problem of continuously reporting alternative paths for a user traveling along a given path. Specifically, given a path P on which a user is traveling, we continuously report to the user k paths from the user's current location on P to the target t. We present several algorithms each improving on the previous based on non-trivial observations and novel optimisations. The proposed algorithms maintain and exploit the previously computed useful information to efficiently update the k alternative paths as the user moves. We provide space and time complexity analysis for each proposed algorithm. We conduct a comprehensive experimental study on large real-world road networks. The results demonstrate that the proposed algorithms are up to several orders of magnitude faster than the straightforward algorithms.

Original languageEnglish
Pages (from-to)2243-2255
Number of pages13
JournalProceedings of the VLDB Endowment
Volume13
Issue number11
DOIs
Publication statusPublished - 2020
EventInternational Conference on Very Large Databases 2020 - Tokyo, Japan
Duration: 31 Aug 20204 Sep 2020
Conference number: 46th
https://dl.acm.org/journal/pvldb (Proceedings)
https://vldb2020.org (Website)

Cite this