Home > Papers

 
 
An Efficient Trip Planning Algorithm Under Constraints
Jinling Bao 1 #,Xiaochun Yang 2 *,Bin Wang 2
1.College of Information Science and Engineering, Northeast University, Shenyang 110819
2.College of Information Science and Engineering, Northeast University, Shenyang, 110819
*Correspondence author
#Submitted by
Subject:
Funding: The National Natural science Foundation of China（No.Nos. 61173031, 61272178）, Specialized Research Fund for the Doctoral Program of Higher Education （No.No. 20110042110028）, the Joint Research Fund for Overseas Natural Science of China （No.No. 61129002）
Opened online:15 August 2013
Accepted by: none
Citation: Jinling Bao,Xiaochun Yang,Bin Wang.An Efficient Trip Planning Algorithm Under Constraints[OL]. [15 August 2013] http://en.paper.edu.cn/en_releasepaper/content/4554413
 
 
The problem of trip planning has received wide concerns in recent years. More and more people require the service of automatically confirming the optimal tour route. When users assign the source and the destination, and the time limit of the tour, how can automatically decide the optimal tour route with the highest sum of the popularity scores of scenic spots. Current methods for trip planning are on the setting that providing with the route which is composed of the scenic spots to travel. These would work poorly for the pre-mentioned problem when the route satisfying the constraints can not be found. Thus we adjust the setting to giving the route composed of the scenic spots which users visit or simply pass by. Obviously, the modified problem would incur larger search cost as each scenic spot in the given route has two states. It can be demonstrated that this new problem is NP hard, making it difficult to find an efficient exact algorithm for the present. In this paper, we propose a greedy strategy based algorithm to solve the trip planning problem, and we also present an improved algorithm with better performance. The experimental results on synthesized and real data sets reveal that our algorithm is able to find the approximately optimal path in high efficiency.
Keywords:Constraints; Path Searching; Trip Planning; Benefit Score; Cost Score
 
 
 

For this paper
  • ● PDF (0B)
  • ● Revision 0 　　
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags
Add yours

Related Papers

Statistics
PDF Downloaded 286
Bookmarked 0
Recommend 5
Comments Array
Submit your papers