TripRec: An Efficient Approach for Trip Planning with Time Constraints

TripRec: An Efficient Approach for Trip Planning with Time Constraints

Heli Sun (School of Electronic and Information Engineering, Xi'an Jiaotong Univeristy, Xi'an, China & State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing China, China), Jianbin Huang (State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China & School of Software, Xidian University, Xi'an, China), Xinwei She (School of Software, Xidian University, Xi'an, China), Zhou Yang (School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an, China), Jiao Liu (School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an, China), Jianhua Zou (School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an, China), Qinbao Song (School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an, China) and Dong Wang (School of Information Science and Technology, Northwest University, Xi'an, China)
Copyright: © 2015 |Pages: 21
DOI: 10.4018/ijdwm.2015010103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The problem of trip planning with time constraints aims to find the optimal routes satisfying the maximum time requirement and possessing the highest attraction score. In this paper, a more efficient algorithm TripRec is proposed to solve this problem. Based on the principle of the Aprior algorithm for mining frequent item sets, our method constructs candidate attraction sets containing k attractions by using the join rule on valid sets consisting of k-1 attractions. After all the valid routes from the valid k-1 attraction sets have been obtained, all of the candidate routes for the candidate k-sets can be acquired through a route extension approach. This method exhibits manifest improvement of the efficiency in the valid routes generation process. Then, by determining whether there exists at least one valid route, the paper prunes some candidate attraction sets to gain all the valid sets. The process will continue until no more valid attraction sets can be obtained. In addition, several optimization strategies are employed to greatly enhance the performance of the algorithm. Experimental results on both real-world and synthetic data sets show that our algorithm has the better pruning rate and efficiency compared with the state-of-the-art method.
Article Preview

1. Introduction

The wide application of wireless telecommunication and smart hand-held devices among the public enable us to gather a large amount of trajectories of moving objects (Goh & Taniar, 2004; Kisilevich et al., 2010; Lu et al., 2010; Taniar & Goh, 2007; Waluyo et al., 2005; Xuan et al., 2011; Zheng et al., 2009). Several methods have been proposed to mine hot tourist attractions from quantities of trajectories of the users (Horozov et al., 2006; Huang & Bian, 2009; Yu & Chang, 2009). However, trip planning based on the already-known tourist attractions is still a challenging task, due to its high computational complexity. This problem possesses considerable theoretical significance and practical value that can be applicable to many different scenarios such as personalized trip plan for a tourist, energy-efficient route suggestion for taxi drivers.

Recently, Lu et al. (2011) have proposed a problem of trip planning with time constraints. Taking into account the scores of tourism value of all the attractions, stay time of every attraction and travel time between them, the problem aims to find an optimal route within the time constraint that has the highest attraction score. A simple solution is the brute force approach. However, the brute force method entails the enumeration of all possible itineraries, which takes a considerable computational cost. To achieve better performance, Lu et al. proposed a novel data mining-based approach, namely Trip-Mine, to efficiently find the optimal trip satisfying the travel time constraint specified by the user. Based on the Aprior algorithm (Agrawal & Srikant, 1994) for mining frequent item sets, TripMine generates and prunes the candidate attraction sets. After that, from all itinerary permutations spawned by the candidate attraction sets, it obtains the optimal route within a time constraint. To further reduce computational cost, three optimization mechanisms are introduced (Lu et al., 2011). However, the performance of TripMine deteriorates drastically as the number of attractions or the value of time threshold increases, which makes it not feasible for trip planning with more attractions or a longer time upper bound.

When generating candidate routes from an attraction set, TripMine lists all the permutations of the attractions in the set. The candidate routes generation process ceases once a valid route is found or all possible combinations have been enumerated and no valid route has been found. Therefore, many invalid itineraries can be formed, which impedes the pruning process and thus incurs higher computational cost. To overcome the above weakness, we present a novel and more efficient trip planning approach named TripRec which is built on the join rule of Aprior algorithm as well. In contrast to the original listing all permutations approach taken by TripMine, our algorithm features the creation of routes of length k+1 from all valid routes of length k through an route extension method. Some identified optimization strategies are utilized to further boost the performance of our method. Experimental results on real-world and synthetic data sets prove that our method surpasses TripMine when there are more attractions and a longer time constraint for a trip.

The remainder of the paper is organized as follows: Section 2 outlines related work. The formulation of the problem of trip planning with time constraint is highlighted in section 3. The TripRec algorithm is described in detail in section 4. Section 5 deals with the computer simulation results and performance comparison with previous methods. Finally, section 6 conclusions the paper.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing