Journal of East China Normal University(Natural Sc ›› 2019, Vol. 2019 ›› Issue (5): 100-112.doi: 10.3969/j.issn.1000-5641.2019.05.008

• Computational Intelligence in Emergent Applications • Previous Articles     Next Articles

Optimal route search based on user preferences

JIANG Qun1, DAI Ge-nan1, ZHANG Sen1, GE You-ming1, LIU Yu-bao1,2   

  1. 1. School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China;
    2. Guangdong Key Laboratory of Big Data Analysis and Processing, Sun Yat-Sen University, Guangzhou 510006, China
  • Received:2019-07-29 Online:2019-09-25 Published:2019-10-11

Abstract: This paper studies the methodology for optimal route search based on user preferences, such as keyword and weight preferences, under a constraint. The research problem is NP-hard. To solve the query efficiently, we propose two new index building methods and select candidate nodes for retrieving the established indices. This paper subsequently proposes an A* based route search algorithm to identify the optimal route and use several effective pruning strategies to speed up execution. Experimental results on two real-world check-in datasets demonstrates the effectiveness of the proposed method. When the budget ranges from 4 hours to 7 hours, our algorithm performs better than the state-of-the-art PACER algorithm.

Key words: route search, users' preferences, A* algorithm

CLC Number: