Journal of Northeastern University Natural Science ›› 2016, Vol. 37 ›› Issue (5): 629-633.DOI: 10.12068/j.issn.1005-3026.2016.05.005

• Information & Control • Previous Articles     Next Articles

Popularity-Optimal Path Search Based on Time Constraint

BAO Jin-ling1, WANG Bin1, LIU Gang2, YANG Xiao-chun1   

  1. 1. School of Computer Science & Engineering, Northeastern University, Shenyang 110819, China; 2. School of Computer Science, Baicheng Normal College, Baicheng 137000, China.
  • Received:2015-04-01 Revised:2015-04-01 Online:2016-05-15 Published:2016-05-13
  • Contact: WANG Bin
  • About author:-
  • Supported by:
    -

Abstract: When the permitted time is not enough to visit all attractions in any path, the path satisfying the constraints could not be found by the existing search methods. An approximation algorithm PSScaling to solve this problem was presented, making a choice on any node (visit or pass by) according to the tradeoff between permitted time and popularity score of attractions, and selecting the best combination of attractions to access in the same path. The experimental results on real data sets reveal that the proposed algorithm is able to find the approximate optimal path efficiently.

Key words: location-based services, trip planning, time constrained, optimal path search, road network

CLC Number: