Personalized Tour Recommendation Based on User Interests and Points of Interest Visit Durations

1 Introduction

Tour recommendation and itinerary planning are challenging tasks due to the different interest preferences and trip constraints (e.g., time limits, start and end points) of each unique tourist 1 . While there is an abundance of information from the Internet and travel guides, many of these resources simply recommend individual Points of Interest (POI) that are deemed to be popular, but otherwise do not appeal to the interest preferences of users or adhere to their trip constraints. Furthermore, the massive volume of information makes it a challenge for tourists to narrow down to a potential set of POIs to visit in an unfamiliar city. Even after the tourist finds a suitable set of POIs to visit, it will take considerable time and effort for the tourist to plan the appropriate duration of visit at each POI and the order in which to visit the POIs.

1 We use the terms "tourist" and "user" interchangeably.

To address these issues, we propose the PERSTOUR algorithm for recommending personalized tours where the suggested POIs are optimized to the users' interest preferences and POI popularity. We formulate our tour recommendation problem based on the Orienteering problem [Tsiligirides, 1984], which considers a user's trip constraints such as time limitations and the need for the tour to start and end at specific POIs (e.g., POIs near the tourist's hotel). Using geo-tagged photos as a proxy for tourist visits, we are able to extract real-life user travel histories, which can then be used to automatically determine a user's interest level in various POI categories (e.g., parks, beaches, shopping) as well as the popularity of individual POIs. As tourists have different preference levels between POI popularity and POI relevance to their interests, our PERSTOUR algorithm also allows tourists to indicate their preferred level of trade-off between POI popularity and his/her interest preferences.

Our main contributions are as follows:

• We propose the PERSTOUR algorithm for recommending personalized tours with POIs and visit duration based on POI popularity, users' interest preferences and

• trip constraints. Our tour recommendation problem is modelled in the context of the Orienteering problem (Section 3).
• We introduce the concept of time-based user interest, where a user's level of interest in a POI category is based on his/her time spent at such POIs, relative to the average user. We also compare our time-based user interest to the current practice of using frequency-based user interest, and show how time-based user interest results in recommended tours that more accurately reflect real-life travel sequences (Section 3.1).
• We demonstrate the personalization of POI visit duration using time-based user interest. Our results show that personalized visit durations more accurately reflect the real-life POI visit durations of users, compared to the current practice of using average visit duration (Section 3.1).
• We implement a framework (Fig. 1) for extracting reallife user travel histories, which are then used for training our PERSTOUR algorithm and serve as ground truth for our subsequent evaluation (Section 4).
• We evaluate different variants of PERSTOUR against various baselines using a Flickr dataset spanning four cities. Our results show that PERSTOUR out-performs these baselines based on tour popularity, user interest, recall, precision and F1-score (Sections 5 and 6).

For the rest of the paper: Section 2 discusses related work in tour recommendation, and Section 7 concludes our paper.

2 RelatedWork

Tour recommendation has been a well-studied field, with many developed applications [Vansteenwegen and Oudheusden, 2007; Castillo et al., 2008; Brilhante et al., 2014] and research ranging from recommending beautiful, quiet, and happy tours [Quercia et al., 2014] to tour recommendation using randomwalks with restart [Lucchese et al., 2012]. In this section, we focus on research related to our work, and refer readers to [Souffriau and Vansteenwegen, 2010] and [Damianos Gavalas, 2014] for an overview on the general field of tour recommendation.

[Choudhury et al., 2010] was one of the earlier tour recommendation studies based on the Orienteering problem, where recommended tours start and end at specific POIs while trying to maximize an objective score. Using a modified Orienteering problem, [Gionis et al., 2014] utilized POI categories such that recommended tours are constrained by a POI category visit order (e.g., museum→ park → beach). Similarly, [Lim, 2015] used a modified Orienteering problem constrained by a mandatory POI category, which corresponds to the POI category a user is most interested in. Based on user-indicated interests and trip constraints (e.g., time budget, start and end locations), [Vansteenwegen et al., 2011a] recommended tours comprising POI categories that best match user interests while adhering to these trip constraints.

In contrast, [Brilhante et al., 2013] formulated tour recommendation as a Generalized Maximum Coverage problem [Cohen and Katzir, 2008], with the objective of finding an optimal set of POIs based on both POI popularity and user interest. Thereafter, [Brilhante et al., 2015] extended upon the former by using a variation of the Travelling Salesman Problem, with the main aim of finding the shortest route among the set of optimal POIs recommended in [Brilhante et al., 2013]. In addition to user interests in tour recommendation, [Chen et al., 2014] also considered travelling times based on different traffic conditions, using trajectory patterns derived from taxi GPS traces. With further considerations for different transport modes, [Kurashima et al., 2010; 2013] used a combined topic and Markov model to recommend tours based on both user interests and frequently travelled routes.

While these earlier works are the state-of-the-art in tour recommendation research, our proposed work differs from these earlier works in two main aspects: (i) instead of using frequency-based user interest (by POI visit frequency) or requiring users to explicitly indicate their interest preferences, we derive a relative measure of time-based user interest using a user's visit durations at POIs of a specific category, relative to the average visit durations of other users; (ii) we recommend a personalized POI visit duration to individual users based on their time-based user interests, instead of using the average POI visit duration for all users or not considering visit duration at all.

3 Background and ProblemDefinition

3.1 Preliminaries

If there are m POIs for a particular city, let P = {p1, ..., pm} be the set of POIs in that city. Each POI p is also labelled with a category Catp (e.g., church, park, beach) and latitude/longitude coordinates. We denote a function Pop(p) that indicates the popularity of a POI p, based on the number of times POI p has been visited. Similarly, the function T Travel (px, py) measures the time needed to travel from POI px to py, based on the distance between POIs px and py and the indicated travelling speed. For simplicity, we use a travelling speed of 4km/hour (i.e., a leisure walking speed). 2

Definition 1: Travel History. Given a user u who has visited n POIs, we define his/her travel history as an ordered sequence, Su = ((p1, tap1 , tdp1 ), ..., (pn, tapn , tdpn )), with each triplet (px, tapx , tdpx ) comprising the visited POI px, and the arrival time tapx and departure time tdpx at POI px. Thus, the visit duration at POI px can be determined by the difference between tapx and tdpx . Similarly, for a travel sequence Su, tap1 and tdpn also indicates the start and end time of the itinerary respectively. For brevity, we simplify Su = ((p1, tap1 , tdp1 ), ..., (pn, tapn , tdpn )) as Su = (p1, ..., pn).

Definition 2: Travel Sequence. Based on the travel history Su of a user u, we can further divide this travel history into multiple travel sequences (i.e., sub-sequences of Su). We divide a travel history Su into separate travel sequences if tdpx -tapx+1 > τ . That is, we separate a travel history into distinct travel sequences if the consecutive POI visits occur more than τ time units apart. Similar to other works [Choudhury et al., 2010; Lim, 2015], we choose τ = 8 hours in our experiments. These travel sequences also serve as the ground truth of real-life user trajectories, which are subsequently used for evaluating our PERSTOUR algorithm and baselines.

2T Travel (px, py) can be easily generalized to different transport modes (e.g., taxi, bus, train) and also consider the traffic condition between POIs (e.g., longer travel times between two POIs in a congested city, compared to two equal-distanced POIs elsewhere).

Definition 3: Average POI Visit Duration. Given a set of travel histories for all users U, we determine the average visit duration for a POI p as follows:

where n is the number of visits to POI p by all users and δ(px=p) = {1, px=p 0, otherwise . ¯ V (p) is commonly used in tour recommendation as the POI visit duration for all users [Brilhante et al., 2013; 2015; Chen et al., 2014], while many earlier works do not factor in POI visit durations at all. In our work, we show how recommended POI visit durations can be personalized to individual users based on their interest (Definition 5), and use ¯ V (p) as a comparison baseline (i.e., the non-personalized POI visit duration).

Definition 4: Time-based User Interest. As described earlier, the category of a POI p is denoted Catp. Given that C represents the set of all POI categories, we determine the interest of a user u in POI category c as follows:

where δ(Catpx =c) = {1, Catpx =c 0, otherwise . In short, Eqn. 2 determines the interest of a user u in a particular POI category c, based on his/her time spent at each POI of category c, relative to the average visit duration (of all users) at the same POI. The rationale is that a user is likely to spend more time at a POI that he/she is interested in. Thus, by calculating how much more (or less) time a user is spending at POIs of a certain category compared to the average user, we can determine the interest level of this user in POIs of this category.

Definition 5: Personalized POI Visit Duration. Based on our definition of time-based user interest (Eqn. 2), we are able to personalize the recommended visit duration at each POI based on each user's interest level. We determine the personalized visit duration at a POI p for a user u as follows:

That is, we are recommending a personalized POI visit duration based on user u's relative interest level in category Catp multiplied by the average time spent at POI p. Thus, if a user is more (less) interested in category Catp, he/she will spend more (less) time at POI p than the average user.

Definition 6: Frequency-based User Interest. We also define a simplified version of user interest, denoted IntF req u (c), which is based on the number of times a user visits POIs of a certain category c (i.e., the more times a user visits POIs of a specific category, the more interested this user is in that category). As using IntFreq u (c) is the current practice in tour recommendation research [Brilhante et al., 2013; Lim, 2015; Brilhante et al., 2015], we include it for a more complete study and as a comparison baseline to our proposed IntT ime u (c).

3.2 ProblemDefinition

We now define our tour recommendation problem in the context of the Orienteering problem and its integer problem formulation [Tsiligirides, 1984; Vansteenwegen et al., 2011b; Lim, 2015]. Given the set of POIs P, a budget B, starting POI p1 and destination POI pN, our goal is to recommend an itinerary I = (p1, ..., pN) that maximizes a certain score S while adhering to the budget B. In this case, the score S is represented by the popularity and user interest of the recommended POIs using the functions Pop(p) and Int(Catp), respectively. The budget B is calculated using the function Cost(px, py) = T Travel (px, py) + T V isit u (py), i.e., using both travelling time and personalized visit duration at the POI. One main difference between our work and earlier work is that we personalize the visit duration at each recommended POI based on user interest (Definition 5), instead of using the average visit duration for all users or not considering visit duration at all. Formally, we want to find an itinerary I = (p1, ..., pN) that:

where xi,j = 1 if both POI i and j are visited in sequence (i.e., we travel directly from POI i to j), and xi,j = 0 otherwise. We attempt to solve for Eqn. 4, such that:

Eqn. 4 is a multi-objective function that maximizes the popularity and interest of all visited POIs in the itinerary, where η is the weighting given to the popularity and interest components. Eqn. 4 is also subject to constraints 5 to 9. Constraint 5 ensures that the itinerary starts at POI 1 and ends at POI N, while constraint 6 ensures that the itinerary is connected and no POIs are visited more than once. Constraint 7 ensures that the time taken for the itinerary is within the budget B, based on the function Cost(px, py) that considers both travelling time and personalized POI visit duration. Given that px is the position of POI x in itinerary I, constraints 8 and 9 ensure that there are no sub-tours in the proposed solution, adapted from the sub-tour elimination used in the Travelling Salesman Problem [Miller et al., 1960].

Based on this problem definition, we can then proceed to solve our tour recommendation problem as an integer programming problem. For solving this integer programming problem, we used the lpsolve linear programming package [Berkelaar et al., 2004]. We denote our proposed algorithm for personalized tour recommendation as PERSTOUR, and shall describe our overall framework and the different PERSTOUR variants in the following section.

4 Tour Recommendation Framework

Fig. 1 outlines our overall tour recommendation framework. This framework requires a list of POIs (with lat/long coordinates and POI categories) and a set of geo-tagged photos (with lat/long coordinates and time taken), which can be easily obtained fromWikipedia and Flickr, respectively. Thereafter, the main steps in our framework are:

Step 1: Determine POI visits (Map photos to POIs). We first determine the POI visits in each city by mapping the set of geo-tagged photos to the list of POIs. In particular, we map a photo to a POI if their coordinates differ by <200m based on the Haversine formula [Sinnott, 1984], which is used for calculating spherical (earth) distances.

Step 2: Construct Travel History/Sequences. Based on the POI visits from Step 1, we can construct the travel history of each user by sorting their POI visits in ascending temporal-order (Definition 1). Using each user's travel history, we then proceed to group consecutive POI visits as an individual travel sequence, if the consecutive POI visits differ by <8 hours (Definition 2). Thus, we are also able to determine the POI visit duration based on the time difference of the first and last photo taken at each POI.

Step 3: Recommend Tours using PERSTOUR. As described in Section 3.2, there can be different variants of PERSTOUR, based on the value of η and the type of interest function chosen. The value of η indicates the weight given to either POI popularity or user interest, while the interest function can be either time-based interest (IntT ime u ) or frequencybased interest (IntFreq u ). We experiment with the following variants:

• PERSTOUR using η=0 (PT-0). PERSTOUR with full emphasis on POI popularity, ignoring user interest (i.e., no need to choose between IntT ime u or IntFreq u ).
• PERSTOUR using IntTime u and η=0.5 (PT-.5T). PERSTOUR with balanced emphasis on optimizing both POI popularity and time-based user interest.
• PERSTOUR using IntFreq u and η=0.5 (PT-.5F). PERSTOUR with balanced emphasis on optimizing both POI popularity and frequency-based user interest.
• PERSTOUR using IntTime u and η=1 (PT-1T). PERSTOUR with full emphasis on optimizing time-based user interest, ignoring POI popularity.
• PERSTOUR using IntFreq u and η=1 (PT-1F). PERSTOUR with full emphasis on optimizing frequencybased user interest, ignoring POI popularity.

These variants allow us to best evaluate the effects of different η values, and compare between time-based interest and frequency-based interest. As PT-0 does not consider user interest, there is no need to choose between time-based or frequency-based user interest.

5 Experimental Methodology

5.1 Dataset

For our experiments, we use the Yahoo! Flickr Creative Commons 100M (YFCC100M) dataset [Thomee et al., 2015], which consists of 100M Flickr photos and videos. This dataset also comprises the meta information regarding the photos, such as the date/time taken, geo-location coordinates and accuracy of these geo-location coordinates. The geolocation accuracy range from world level (least accurate) to street level (most accurate).

Using the YFCC100M dataset, we extracted geo-tagged photos that were taken in four different cities, namely: Toronto, Osaka, Glasgow and Edinburgh. To ensure the best accuracy and generalizability of our results, we only chose photos with the highest geo-location accuracy and experimented on four touristic cities around the world. A more detailed description of our dataset is shown in Table 1.

5.2 Baseline Algorithms

Similar to our PERSTOUR approach, these baseline algorithms commence from a starting POI p1 and iteratively choose a next POI to visit until either: (i) the budget B is exhausted; or (ii) the destination POI pN is reached. The sequence of selected POIs thus forms the recommended itinerary, and the three baselines are:

• Greedy Nearest (GNEAR). Chooses the next POI to visit by randomly selecting from the three nearest, unvisited POIs.
• Greedy Most Popular (GPOP). Chooses the next POI to visit by randomly selecting from the three most popular, unvisited POIs.
• Random Selection (RAND). Chooses the next POI to visit by randomly selecting from all unvisited POIs.

GNEAR and GPOP are meant to reflect tourists behavior by visiting nearby and popular POIs respectively, while RAND shows the performance of a random-based approach.

5.3 Evaluation

We evaluate PERSTOUR and the baselines using leave-oneout cross-validation [Kohavi, 1995] (i.e., when evaluating a specific travel sequence of a user, we use this user's other travel sequences for training our algorithms). Specifically, we consider all real-life travel sequences with ≥3 POI visits and evaluate the algorithms using the starting POIs and destination POIs of these travel sequences. Thereafter, we evaluate the performance of each algorithm based on the recommended tour itinerary I using the following metrics:

1. Tour Recall: TR(I). The proportion of POIs in a user's real-life travel sequence that were also recommended in itinerary I. Let Pr be the set of POIs recommended in itinerary I and Pv be the set of POIs visited in the reallife travel sequence, tour recall is defined as: TR(I) = |Pr∩Pv | |Pv| .
2. Tour Precision: TP (I). The proportion of POIs recommended in itinerary I that were also in a user's reallife travel sequence. Let Pr be the set of POIs recommended in itinerary I and Pv be the set of POIs visited in the real-life travel sequence, tour precision is defined as: TP (I) = |Pr∩Pv| |Pr| .
3. Tour F1-score: TF1 (I). The harmonic mean of both the recall and precision of a recommended tour itinerary I, defined as: TF1 (I) = 2×TP (I)×TR(I) TP (I)+TR(I) .
4. Root-Mean-Square Error (RMSE) of POI Visit Duration: TRMSE(I). The level of error between our recommended POI visit durations in itinerary I compared to the real-life POI visit durations taken by the users. Let I s ∈ I be the recommended POIs that were visited in real-life 5 , and Dr and Dv be the recommended and

4 PT-.5T out-performs PT-.5F in terms of TR (.7402 vs .7398) for Edinburgh, although both values are rounded to .740 in Table 2.

5 We can only compare POI visit durations for POIs in itinerary I that were "correctly" recommended (i.e., visited in real-life).

• real-life POI visit durations respectively, RMSE is defined as: TRMSE(I) = √∑p∈Is (Dr-Dv )2 |I s | .
• Tour Popularity: TPop(I). The overall popularity of all POIs in the recommended itinerary I, defined as: TP op(I) = ∑ p∈I P op(p).
• Tour Interest: T u Int (I). The overall interest of all POIs in the recommended itinerary I to a user u, defined as: T u Int (I) = ∑ p∈I Intu(Catp).
• Popularity and Interest Rank: T aRk . The average rank of an algorithm a based on its TPop and TInt scores ranked against other algorithms (1=best, 8=worst).

We selected these metrics to better evaluate the following: (i) time-based vs frequency-based user interest, using Metrics 1-3; (ii) personalized vs non-personalized POI visit durations, using Metric 4; and (iii) PERSTOUR vs baselines, using Metrics 5-7. As personalized POI visit durations only apply to PERSTOUR and not the baselines, we only report TRMSE scores for the PT-0, PT-.5F, PT-.5T, PT-1F and PT-1T algorithms. Our baseline for comparing TRMSE are variants of PERSTOUR that use non-personalized POI visit durations, i.e., average POI visit durations.

6 Results and Discussion

6.1 Comparison between Time-based and Frequency-based User Interest

We first study the performance difference between using time-based user interest and frequency-based user interest, as shown in Table 2. Comparing the TF1 scores between PT-.5T and PT-.5F, and between PT-1T and PT-1F, the results show that PERSTOUR using time-based user interest (PT-.5T and PT-1T) consistently out-performs its counterpart that uses frequency-based user interest (PT-.5F and PT-1F). This observation highlights the effectiveness of time-based user interest in recommending tours that more accurately reflect reallife tours of users, compared to using frequency-based user interest. While PT-1T under-performs PT-1F in terms of TR for Edinburgh and Osaka, we focus more on the TF1 scores as it provides a balanced representation of both TR and TP . Moreover, PT-.5T and PT-1T (time-based user interest) consistently results in higher TP scores, compared to its PT-.5F and PT-1F counterparts (frequency-based user interest). Another observation is that all PERSTOUR variants also consistently out-perform the three baselines, in terms of TF1 scores.

The reason for the more accurate recommendations of time-based user interest compared to frequency-based user interest is due to its use of POI visit durations instead of POI visit frequency. Consider user A who only visited two parks but spent three or more hours at each of them and user B who visited five parks but spent less than 15 minutes at each of them. Frequency-based interest incorrectly classifies user B as having more interest in the parks category due to his/her five visits, compared to user A's two visits. On the other hand, time-based interest more accurately determines that user A has a higher interest in the parks category due to his/her long visit duration, despite user A only visiting two parks. Furthermore, time-based interest can more accurately capture a user's level of interest based on how much longer this user spends at a POI compared to the average user (e.g., a user is more interested if he/she spends 3 hours at a POI when the average time spent is only 30 minutes). With the availability of user interest levels, we can better personalize POI visit duration for each unique user, which we evaluate next.

6.2 Comparison between Personalized and Non-personalized Visit Durations

The TRMSE scores in Table 3 show that our recommendation of a personalized POI visit duration (Definition 5) outperforms the non-personalized version in 19 out of 20 cases 6 , based on a smaller error in the recommended POI visit durations. This result shows that personalizing POI visit duration using time-based user interests more accurately reflects the real-life POI visit duration of users, compared to the current standard of simply using average POI visit duration.

6 Except for PT-.5T on the Osaka dataset.

Apart from recommending accurate POIs (TF1 scores), recommending the appropriate amount of time to spend at each POI is another important consideration in tour recommendation, which has not been explored in earlier works.

Previously, we have observed how time-based interest results in more accurate POI recommendations based on the TF1 scores. Our personalized POI visit duration builds upon this success by customizing the POI visit duration to each unique user based on his/her relative interest level (i.e., spend more time in a POI that interests the user, and less time in a POI that the user is less interested in). Accurate POI visit durations have another important implication in tour recommendation, where spending less time at un-interesting POIs frees up the time budget for more visits to POIs that are more interesting to the user. Similarly, a user might prefer to spend more time visiting a few POIs of great interest, compared to visiting many POIs of less interest to the user.

6.3 Comparison of Popularity and Interest

Based on the TRk scores in Table 4, we observe that PT.5T (time-based user interest) is consistently the best performer, out-performing all baselines as well as its PT-.5F counterpart that uses frequency-based user interest. In addition, we also observe that PT-1T (time-based user interest) out-performs its PT-1F counterpart (frequency-based user interest) for three out of four cities. These results show the effectiveness of time-based user interest over frequency-based user interest, based on the TRk scores.

The effects of the η parameter can be observed in the TPop and TInt scores. A value of η = 0 (PT-0) results in the best performance in TPop and worst performance in TInt, while a value of η = 1 (PT-1F and PT-1T) results in the opposite. While we include the TPop and TInt scores for completeness, we are more interested in TRk as it gives a balanced measurement of both TPop and TInt.

7 Conclusion

We modelled our tour recommendation problem based on the Orienteering problem and proposed the PERSTOUR algorithm for recommending personalized tours. Our PERSTOUR algorithm considers both POI popularity and user interest preferences to recommend suitable POIs to visit and the amount of time to spend at each POI. In addition, we implemented a framework where geo-tagged photos can be used to automatically detect real-life travel sequences, and determine POI popularity and user interest, which can then be used to train our PERSTOUR algorithm. Our work improves upon earlier tour recommendation research in two main ways: (i) we introduce time-based user interest derived from a user's visit durations at specific POIs relative to other users, instead of using a frequency-based user interest based on POI visit frequency; and (ii) we personalize POI visit duration based on the relative interest levels of individual users, instead of using the average POI visit duration for all users or not considering POI visit duration at all.

Using a Flickr dataset across four cities, we evaluate the effectiveness of our PERSTOUR algorithm against various baselines in terms of tour popularity, interest, precision, recall, F1score, and RMSE of visit duration. In particular, our experimental results show that: (i) using time-based user interest results in tours that more accurately reflect the real-life travel sequences of users, compared to using frequency-based user interest, based on precision and F1-score; (ii) our personalized POI visit duration more accurately reflects the time users spend at POIs in real-life, compared to the current standard of using average visit duration, based on the RMSE of visit duration; and (iii) PERSTOUR and its variants generally outperform all baselines in most cases, based on tour popularity, interest, precision, recall and F1-score.

Acknowledgments. National ICT Australia (NICTA) is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.