Exploiting Item Dependencies to Improve Tourist Trip Recommendations Daniel Herzog Wolfgang Wörndl Department of Informatics Department of Informatics Technical University of Munich Technical University of Munich Boltzmannstr. 3, 85748 Garching, Germany Boltzmannstr. 3, 85748 Garching, Germany herzogd@in.tum.de woerndl@in.tum.de ABSTRACT On the other side, a craft market might be more appreciated Combining multiple points of interest (POIs) to attractive after visiting a related folk museum [19]. The examples show and reasonable tourist trips is a challenge in the field of that the total value of a trip is not the sum of the predicted Recommender Systems (RSs). Even if a user likes going to ratings of the POIs. Instead, the value of a POI for a user restaurants, a trip composed of too many restaurants will is influenced by other POIs in the same trip. We call this not be appreciated. In this position paper, we present our influence item dependencies. Such item dependencies can ideas how to improve tourist trip recommendations by focus- follow a general pattern (e.g., limiting restaurants in a trip ing more on user satisfaction. We introduce the concept of to a reasonable number) but usually differ between users item dependencies describing how POIs influence the value because of personal preferences. of other POIs in the same trip when recommending tourist In order to integrate item dependencies into the recom- trips. Besides background information and related work in mendation process, the user’s preferences and the relevant the field of tourist trip recommendations, we present ideas item dependencies for the user have to be collected. Ad- to iteratively learn dependencies between items and to inte- vanced user interfaces and interaction options help to achieve grate them into the recommendation process. this goal. Thus, we want to tackle the described problem from two perspectives: recommendation algorithms and the user’s perspective. We define the following two research CCS Concepts questions: •Information systems → Recommender systems; •Human-centered computing → Human computer in- RQ 1 How can existing algorithms be extended to consider teraction (HCI); item dependencies when recommending POI sequences? RQ 2 How can user interfaces support the users in providing Keywords feedback on mobile devices with regard to appreciated Item Dependencies, Sequential Recommendation, Tourist combinations of POIs? Trip Design Problem, POI, User Interface In order to find answers to these research questions, we will develop novel algorithms, implement them in a real 1. INTRODUCTION AND MOTIVATION working RS and evaluate their performance in large user Optimizing sequences of recommendations is an ongoing studies. In this position paper, we start our research by challenge in the research of Recommender Systems (RSs) presenting background information and related work. We [13]. One example of sequential recommendations are tourist introduce item dependencies in tourist trips and suggest a trips composed of multiple points of interest (POIs) such framework for sequential POI recommendations with the fo- as restaurants, museums or monuments. Finding the right cus on finding the best combinations of POIs. In the end, combination of POIs for a tourist trip is a complex task. we give an outlook on experiments we want to conduct to Combining the highest rated POIs into a sequence does not evaluate our work and we provide a short conclusion. guarantee the highest possible user satisfaction when one POI has a negative influence on another POI or the trip it- 2. BACKGROUND AND RELATED WORK self. For example, a person who likes going to restaurants will most likely prefer daily trips including one or two restau- In this section, we provide an introduction to the topic of rants but every additional restaurant may be less appealing. tourist trip recommendations. We briefly summarize impor- tant related work in this field and introduce the extension of item dependencies. 2.1 Related Tourist Trip Design Problems The problem of combining POIs to attractive and rea- sonable routes is called the Tourist Trip Design Problem (TTDP) [19]. In its simplest specification, the TTDP is Copyright held by the author(s). identical to the Orienteering Problem (OP): every location RecTour 2016 - Workshop on Recommenders in Tourism held in conjunc- tion with the 10th ACM Conference on Recommender Systems (RecSys), which can be visited has a value but a time budget and the September 15, 2016, Boston, MA, USA. known travel time between the points restricts the number of possible routes [15]. The OP aims to find a route which includes some of the points to maximize the overall value for the traveler while not exceeding the time budget. Over the past years, different extensions of the OP have been researched. The team orienteering problem (TOP) aims at finding multiple routes at the same time while avoid- ing overlaps [4]. In the (T)OP with time windows (TOPTW), each location can only be visited within a defined time win- Figure 1: Item dependencies in a tourist trip dow (e.g., the opening hours of that POI) [18]. Further variants allow the integration of inter-modal transportation into the trip planning [6] or add multiple constraints [14]. 2.3 Item Dependencies in Tourist Trip Rec- A few variants of the OP pursue similar goals to our work. Little attention has been given to the Generalized Orienteer- ommendations ing Problem (GOP) which can be applied to, for example, In most of the OP variants, a location is a node with a fix reduce the value of a trip if it contains many equal attrac- value. As POIs come with certain characteristics (e.g., the tions. The main difference between the OP and the GOP POI type), we claim that the attractiveness of a tourist trip is that every node in the GOP comes with a set of values recommendation can be increased if these values are flexible representing multiple goals of the visitor [10]. Other vari- and dependent on the presence or absence of other POIs in ants close to our problem are the OP with variable profits the same trip. (OPVP) [5], the TOP with decreasing profits (DPTOP) [1] Figure 1 shows how considering item dependencies changes and the Clustered OP (COP) [2]. The OPVP assumes that the trip generation process. In this example, the black points the node values depend on a number of discrete passes or represent restaurants, the white points POIs of other cate- the time spent at the node. In the DPTOP the profit of gories. The predicted ratings are in a range from 1 (lowest each node decreases with time and in the COP the score of value) to 10 (highest value). Assuming that a user does a node can only be gained if all nodes of a group of nodes not have the time to visit all POIs, the route of the solid are part of the path. line could be recommended. However, two restaurants in a Extensive overviews of existing algorithms and heuristics trip with three POIs might not be appreciated by the user. solving the described problems are presented by Vansteen- Thus, the rating of the second restaurant perceived by the wegen et al. [17], Gavalas et al. [9] and Gunawan et al. user is actually lower than the prediction (1 instead of 8). [11]. So far, no existing work considers individual depen- Algorithms incorporating item dependencies would therefore dencies between POIs, e.g., the influence of a restaurant on change the trip by the dashed line to generate a more pleas- another POI. In our work, we want to develop heuristics that ant route (assuming that including the new POI does not maximize the user satisfaction by incorporating item depen- have any negative influence on the other POIs of the trip). dencies and that can be used for practical applications. The existing TTDP applications presented in Section 2.2 generate feasible routes but they do not consider the de- 2.2 Existing Tourist Trip Applications scribed dependencies between POIs. This is an important, Some applications recommending sequences of items ex- open task to improve the quality of recommended tourist ist but only a few working prototypes recommend tourist trips [21]. trips. Vansteenwegen et al. developed the City Trip Plan- ner, a web application that recommends trips for a requested 3. PROPOSED SOLUTION AND NEXT RE- number of days [16]. It respects limitations like opening SEARCH STEPS hours and can include a lunch break into the trip. An up- To tackle the described problem, we have to develop novel dated version is available at www.citytripplanner.com. A algorithms considering dependencies between POIs. Fur- similar application for multi-day tourist trips is DailyTRIP thermore, a RS has to provide user interfaces that allow to [8]. Wörndl and Hefele [21] developed a web application for learn user preferences and item dependencies and to provide finding city trips. It uses Foursquare to predict POI ratings feedback on recommendations while minimizing user effort. for the user and extends Dijkstra’s algorithm to generate routes. Garcia et al. developed a desktop and mobile pro- 3.1 Extending Existing TTDP Algorithms totype for recommending trips in San Sebastián [7]. mTrip We focus on trip recommendations from a user perspective (www.mtrip.com/en/travel-guide/) is a mobile tourist guide and for practical applications. Hence, we will mainly develop available for Android and iOS. Some of these applications al- and improve heuristics instead of exact algorithms to ensure low basic customization after a trip has been recommended, a feasible runtime. e.g., removing single POIs or use more iterative dialogues Greedy algorithms choose the locally optimal choice at between the user and the system to find travel packages [20] each step of the trip generation. One example is Dijkstra’s [12]. None of them provides advanced user interfaces to learn algorithm which already has been used to recommend tourist and consider individual dependencies between POIs, which trips [21]. Such an algorithm can be adapted to use flexible is an important task when improving the selection of items values that change depending on the already visited nodes in a sequential RS. of the graph. Other approaches solving the OP start with finding a path using a greedy algorithm and then update the path in an iterative manner, i.e., removing or replacing single nodes of the generated path [4]. This is another promising solution for incorporating item dependencies. After a first path has been found, single POIs can be replaced or removed generates routes in an iterative manner. For example, the user can be presented with two or more alternatives for con- crete POI recommendations and can indicate her or his pref- erences for one POI over the others. Other options are sug- gestions for adding or removing POIs. While some depen- dencies are universal (e.g., no need for two restaurants in a row), these interactions support the RS in learning fur- ther combinations of POIs the user appreciates or rejects. Nevertheless, the user should not be overwhelmed with in- teractions. 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 sim- ilar 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 ac- cordingly [19]. Again, interfaces allow the user to select her or his preferences if, for example, another POI should be added to the trip. The challenge is to update the route while considering the already visited POIs and their item dependencies. Furthermore, the system has to inform the user if a previously chosen POI cannot be visited during the Figure 2: Activity diagram of our framework for trip anymore. generating and updating a tourist trip 3.3 Evaluations and User Studies if this has a positive effect on other POIs or the trip, as In this section, we briefly want to outline our planned ex- presented in Figure 1. Another idea is to extend a tabu periments and user studies for evaluating our work. This search heuristic which already has been applied for more evaluation will be split in two parts: evaluating the rec- complex OP variants [14]. ommendation 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. 3.2 Creating Routes and Learning Item De- A big selection of benchmark instances for the OP and its pendencies variants exist [17] [11]. However, our goal is not to find exact User preferences and relevant item dependencies have to solutions for the OP with item dependencies. Instead, our be elicited to improve the outcome of the presented algo- focus are practical applications. This is why we tackle the rithms. One goal is to reduce user interaction especially problem with heuristics that provide satisfying solution in a when the user is moving or already on a trip. feasible time. Another problem is that our approaches for We suggest a conversational recommendation approach. solving the OP with item dependencies can not be compared The idea is to provide dialogues to iteratively create and to the benchmark instances of other variants. In our prob- update the recommendations and to use the user’s feedback lem, the value of a node is flexible and depending on other to learn relevant item dependencies. The key activities of nodes in the same path. Hence, the maximum total value of our framework are illustrated in Figure 2. After predicting the trip can differ significantly. To tackle the described chal- ratings for all POIs that come into consideration for recom- lenges, we will develop different algorithms considering item mendation, two iterative processes generate POI sequences dependencies. Like this, we can compare the algorithms with and update the recommendation if the user’s plans change. each other and identify the most promising approaches. For The key activities are explained in detail in the following. a comparison with algorithms solving the TTDP without The annotations in Figure 2 show which activities aim at item dependencies, we will conduct user studies aiming at solving the first (RQ 1) and which the second (RQ 2) re- measuring the user satisfaction. We will present tourist trips search question. created by different algorithms and let the user evaluate the The framework is composed of three main phases. In the quality of the trip and their satisfaction. rating prediction phase, established recommendation tech- The second pillar of our experiments are user studies to niques are applied to predict ratings. These ratings repre- measure the usability of the interfaces that support the user sent the value of the POI for the user regardless of other to create and improve tourist trips and to learn personal item POIs. This rating should consider the context of the rec- dependencies. These interfaces will be developed in a iter- ommendation to improve the prediction. For example, an ative, user-centered approach. We will start with observa- outdoor POI should receive a lower rating when the weather tions and interviews to elicit user requirements. Paper pro- is bad. In the next phase, route generation, the RS creates totypes will allow us to evaluate the usability of our drafts the first route including some of the rated POIs. Therefore, before the actual implementation takes place. Different ver- one of the algorithms introduced in Section 3.1 is applied. sions can be compared in A/B testing. The user feedback In contrast to single-shot recommendations, our framework will be implemented in further developments of a functional prototype. To measure usability, established questionnaires Engineering, ICWE’10, pages 486–497, Berlin, like the System Usability Scale (SUS) can be used [3]. This Heidelberg, 2010. Springer-Verlag. questionnaire consists of ten questions providing a global [8] D. Gavalas, M. Kenteris, C. Konstantopoulos, and view of subjective assessments of usability. Based on the re- G. Pantziou. Web application for recommending sponses, a SUS score can be calculated to measure usability personalised mobile tourist routes. Software, IET, and to compare different systems. 6(4):313–322, 2012. In the end, the developed interfaces will be integrated into [9] D. Gavalas, C. Konstantopoulos, K. Mastakas, and a working application which will be evaluated in lab and field G. Pantziou. A survey on algorithmic approaches for studies with real users. solving tourist trip design problems. Journal of Heuristics, 20(3):291–328, June 2014. 4. CONCLUSION [10] Z. W. Geem, C.-L. Tseng, and Y. Park. Harmony In this paper, we targeted the issue of item dependencies search for generalized orienteering problem: best in tourist trips. We presented a framework that can be used touring in china. In L. Wang, K. Chen, and Y. S. Ong, to iteratively generate and improve recommendations. The editors, Advances in natural computation, pages framework represents the starting point of our research in 741–750. Springer Berlin Heidelberg, Berlin, the field of sequential recommendations. The goal is to use Heidelberg, 2005. it for the development of a real working mobile RS. Hence, [11] A. Gunawan, H. C. Lau, and P. Vansteenwegen. our next step is to examine which existing TTDP algorithms Orienteering problem: A survey of recent variants, can be extended to consider the influence of POIs on other solution approaches and applications. European POIs in a tourist trip. As there are no existing solutions Journal of Operational Research, 2016. considering dependencies, we have to develop multiple al- [12] T. Mahmood, F. Ricci, and A. Venturini. Improving gorithms and compare them with regard to quality of the recommendation effectiveness: Adapting a dialogue trips, a feasible runtime and user satisfaction. strategy in online travel planning. Information The second key aspect of future work is the development Technology & Tourism, 11(4):285–302, 2009. and evaluation of interfaces facilitating the creation of pleas- [13] F. Ricci, L. Rokach, and B. Shapira. Recommender ant sequences. They should allow the user to express her or systems: Introduction and challenges. In his travel preferences and the application to learn relevant Recommender Systems Handbook, pages 1–34. dependencies between POIs. When the user’s plans change Springer, 2015. spontaneously, dialogues can support the modification of the [14] K. Sylejmani, J. Dorn, and N. Musliu. A tabu search trip. These dialogues must not be too distracting or an- approach for multi constrained team orienteering noying, especially when the user is moving. Thus, implicit problem and its application in touristic trip planning. feedback plays an important role. In Hybrid Intelligent Systems (HIS), 2012 12th The expected outcome of our research is a sequential RS International Conference on, pages 300–305, Dec 2012. that outperforms previous solutions with regard to attrac- [15] T. Tsiligirides. Heuristic methods applied to tiveness of the trips and usability of the system. We want orienteering. Journal of the Operational Research to evaluate our algorithms and the conversational RS in Society, pages 797–809, 1984. large user studies in a realistic environment. This is why [16] P. Vansteenwegen, W. Souffriau, G. V. Berghe, and we will develop a mobile application for recommending POI D. V. Oudheusden. The city trip planner. Expert Syst. sequences. Appl., 38(6):6540–6546, June 2011. [17] P. Vansteenwegen, W. Souffriau, and 5. REFERENCES D. Van Oudheusden. The orienteering problem: A [1] H. M. Afsar and N. Labadie. Team orienteering survey. European Journal of Operational Research, problem with decreasing profits. Electronic Notes in 209(1):1–10, 2011. Discrete Mathematics, 41:285 – 293, 2013. [18] P. Vansteenwegen, W. Souffriau, G. Vanden Berghe, [2] E. Angelelli, C. Archetti, and M. Vindigni. The and D. Van Oudheusden. Iterated local search for the clustered orienteering problem. European Journal of team orienteering problem with time windows. Operational Research, 238(2):404 – 414, 2014. Comput. Oper. Res., 36(12):3281–3290, Dec. 2009. [3] J. Brooke. SUS-A quick and dirty usability scale. [19] P. Vansteenwegen and D. Van Oudheusden. The Usability evaluation in industry, pages 189–194, 1996. mobile tourist guide: an or opportunity. OR Insight, [4] I.-M. Chao, B. L. Golden, and E. A. Wasil. The team 20(3):21–27, 2007. orienteering problem. European journal of operational [20] A. Venturini and F. Ricci. Applying trip@dvice research, 88(3):464–474, 1996. recommendation technology to www.visiteurope.com. [5] G. Erdogan and G. Laporte. The orienteering problem In Proceedings of the 2006 Conference on ECAI 2006: with variable profits. Networks, 61(2):104–116, March 17th European Conference on Artificial Intelligence 2013. August 29 – September 1, 2006, Riva Del Garda, Italy, [6] F. V. Fomin and A. Lingas. Approximation algorithms pages 607–611, Amsterdam, The Netherlands, The for time-dependent orienteering. Information Netherlands, 2006. IOS Press. Processing Letters, 83(2):57–62, 2002. [21] W. Wörndl and A. Hefele. Generating paths through [7] A. Garcia, O. Arbelaitz, M. T. Linaza, discovered places-of-interests for city trip planning. In P. Vansteenwegen, and W. Souffriau. Personalized Information and Communication Technologies in tourist route generation. In Proceedings of the 10th Tourism 2016, pages 441–453. Springer, 2016. International Conference on Current Trends in Web