Continuously Monitoring Alternative Shortest Paths on Road Networks

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

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review


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.

TitelProceedings of the VLDB Endowment
RedaktørerMagdalena Balazinska, Xiaofang Zhou
Antal sider13
ForlagAssociation for Computing Machinery
Publikationsdato1 jul. 2020
StatusUdgivet - 1 jul. 2020
NavnProceedings of the VLDB Endowment

Citer dette