Combining multiple points of interest (POIs) to attractive and reasonable tourist trips is a challenge in the eld of Recommender Systems (RSs). Even if a user likes going to restaurants, a trip composed of too many restaurants will not be appreciated. In this position paper, we present our ideas how to improve tourist trip recommendations by focusing more on user satisfaction. We introduce the concept of item dependencies describing how POIs in uence the value of other POIs in the same trip when recommending tourist trips. Besides background information and related work in the eld of tourist trip recommendations, we present ideas to iteratively learn dependencies between items and to integrate them into the recommendation process.
Optimizing sequences of recommendations is an ongoing
challenge in the research of Recommender Systems (RSs)
[
On the other side, a craft market might be more appreciated
after visiting a related folk museum [
In order to integrate item dependencies into the recommendation process, the user's preferences and the relevant item dependencies for the user have to be collected. Advanced user interfaces and interaction options help to achieve this goal. Thus, we want to tackle the described problem from two perspectives: recommendation algorithms and the user's perspective. We de ne the following two research questions: RQ 1 How can existing algorithms be extended to consider item dependencies when recommending POI sequences? RQ 2 How can user interfaces support the users in providing feedback on mobile devices with regard to appreciated combinations of POIs?
In order to nd answers to these research questions, we will develop novel algorithms, implement them in a real working RS and evaluate their performance in large user studies. In this position paper, we start our research by presenting background information and related work. We introduce item dependencies in tourist trips and suggest a framework for sequential POI recommendations with the focus on nding the best combinations of POIs. In the end, we give an outlook on experiments we want to conduct to evaluate our work and we provide a short conclusion. 2.
In this section, we provide an introduction to the topic of tourist trip recommendations. We brie y summarize important related work in this eld and introduce the extension of item dependencies. 2.1
The problem of combining POIs to attractive and
reasonable routes is called the Tourist Trip Design Problem
(TTDP) [
Over the past years, di erent extensions of the OP have
been researched. The team orienteering problem (TOP)
aims at nding multiple routes at the same time while
avoiding overlaps [
A few variants of the OP pursue similar goals to our work.
Little attention has been given to the Generalized
Orienteering Problem (GOP) which can be applied to, for example,
reduce the value of a trip if it contains many equal
attractions. The main di erence between the OP and the GOP
is that every node in the GOP comes with a set of values
representing multiple goals of the visitor [
Extensive overviews of existing algorithms and heuristics
solving the described problems are presented by
Vansteenwegen et al. [
Some applications recommending sequences of items
exist but only a few working prototypes recommend tourist
trips. Vansteenwegen et al. developed the City Trip
Planner, a web application that recommends trips for a requested
number of days [
In most of the OP variants, a location is a node with a x value. As POIs come with certain characteristics (e.g., the POI type), we claim that the attractiveness of a tourist trip recommendation can be increased if these values are exible and dependent on the presence or absence of other POIs in the same trip.
Figure 1 shows how considering item dependencies changes the trip generation process. In this example, the black points represent restaurants, the white points POIs of other categories. The predicted ratings are in a range from 1 (lowest value) to 10 (highest value). Assuming that a user does not have the time to visit all POIs, the route of the solid line could be recommended. However, two restaurants in a trip with three POIs might not be appreciated by the user. Thus, the rating of the second restaurant perceived by the user is actually lower than the prediction (1 instead of 8). Algorithms incorporating item dependencies would therefore change the trip by the dashed line to generate a more pleasant route (assuming that including the new POI does not have any negative in uence on the other POIs of the trip).
The existing TTDP applications presented in Section 2.2
generate feasible routes but they do not consider the
described dependencies between POIs. This is an important,
open task to improve the quality of recommended tourist
trips [
To tackle the described problem, we have to develop novel algorithms considering dependencies between POIs. Furthermore, a RS has to provide user interfaces that allow to learn user preferences and item dependencies and to provide feedback on recommendations while minimizing user e ort. 3.1
We focus on trip recommendations from a user perspective and for practical applications. Hence, we will mainly develop and improve heuristics instead of exact algorithms to ensure a feasible runtime.
Greedy algorithms choose the locally optimal choice at
each step of the trip generation. One example is Dijkstra's
algorithm which already has been used to recommend tourist
trips [
User preferences and relevant item dependencies have to be elicited to improve the outcome of the presented algorithms. One goal is to reduce user interaction especially when the user is moving or already on a trip.
We suggest a conversational recommendation approach. The idea is to provide dialogues to iteratively create and update the recommendations and to use the user's feedback to learn relevant item dependencies. The key activities of our framework are illustrated in Figure 2. After predicting ratings for all POIs that come into consideration for recommendation, two iterative processes generate POI sequences and update the recommendation if the user's plans change. The key activities are explained in detail in the following. The annotations in Figure 2 show which activities aim at solving the rst (RQ 1) and which the second (RQ 2) research question.
The framework is composed of three main phases. In the
rating prediction phase, established recommendation
techniques are applied to predict ratings. These ratings
represent the value of the POI for the user regardless of other
POIs. This rating should consider the context of the
recommendation to improve the prediction. For example, an
outdoor POI should receive a lower rating when the weather
is bad. In the next phase, route generation, the RS creates
the rst route including some of the rated POIs. Therefore,
one of the algorithms introduced in Section 3.1 is applied.
In contrast to single-shot recommendations, our framework
generates routes in an iterative manner. For example, the
user can be presented with two or more alternatives for
concrete POI recommendations and can indicate her or his
preferences for one POI over the others. Other options are
suggestions for adding or removing POIs. While some
dependencies are universal (e.g., no need for two restaurants in
a row), these interactions support the RS in learning
further combinations of POIs the user appreciates or rejects.
Nevertheless, the user should not be overwhelmed with
interactions. This is why implicit feedback plays an important
role in our research. If, for example, a user spends a lot of
time at a POI, it is likely that the user is interested in
similar POIs. After each feedback phase, the RS suggests an
optimized sequence based on the user's feedback. Finally, in
the route review phase, the RS observes the user's progress
and updates the rest of the current route when the user's
plans change spontaneously. For example, when the user
spends more time at a POI, visits additional POIs or skips
suggested steps of the trip, the trip should be updated
accordingly [
In this section, we brie y want to outline our planned experiments and user studies for evaluating our work. This evaluation will be split in two parts: evaluating the recommendation algorithms and user studies for the developed user interfaces. In the end, a bigger, comprehensive study will be conducted to evaluate the RS as a whole.
A big selection of benchmark instances for the OP and its
variants exist [
The second pillar of our experiments are user studies to
measure the usability of the interfaces that support the user
to create and improve tourist trips and to learn personal item
dependencies. These interfaces will be developed in a
iterative, user-centered approach. We will start with
observations and interviews to elicit user requirements. Paper
prototypes will allow us to evaluate the usability of our drafts
before the actual implementation takes place. Di erent
versions can be compared in A/B testing. The user feedback
will be implemented in further developments of a functional
prototype. To measure usability, established questionnaires
like the System Usability Scale (SUS) can be used [
In the end, the developed interfaces will be integrated into a working application which will be evaluated in lab and eld studies with real users.
In this paper, we targeted the issue of item dependencies in tourist trips. We presented a framework that can be used to iteratively generate and improve recommendations. The framework represents the starting point of our research in the eld of sequential recommendations. The goal is to use it for the development of a real working mobile RS. Hence, our next step is to examine which existing TTDP algorithms can be extended to consider the in uence of POIs on other POIs in a tourist trip. As there are no existing solutions considering dependencies, we have to develop multiple algorithms and compare them with regard to quality of the trips, a feasible runtime and user satisfaction.
The second key aspect of future work is the development and evaluation of interfaces facilitating the creation of pleasant sequences. They should allow the user to express her or his travel preferences and the application to learn relevant dependencies between POIs. When the user's plans change spontaneously, dialogues can support the modi cation of the trip. These dialogues must not be too distracting or annoying, especially when the user is moving. Thus, implicit feedback plays an important role.
The expected outcome of our research is a sequential RS that outperforms previous solutions with regard to attractiveness of the trips and usability of the system. We want to evaluate our algorithms and the conversational RS in large user studies in a realistic environment. This is why we will develop a mobile application for recommending POI sequences.