Diversified Top-k Route Planning in Road Network

Zihan Luo, Lei Li, Mengxuan Zhang, Wen Hua, Yehong Xu, Xiaofang Zhou

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

12 Citations (Scopus)


Route planning is ubiquitous and has a profound impact on our daily life. However, the existing path algorithms tend to produce similar paths between similar OD (Origin-Destination) pairs because they optimize query results without considering their influence on the whole network, which further introduces congestions. Therefore, we investigate the problem of diversifying the top-k paths between an OD pair such that their similarities are under a threshold while their total length is minimal. However, the current solutions all depend on the expensive graph traversal which is too slow to apply in practice. Therefore, we first propose an edge deviation and concatenation-based method to avoid the expensive graph search in path enumeration. After that, we dive into the path relations and propose a path similarity computation method with constant complexity, and propose a pruning technique to improve efficiency. Finally, we provide the completeness and efficiency-oriented solutions to further accelerate the query answering. Evaluations on the real-life road networks demonstrate the effectiveness and efficiency of our algorithm over the state-of-the-art.

Original languageEnglish
Title of host publicationPVLDB 2022 - Proceedings of the 48th International Conference on Very Large Databases
PublisherVLDB Endowment
Number of pages14
Publication statusPublished - 1 Jul 2022
Externally publishedYes
Event48th International Conference on Very Large Data Bases, VLDB 2022 - Sydney, Australia
Duration: 5 Sept 20229 Sept 2022

Publication series

NameProceedings of the VLDB Endowment
PublisherVery Large Data Base Endowment Inc.
ISSN (Print)2150-8097


Conference48th International Conference on Very Large Data Bases, VLDB 2022

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Diversified Top-k Route Planning in Road Network'. Together they form a unique fingerprint.

Cite this