关键词: 道路网络, 条最优路线, 兴趣点, 关键词搜索, 个性化旅游路线

Abstract: Tourists visit an unfamiliar city with the intention of exploring multiple attractions and sampling local cuisine before eventually heading to their hotel for rest. Due to these requirements, tourists seek multiple routes that are short in distance, cover all desired locations, and are popular among consumers. Such route queries that support keyword searches for the top-k optimal routes are known as top-k optimal route queries with keyword support. This query involves providing a road network, a set of points of interest on the network, and a route query containing a starting point and multiple keywords. The objective of the query is to find k optimal routes that pass through multiple points of interest matching the query's keywords, where the score considers both the route distance and the popularity of the points of interest along the route. However, some existing research on this problem reduces the complexity of the algorithm by assuming that the user-input keywords determine the order of visiting the points of interest. This approach is not suitable for scenarios where there are no specific requirements on the order of visiting the points, thus failing to meet the user's true intent and reducing practicality. Other approaches aim to improve query efficiency by setting distance thresholds to prune points of interest that do not meet the requirements. However, such algorithms cannot guarantee that the pruned points of interest will not be part of the optimal routes. In response to the issues with the above-mentioned algorithm, this paper proposes a keyword-aware top-k optimal route query algorithm. The algorithm first divides the entire road network into multiple subnetworks and employs a heuristic search strategy, starting from the subgraph containing the query's starting point and gradually expanding the search scope until it finds the top-k optimal routes or explores the entire road network. During the expansion process, the algorithm introduces a subgraph pruning strategy to eliminate subgraphs that do not contain the top-k optimal routes, thereby reducing the search scope. Additionally, to avoid computing every possible set of points of interest that could form the optimal routes, the algorithm designs a points of interest sequence pruning strategy to quickly filter out sequences that are unlikely to form the optimal routes, thus reducing computation costs. Through the proposed algorithm, tourists can more easily plan their travel routes and obtain more optimal choices that suit their preferences. Furthermore, extensive experiments on real and synthetic datasets have been conducted to demonstrate the effectiveness of the proposed algorithm compared to baseline methods.

Key words: road network, top-k optimal routes, POI, keywords search, personalized travel route