Article Preview
Top1. Introduction
Efficient and personalized trip planning becomes increasingly important with fast increased pace of life. Ideally, personalized trip planning can help tourists to visit as many favorite scenes as possible, with minimal time and effort. In reality, it is difficult for efficient and personalized trip planning. Most tourists will simply follow others’ trajectories by word of mouth, commercial brochures, travel blogs, or touring books, thus it is difficult to figure out scenes of interests and best routes that connect the scenes before-hand. For example, a tourist plans to travel on a holiday, but does not have a specific destination in mind. In order to plan an efficient and pleasant trip, she scans the touring routes on the Web or seeks advices from travel agents. She then chooses a popular travel trajectory suggested by others, with little consideration of her own interests. Such planning can easily lead to following problems: i) waste of time on scenes not interested; ii) missed scenes of interest; iii) extra time due to random stopping at scenes and connection between scenes; and iv) unnecessary increased cost. For a satisfactory trip planning, the following features are desired: i) automated suggestion of scenes or attractions; ii) personalized based on a tourist’s interest and habits; iii) maximal coverage of sites of interest; and iv) minimal effort such as transporting time on the route.
To achieve these goals, in this paper, we present our work on a novel spatio-temporal sequence (STS) searching system OrientSTS to support optimal personalized trip planning. OrientSTS provides a knowledge base of scenes with their tagged features, and season characteristics represented by probabilistic combination of tags. Such information is provided through collective knowledge from social network websites. By combining personal profiles and scene features, OrientSTS generates a set of weighed scenes for each city for each user. OrientSTS can then retrieve the optimal sequence of scenes in terms of distance, weight, visiting time, and scene features. The goal is to provide the traveler with a STS that passes through as many chosen favorite scenes as possible with maximal weight and minimal distance within available travel time. As a result, a traveler can make efficient and personalized trip planning based on her own profile before she starts to travel.
To demonstrate our approach, we show a trip planning scenario in Figure 1. When a traveler arrives at a city, the system automatically presents scenes with weights according to scene features and a user’s profile. Here six scenes of interests with large weights are chosen: scenes (o1;o2;o3;o4;o5;o6) with weights (w1;w2;w3;w4;w5;w6) respectively. Given these six selected scenes, the database that stores the features of scenes will provide an efficient search of an optimal STS, i.e., the red sequence in Figure 1. Mean-while, there is another sequence created by following others’ general trajectory, shown as the blue sequence. The time cost of touring includes both the stopping time at each scene and the transitional time between scenes, as demonstrated in the rectangles on the timelines (Popescu, 2009). The difference of visiting orders of the scenes leads to much different overall time: under six hours for the red sequence and over nine hours for the blue sequence.
In this paper, we take the STS problem as a graph oriented problem where touring scenes are nodes and paths between these scenes are edges. To the best of our knowledge, no prior work considers both point weight and edge distance, which are inversely proportional.
Figure 1. Two different sequences (red, blue) include six chosen scenes with different weights and timelines. Scenes of each sequence which have been visited are presented in the order of visit. On the timelines, transitions between tourist scenes are depicted by rectangles and visiting time is in minutes.