Article Preview
Top1. 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.