Bao, Jinling; Wang, Bin; Liu, Gang; Yang, Xiaochun Popularity-optimal path search based on time constraint. (Chinese. English summary) Zbl 1363.90204 J. Northeast. Univ., Nat. Sci. 37, No. 5, 629-633 (2016). Summary: 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, by which one can make a choice on any node (visit or pass by) according to the tradeoff between permitted time and popularity score of attractions, and select 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. MSC: 90C27 Combinatorial optimization 90C35 Programming involving graphs or networks 90C59 Approximation methods and heuristics in mathematical programming Keywords:location-based services; trip planning; time constraint; optimal path search; road network PDFBibTeX XMLCite \textit{J. Bao} et al., J. Northeast. Univ., Nat. Sci. 37, No. 5, 629--633 (2016; Zbl 1363.90204) Full Text: DOI