Recommender systems facilitate the decision making process for users by selecting and ranking items according to users' interests. Travellers can highly benefit from recommender systems due to vast amount of information available regarding places to visit and many diferent factors that afect the travel plans. Travel recommender systems tackle both the issues of recommending relevant places and also sequencing them in a feasible order. However there are many diferent constraints that afect the recommendations for travellers such as travel dates, weather and companions, which makes the recommendation system more complex. In this paper, we present a novel approach to create multi-day trips that start and end at the accommodation of the user. We apply diferent clustering algorithms to tackle the issue of creating multi-day trips with balanced itineraries and conduct a user study to understand how our approach performed against baseline methods. Our results show that our algorithm performs better than other selected methods to recommend interesting points-of-interests to users and create appealing itineraries.
With the growing amount of data collected and presented to the user,
ifnding relevant information gets harder every day. One approach to
solve this problem and filter through the vast amount of information
is using recommender systems. Recommender systems are tools
and techniques to support users in finding products, services or
information that are relevant according to the users’ query, profile
and context, and present them in an eficient way. One of the areas
that can highly benefit from recommender systems is the travel
industry [
TTDP addresses this issue in two parts: ranking and selection
of POIs that might interest the user, and creating a feasible route
using the selected POIs [
The paper is structured as follows: Section 2 discusses related
work in travel recommender systems and route creation algorithms,
Section 3 explains the methodology followed to create multi-day,
round trip itineraries using recommender systems and diferent
algorithms used for comparison, Section 4 discusses results from
an ofline study for the mentioned algorithms according to certain
criteria, whereas Section 5 extends these results with a user study
to evaluate the success of each algorithm. Section 6 concludes the
paper with the possible future work and final remarks.
2
Diferent approaches for TTDPs have been proposed to create
feasible sequences of POIs. Gavalas et al. [
Kurata and Hara [
In this section we discuss our novel approach for creating multiday round trip itineraries. We propose to first cluster POIs that are within the walking distance to the hotel for diferent days and then run a round trip routing algorithm to create the itineraries for each day. We compare our approach against a simple baseline algorithm. 3.1
In order to create round trips starting and ending at the hotel, the
model is defined as a travelling salesmen problem with profits model
[
The 2-opt algorithm is used to optimize the solution after each POI is selected so that it creates a shorter route that includes the same POIs, if there is a better route sequence that can be created by eliminating crossing routes (see Figures 1 and 2 for an example). The idea behind 2-opt is to switch places of POIs if the total distance of the new alignment is less than the original one. For each POI, POIs i and j are swapped if:
(, + 1) + ( , + 1) > (, ) + ( + 1, + 1) 3.2
In order to create multi-day trips, the POIs must be distributed among each day so that the routes created will have unique POIs that are selected to create routes with most profit. Therefore while creating POI lists for each day we need to take the following into account: • each day must have enough POIs to fill the time limit that is set by the traveller, • each day must have POIs that are rated highly by the traveller, • the POIs must be clustered in a way that closer POIs recommended must be in the same day. 3.2.1 Baseline algorithm. While creating multi-day trips, the baseline algorithm that is selected to create multiple round trips is running the algorithm specified for creating round trips n times, n being the number of days. For each run, the POIs that are used in the previous days will be removed from the POI list. This allows to get a baseline since this way the algorithm is able to take all POIs into account and therefore create itineraries that have closer POIs together and allows to create itineraries with multiple tours to the same location if the high rated POIs are clustered in the same location within the city. Although the itineraries are expected to include many POIs and high ratings, there are two disadvantages of the baseline approach that is expected: • The baseline algorithm takes into account all of the POIs rated by the user and if a POI with a lower score is much closer than a distant high rated POI, a selection of lower rated POIs might be favored over higher rated ones. • The baseline algorithm needs to go over all of the POIs to decide the highest profit ones, therefore running the round trip algorithm n times will have a longer runtime which is not eficient for the mobile users with lower computation power and limited battery. Consequently, the baseline algorithm
Generating Multi-Day Round Trip Itineraries for Tourists
will be compared to certain clustering algorithms in terms
of both runtime and itinerary success criteria.
3.2.2 k-means Clustering. Secondly, we used the k-means
algorithm to cluster these items. k-means allows to cluster POIs that are
closer to each other by starting with k random clusters (where k is
the number of days for the trip) and then iteratively reassigning
each POI to the cluster that is the closest one [
The second aim is to have higher rated POIs added to each cluster.
In order to create balanced itineraries for each day, we perform
pre-processing on the POI data to select the higher rated POIs
over the ones that are closer to the clusters. In order to do the
pre-processing, the recommender systems first predict ratings for
each POI by matching the user profile and information collected
about POIs. One way the recommender system can predict ratings
for the user is proposed by [
After grouping the POIs according to their relevance to the user, the clustering algorithm is first run on must-visit POIs to create clusters. Then the algorithm is re-run using the clusters created in first step and the can-visit POIs to ensure that each cluster have enough POIs to create routes while having higher rated ones preferred over others while increasing the diversity of the tour and keep the distances between them as low as possible. After creating the clusters, the top n clusters with highest average rating is selected to create round trips.
Figures 3,4 and 5 show 4-day itineraries created with the baseline, k-means and time-limit approaches respectively. It can be seen that time-limit approach has more clusters and less data points assigned to clusters as low rated POIs are discarded beforehand. 4
In order to evaluate the performance of each approach, we first compare the algorithms in an ofline analysis. To do so, we generate routes with the three algorithms using a dataset with 160 POIs and hotels in Istanbul. The hotels and POIs were selected from the attractions that are listed on Tripadvisor. We use diferent metrics to better understand the characteristics of the routes created by each algorithm: mean of average ratings, coeficient of variation of average rating and runtime of the algorithms. 4.1
For each number of days, we calculate the mean of the average ratings. For a trip with n days, where each day i has POIs selected, we sum up the ratings of the POIs of a day, divide the number by and compute the overall mean. Mean of average ratings ensures
The results presented in Figure 6 show that the time-limit approach has routes with the highest number of average ratings per day compared to the baseline and k-means approaches. This is due to the fact that the POIs are first grouped to create clusters that maximize user satisfaction by pre-filtering for highly rated POIs, which is absent in the other approaches. Therefore by the time-limit approach, POIs that have lower scores but which were closer to other POIs were favored over the ones that are higher rated but farther away during the route creation process to ensure more POIs can be added. The results are consistent with increasing number of days. The means are decreasing with more days, which is expected because more POIs with lower ratings have to be included in the routes.
Generating Multi-Day Round Trip Itineraries for Tourists preferred by the user are distributed among diferent days since each cluster is limited with an upper limit. Therefore higher rated POIs are added to diferent clusters when the upper limit for a cluster is reached and a more even distribution is obtained. However, the coeficient of variation is relatively low for all samples. We also investigated the runtime of each clustering algorithm as well as the route creation algorithm. We used an Intel Core i7 (3.1 GHz) processor for the performance analysis. In order to get reliable results, the runtime was calculated as the average of 1000 runs.
As stated before, one of the main drawbacks of the baseline algorithm is its runtime, as it executes the greedy approach on the whole dataset for each day of the route. The results in Figure 8 show that as the number of days increases, the number of comparisons and therefore the runtime increases linearly for the baseline algorithm. However, the k-means and time-limit approaches use clustering first and then run the greedy algorithm on these smaller clusters. The time-limit approach constrains the size of the clusters, therefore the input for the route creation algorithm was limited to a smaller number of POIs for each day. For the k-means algorithm, the runtime decreases as the number of days increases, because the number of POIs in each cluster decreases with more days and therefore the route creation algorithm takes less time overall.
The ofline results give an insight about how each algorithm
behaves to create routes with preferable POIs. In order to evaluate
the diferent algorithms from a user’s perspective, we conducted
a preliminary user study with the Istanbul dataset. For
mitigating the efect of diferent user preferences and limitations of the
dataset, each user is presented with predefined routes where each
POI category was given a static rating. POI categories are created
similarly to the categories proposed in [
To evaluate the behavior of diferent algorithms with a diferent number of days, each algorithm is used to create a two-day and three-day trip from selected hotels. To decrease the efect of the hotel locations on eficiency of routes, we selected two diferent hotels in diferent locations. In total, each user was presented with 12 routes. For each route, the user was asked to answer the following questions by rating each option ranging on a Likert scale ranging from strongly disagree (1) to strongly agree (5): (1) There is an adequate number of points-of-interests for each day (2) Points-of-interests are distributed evenly among each day (3) An adequate amount of time is spent on visiting points-ofinterests rather than travelling between them (4) The points-of-interests recommended are interesting (5) I’m satisfied with the overall recommendation
In total, the questionnaire was filled out by 22 people (50% female, 50% male). The user study participants were identified by sharing the questionnaire on social media and among acquaintances. In order to understand the success of the routes, participants were chosen among people who have lived in Istanbul and who thus have knowledge about the city and the presented POIs. The distribution of the ages of the participants were 0-20 (13.6%), 21-30 (59%), 31-40 (4.5%), 41-50 (4.5%), 51-60 (9%) and 61-70 (4.5%). Figures 10 and 11 show the results of each algorithm for each question for two-day and three-day trips respectively. For two-day trips the time-limit approach performed better than both other algorithms in overall recommendations (ø: 3.70, : 1.06), POIs are distributed evenly among days (ø: 3.80, : 1.16) and recommended POIs are interesting (ø: 4.32, : 0.79). For three-day trips, the time-limit approach performed better than other algorithms in all five categories.
In order to understand if the time-limit algorithm is significantly better than other algorithms, we performed a one-way ANOVA test. The results of the ANOVA test with the confidence interval of = 0.05 shows that for two-day trips the POIs recommended are significantly more interesting for the time-limit approach than both the baseline and k-means approaches, whereas the rest didn’t yield results significant enough for comparison. For three-day trips the ANOVA results shows that both the POIs are significantly more interesting and also the overall recommendations are significantly more appealing for time-limit approach than both the baseline and k-means approaches. Also for the three-day trips, the POIs are distributed more evenly among each day by the time-limit approach compared to k-means approach but not significant enough to compare to the baseline algorithm.
In this research, we propose a new route creation process for multiday round trips, starting and ending at the accommodation of the user. Our approach tags each POI according to their importance for the user, then clusters the POIs to days by limiting each cluster with the maximum amount of time the user spends on travelling per day, starting from the POIs with the highest importance to the user. By doing so, the top clusters that include high importance POIs that are closer to each other are selected. One assumption of the algorithms is that there are enough places highly rated by the user to create routes for the given number of days for the route. By creating clusters and running the round trip algorithm, which is a greedy approach that gives an approximate solution for the orienteering problem, both the runtime is decreased and POIs with higher importance are prioritized over POIs closer to the accommodation. The proposed solution allows parallelization of the route creation process, which can further increase the performance of the algorithm.
According to the ofline results and the user study, the selection of recommended POIs for the route and the overall recommendation quality of the proposed time-limit approach is better than the recommendations given by the baseline algorithm and k-means clustering. However, the current approach follows a very simple method in terms of rating and ranking POIs and was not personalized to user interests, which is also a factor that needs to be taken into account. For the future work, the route creation algorithm can be combined with a recommendation algorithm to create personalized scores for the POIs. By this way the algorithms can be tested by a more extensive user study with personalized routes.
Currently, the algorithm only takes user ratings into account when clustering POIs and creating routes. In the next step, the working hours of the POIs can be incorporated into the routing algorithm as well the clustering algorithm, so the user can visit these POIs at the suggested times. Also this could be used to further customize trips such as adding restaurants to routes for lunch time or creating certain breaks for the users between POIs. Another possible addition is using the context information to rank POIs or create diferent routes according to diferent contextual factors.