Top k Optimal Sequenced Route Query with POI Preferences

Huaijie Zhu*, Wenbin Li, Wei Liu, Jian Yin, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

8 Citations (Scopus)


The optimal sequenced route (OSR) query, as a popular problem in route planning for smart cities, searches for a minimum-distance route passing through several POIs in a specific order from a starting position. In reality, POIs are usually rated, which helps users in making decisions. Existing OSR queries neglect the fact that the POIs in the same category could have different scores, which may affect users’ route choices. In this paper, we study a novel variant of OSR query, namely Rating Constrained Optimal Sequenced Route query (RCOSR), in which the rating score of each POI in the optimal sequenced route should exceed the query threshold. To efficiently process RCOSR queries, we first extend the existing TD-OSR algorithm to propose a baseline method, called MTDOSR. To tackle the shortcomings of MTDOSR, we try to design a new RCOSR algorithm, namely Optimal Subroute Expansion (OSE) Algorithm. To enhance the OSE algorithm, we propose a Reference Node Inverted Index (RNII) to accelerate the distance computation of POI pairs in OSE and quickly retrieve the POIs of each category. To make full use of the OSE and RNII, we further propose a new efficient RCOSR algorithm, called Recurrent Optimal Subroute Expansion (ROSE), which recurrently utilizes OSE to compute the current optimal route as the guiding path and update the distance of POI pairs to guide the expansion. Then, we extend our techniques to handle a variation of RCOSR query, namely RCkOSR query. The experimental results demonstrate that the proposed algorithm significantly outperforms the existing approaches.

Original languageEnglish
Pages (from-to)3-15
Number of pages13
JournalData Science and Engineering
Issue number1
Early online date3 Feb 2022
Publication statusPublished - Mar 2022

Scopus Subject Areas

  • Computational Mechanics
  • Computer Science Applications

User-Defined Keywords

  • Optimal sequenced route
  • Perference
  • Point of interest (POI)
  • Route query


Dive into the research topics of 'Top k Optimal Sequenced Route Query with POI Preferences'. Together they form a unique fingerprint.

Cite this