Tourism Recommender Systems (TRS) assist tourists in designing a plan for a soon-to-be visited city, which consists of a selection of relevant points-of-interest (POI), the order in which they will be visited, the start and end time of the visits, etc. These tools iflter POIs based on the tourist's preferences and take into account time constraints, like the desired duration of the plan, or the POI's opening or closing times. However, being able to provide tourists with an additional travel plan which explains how to reach those POIs using public transportation is a feature in which TRSs come short. Existing solutions try to solve the problem in a simplified way and do not model all possible events involved in using public transportation, such as combining transfer times and trips, changing vehicles, or dealing with delays of transportation units. We therefore propose three novel approaches to generate visit plans and their corresponding travel plans, namely SILS, TRILS and PHILS, which overcome these weaknesses. These approaches generate visit plans by iteratively adjusting them according to the traveling information and difer in the way the adjustment is done. Our experiments on a real-world POI dataset and public transportation information of the city of Izmir show that our approaches outperform the stateof-the-art in terms of quality of recommendations. Moreover, they are also able to provide both visit and travel plans in real-time and are robust in case of delays. To the best of our knowledge previous approaches have not been able to achieve this level of practicality.
Visiting touristic attractions, walking through historical places, or trying local food are among the main activities tourists undertake when they visit a new city or country. Given that the number of attractions is typically large and that tourists are also restricted to time and/or money budgets, they need to optimize and sometimes compromise on the selection of relevant attractions. In addition to this, they also have to figure out if the place is reachable and eventually find a feasible way to reach the location using public transportation. This process can be very cumbersome. Therefore, Tourism Recommender Systems (TRS) have been developed for assisting tourists in planning their trips.
In the literature the problem of generating a visit plan (no public
transportation involved) is known as the tourist trip design
problem (TTDP) [
In this paper we aim at additionally integrating public
transportation information to assist the user in traveling from one attraction
to the next one. This feature is indeed perceived by tourists as one of
the most useful functionalities [
Surprisingly, integrating public transportation information is
still quite unexplored [
Existing solutions for TTDP, which integrate public
transportation information (and therefore, with the time-dependency
constraint) such as [
It is important to note that incorporating real-time transportation information of a city and generating a travel plan T with detailed instructions to move along POIs, even in case of delays, is not provided by any approach so far, to the best of our knowledge. We therefore propose such an approach which generates a sequence of attractions to visit, together with a travel plan with concrete instructions for the user. In total, we make the following contributions: (1) We combine i) an approach for generating a sequence of attractions to be visited, using the time constraints regarding attractions and total trip time (i.e. solving the TTDP problem and using the time-dependency constraint for public transportation) with ii) an approach for generating a realistic, delay-aware travel plan. We employ three diferent strategies (sections 5.1 to 5.3). The travel plan generation is designed to be realistic, as it uses the realtime transportation system’s information (departure times with potential delays) and the current place and time of the user. Furthermore, the real-time computation constraint is considered. 1In this paper, we assume that the user does not want to leave the attractions earlier than planed, as this might stress her and as it would make the problem hardly manageable. (2) We evaluate our three approaches extensively with a large real-world data set, namely the POIs and the public transportation information of Izmir, Turkey. This data set contains 75 POIs, and a large transportation network which consists of approx. 8K stations and 26K bus runs per day. Our evaluation results show that the designed strategies outperform the state-of-the-art in terms of quality of recommendations.
Our approach is applicable to tourist plan recommendation in any city or location in which data about the attractions, their locations, and availability times are available, as its real-time public transportation system information.
The rest of the paper is organized as follows: First we give an overview of the TTDP and the approaches to solve that problem in Related Work (section 2). Then we present the Task Description (section 3) and the models our approaches are based on. We explain the basic concepts of the state-of-the-art method to solve the TTDP, the Iterated Local Search (ILS), in section 4. Section 5 describes our main contribution, three approaches built on top of ILS, i.e. SILS, TRILS, and PHILS, to produce feasible and realistic trip and travel plans. The experiments are shown in section 6. Finally, conclusions and future work are presented in section 7. 2
The tourist trip design problem (TTDP) is the problem of generating
a sequence of the most relevant POIs to visit without violating user
restrictions such as time budget. Although the TTDP has been
widely investigated, a gap remains between theoretically solving
TTDPs and applying them in practice [
One of the earlier works which addresses the TTDP problem is
the one by Tumas and Ricci [
However, most of the solutions seen in the literature consist of
modeling the problem as extensions of the Orienteering problem
(OP). The OP is a combination of two classical problems: the
Knapsack Problem and the Traveling Salesman problem. This problem
can be defined formally as a graph in which nodes represent POIs
and the edges a feasible travel route from one POI to another one.
Each node has a “profit ‘score” (henceforth simply “profit”) that
the user can collect by visiting the POI and the edges are weighted
with travel times. The OP and its variations cannot be solved in
polynomial time and therefore most of the solutions proposed are
based on meta-heuristic algorithms which provide near-optimal
solutions [
State-of-the-art for TD(T)OPTW. Garcia et al. [
Other approaches to solve TTDP. While the most popular
version of ILS is the one proposed by Vansteenwegen [
Completely diferent strategies have been suggested as well,
in addition to these ILS heuristics. In [
Figure. 1 illustrates the desired result, i.e. plans, V and T . In order to explain the underlying models used in our approach we need to provide some fundamental definitions. The POIs part of the visit plan V are selected among the set of available POIs P = {p1, p2, ..., pn }. Each POI has a time window [oi , ci ] with opening time oi and closing time ci . Therefore, visits should take place within the time window. There is a variable for each POI pi which models if the user visits it or not. Let vi be this variable: vi = 1 if pi is visited and included in the plan V , 0 otherwise. Let tiv be the time the tourist u spends at pi , if vi = 1. If the visit takes place, this time is fixed, i.e. each POI has a recommended visit time and we assume for simplicity this cannot be shortened or extended. Let tis be the start time of a visit at pi . Then, the ending time of a visit is simply given by tie = tis + tiv . The time required to travel from pi to pj is w(ti, j). This times depends on the departure time t from pi . When a tourist visits a POI pi she collects the profit si . Furthermore, let x(i, j) be a variable which models the fact that u visits pj after she visited pi . If this occurs, then x(i, j) = 1, and 0 otherwise. The overall visit time for a plan should not exceed the tourist’s total available time. Let tmax be the time budget of u. The goal is to generate a visit plan V together with a travel plan T (which includes the detailed instructions tailored for public transportation). The time-dependency itself is modeled within w(ti, j). Therefore, we call this problem the tourist trip design problem with travel instructions (TTDP-TI). This can be divided into two subtasks: (1) the generation of a visit plan V taking into account the time-dependency, and (2) providing the travel instructions. Each of these subtasks will be explained in the following subsections. 3.2
The TTDP part of our problem is modeled as the time-dependent
orienteering problem with time windows (TDOPTW). The goal is
to produce a visit plan V , i.e. a route r which goes through some
of the available POIs, thereby collecting as much profit as possible
(objective function). For this problem one POI is required as the
starting point and one as the ending point of the trip. Typically p1
and pn are picked as start and end locations [
POI included in V should be visited at most once. (3) The waiting time before a visit at a POI starts is limited by a constant M.
tie + w(ti, j) − tjs ≤ M(1 − x(i, j)), (i, j = 1, ..., n). (4) The total time spent for the trip which includes the visit times, travel times and eventually the waiting times before a visit takes place should be less than the specified time budget tmax .
(5) The visits take place within the POI’s time window.
In the same way as OP, TDOPTW can be formulated in two possible
ways: as a graph or as integer linear programming problem. We refer
to Vansteenwegen et al. [
The sequence V = (pi , ..., pk ) is reconstructed from the variables x(l,m), each of which represents a consecutive visit. In addition to V the visitation times for the each POI, ((tis , tie ), ..., (tks , tke )) are returned. It is important here to notice that getting the travel plans T (i.e. how to reach POIs) are beyond the scope of TDOPTW. They are generated by a separate algorithm, if needed. Most of the solutions relax the travel time w(ti, j) by removing the time-dependency: w(i, j). Therefore, when the plan is adjusted according to real travel times, this might become infeasible (see section 5).
One important aspect of the TTDP is to determine the importance of a POI for a user u, i.e. to estimate the profit si the user could get by visiting the POI. This can be done in diferent ways. 3.3
In order to obtain the travel instructions T we make use of a route
planner in real-time. In fact, designing approaches which provide
travel plans has been one of the main concerns of route planning.
Not only the time-dependency, but also the real-time requirement
are aspects which have been widely studied in this field. To fulfill
the real-time requirement graphs are the most recurrent models in
public transportation [
We now come back to the TTDP problem, which is modeled in
our case as a TDOPTW. In this regard the Iterated Local Search
(ILS) heuristic is the state-of-the-art to solve TDOPTW. Our three
approaches, SILS, TRILS, and PHILS are built upon ILS as
conceived by Vansteenwegen [
Insertion Step. In the insertion step, a new visit (POI) is added to the tour. The POI with the highest Ratioi is always the one picked for the insertion and we calculate Ratioi as follows:
Ratioi = (si )2/Shi f ti (1) where si is the profit, and Shi f ti is the extra time added to the duration of the trip plan if pi is added to it. To compute the extra time, not only the visiting time of pi is taken into account but also the travel time from the previous POI and to the following POI in the sequence. Since time is limited by the time budget tmax , every time we insert a new POI it is checked whether existing visits still ift in their corresponding POI’s time window.
Shake Step. The shake step removes at least one visit from the given tour. The purpose of this step is to escape local optima. The soon-to-be-removed POI is selected in a random fashion by means of variables which rotate over the whole visit plan. The visits scheduled after the removed POI are shifted towards the beginning to avoid unnecessary waiting times. Some of the visits may not be shifted because of the time window constraint. The visits after those non-shiftable visits remain unchanged.
For further details about the used variables and how these are
updated in both the INSERT and SHAKE steps, we refer the reader
to [
ILS: combining both steps. A pseudo-code showing the key steps
of the ILS can be found in [
The insertion operation deals directly with the time-dependency, because the travel time from the previous POI has to be considered in order to place the inserted POI at the right position in time. This might lead to the false belief that this information can be directly requested from the route planner every time an insertion is carried out. However, in practice too many visits are inserted and therefore the number of requests sent to the route planner would be too high to keep the whole computation of ILS operating in real-time.
Therefore, works like that of García et al. [
A method to produce a visit plan V based on pre-computed values
might difer from the real travel times provided by a route planner.
Therefore, a visit plan might have to be adjusted, i.e. the travel time
between POIs has to be corrected. This might cause an increase in
the waiting time or a shift of the visit times. If the time window of
any of the POIs included in the solution is violated, then the plan
is said to be infeasible [
We therefore designed three strategies which not only provide
feasible visit plans but also avoid sacrificing profit. The novelty
2This value has been empirically found in the experiments of Vansteenwegen and is
a good trade-of between the execution time and the quality of the solution. In that
setting the results of the ILS metaheuristic deviate from the optimal solution by only
1.8% using only 1 second of computation [
The logic of SILS is illustrated in Figure 2. The intuition behind this heuristic is as follows: When NoImprovementCounter=150 the found visit plan is adjusted with respect to the real travel times returned by the route planner. If after this adjustment the visit plan is feasible, this is returned as the solution (Va ).
Otherwise, the plan is repaired by removing the POIs in which the time window constraints are violated. The repaired solution Vr is then given to the ILS heuristic, which continues the search for an optimal solution from the plan. In addition, the removed POI(s) are penalized and relocated among other POI candidates with a profit si = 0. This basically disables the POI, which cannot be selected anymore (Ratioi = 0). Moreover, the NoImprovementCounter is set to 0.
The process is repeated until a feasible visit plan is returned. Note that this approach can fail if all POIs are disabled. However, this never occurred in our experiments. 5.2
The logic of TRILS is illustrated in Figure 3. Excluding one or more POIs from the ILS computation might not help in situations where the average travel time is a bad estimator of the actual travel time. This is the case when the timetable is not very regular or when the variance of the travel times in a day is too large.
Therefore, this approach rather gradually increases the estimated average travel times every time a solution is infeasible by multiplying it with a constant (step = 0.05). In this way the estimated travel times can be greater than the real travel times at some point and therefore a feasible plan can be returned. The downside of this strategy is that it might exclude more compact solutions with a higher profit.
As in SILS, TRILS checks the validity of the solution when NoImprovementCounter=150. The visit plan is validated against the real time travels returned by the route planner. If after the adjustment, the visit plan is feasible, this is returned as the solution (Va ). Otherwise, the plan is repaired by removing the POIs in which the visits violate the time window constraints. In addition to this, the average travel times are increased by a constant. The first time an infeasible solution is returned, the average travel times are multiplied by 1.05. The second time by 1.10, and so on. The ILS heuristic continues the computation using the repaired plan Vr . It is important to notice that although the profits of the removed POIs remain unchanged, the insert operation might exclude them because of the increased average travel time, which potentially reduces the number of time slots into which these can be potentially inserted.
The process of increasing the average travel times is repeated until eventually a feasible solution is found. The approach fails if the average travel times are increased 5 times. However, this never occurred in our experiments. 5.3
The logic of PHILS is shown in Figure 4. This approach combines the ideas of the two previous approaches in a more fine-grained fashion. First, this approach tries to validate the current best solution when NoImprovementCounter=50, i.e. at an earlier stage of the solution computation. Let V be the best known plan at this point of calculation. If the alignment with the route planner does not cause the visit plan to be infeasible, then the ILS continues the search for a better solution. If no better solution is found until NoImprovementCounter=150 then the visit plan Va , which is already adjusted, is returned as the solution.
In contrast, if the adjustment causes the plan V to be infeasible three measures are taken: (1) if pi is the POI in V = {..., pj , pi , ...} in which the time window constraint is violated, then the average travel time between pj and pi is increased. Note that this correction is done for only a single pair of POIs and not for all possible pairs as in TRILS. (2) Instead of letting the ILS continue the search from the repaired plan Vr , the previous best known solution is retrieved. Let V ′ be this solution. (3) If V ′ contains pi , then this is removed from it and this solution is used as the new starting point. The intuition is that it is better to correct the solution which lead to the infeasible plan, rather than the plan itself. Then, the ID of pi and the position k in the sequence at which it failed are stored. If pi disrupts another solution at the same position, pi is permanently removed from the candidate set. Note that pi is disabled when the failure is produced at the same position k in the sequence and not simply when it occurs, as in SILS. The ILS continues the search for a better solution based on the repaired plan Vr′. The process is then repeated until a feasible visit plan is produced. 5.4
To generate the travel instructions T required to move from one POI to the next one in the sequence, the route planner can simply store the travel plans (including the travel instructions) of the last adjusted visit plan V . In fact, the last-adjusted plan is also the final returned solution in all three strategies.
To summarize. The three approaches are able to produce feasible solutions, in contrast to approaches based on ILS and average travel times. On the one hand, in the case of SILS and TRILS, the solution is adjusted according to the real travel times before it is returned as the final solution. If the adjusted plan is infeasible, some corrections are being made in the selection strategy, i.e. disabling an out-ofwindow POI, or increasing the average travel times, respectively. A new optimal solution is then searched iteratively on top of that repaired plan. On the other hand, PHILS combines both strategies in a more fine-grained manner. The travel instructions are provided by the route planner without the need for further calculations. 6
The ultimate goal of Recommender Systems is to maximize the user satisfaction. Solutions which model the TTDP as TDOPTW or similar extensions assume that profit is a good measure of the user’s satisfaction. Therefore, they are compared based on their collected profit under the same constraints. We follow the same line of evaluation. An additional aspect we assess is whether our approaches are able to provide a plan in real-time. 6.1
Set up Our POI dataset for Izmir consists of 75 POIs in total. POI information like the labels used to build both the user and POI profiles are obtained from Foursquare3. The POIs are distributed in 4 Regions (see figure 5): 36 are located within the city center; 17 POIs in the north; 8 POIs east; 11 POIs south-west and 3 POIs outside of the city 3https://developer.foursquare.com/ (not shown in the map). The General Directorate of ESHOT4, the public bus transportation corporation of the Municipality of Izmir, Turkey kindly provided us with the public transportation data upon request. All POIs can be reached using the public transportation network. The network consists of 7788 stations and 333 working bus lines operating both ways, which results in 25849 bus runs in a single day.
In order evaluate the performance of the diferent approaches
we first build visit plan requests. Using two of the 75 available
POIs as the starting and ending points of the tour, we produce
75 × 75 = 5625 requests for visit plans. Note that this also includes
the case in which the same POI is used as both starting and ending
point. This simply means that a route would start and end at the
same position, but it might still contain an arbitrary number of
POIs to visit based on the user’s specified time budget. The time
budget is set as either 4, 6 or 8 hours. Starting times of the visit plan
are either 10:00 or 12:00. This gives us 6 time-spans, 10:00 to 14:00
(4 hours), 10:00 to 16:00 (6 hours), 10:00 to 18:00 (8 hours), 12:00 to
16:00 (4 hours), etc. In addition, we also consider 5 diferent user
profiles. To summarize, we have 5 × 5625 × 6 = 168, 750 requests
for visit plans. The following approaches are compared:
(1) AvgILS. This is the approach implemented by García et al. [
Each of the approaches is evaluated under two diferent circumstances: Without Delays (ND), i.e. the case in which all bus units run perfectly on time according to their timetable, and With Delays (D), in which delays are simulated at the level of single transportation units. Note that we assume that the time of request 4General Directorate of ESHOT. http://www.eshot.gov.tr is the start of each time-span, i.e. either 10:00 or 12:00. The delays are therefore introduced before the time of request.
The evaluated metrics are shown at the end of the results table. All experiments were conducted on a single machine with 40 GB of RAM and a 64 bit Intel Xeon E5-2640, 2.5 GHz processor. The route planner ran for the entire duration of the experiments. 6.2
Tables 1 to 5 show the results of our experiments for each approach without and with delays in the transportation network. Each table’s cell condenses the scores obtained for all requests and the five considered profiles in the given timespan. Moreover, for each timespan and metric the best scores achieved are shown in red. Without delays (left tables). SILS produced 0.07% more profit than RepAvgILS, while TRILS and PHILS obtain 0.05% and 0.06%, respectively. A first observation is that the diferences between overall total scores (TS) increase the more infeasible plans are produced (VTW) by AvgILS. The reason is that our approaches produce only feasible plans and therefore manage to gain additional profit in these cases (infeasible solutions contribute zero profit to the TS). This is also reflected in the columns TRS and ARS, the total and average repaired scores for those infeasible solutions. For the infeasible plans the improvement with respect to RepAvgILS is as follows: SILS achieves 6.76% improvement whereas PHILS 6.06%, and TRILS 5.12%.
With delays (right tables). Interestingly, all approaches generate trip plans with higher scores because the number of infeasible trip plans decreases. The reason for this is that delays are simulated for randomly picked units under independent assumptions. Therefore when a user travels to a POI more options, namely the delayed units, are available to reach it, which might reduce the travel time. PHILS performs the best, with an improvement in the overall score of 0.05% wrt. RepAvgILS. This is followed by SILS (0.04%) and TRILS (0.035%). For the infeasible plans the improvement with respect to RepAvgILS is as follows: PHILS achieves a 6.9% improvement whereas SILS 6.6%, and TRILS 4.95%. This shows the robustness of our approaches in the presence of delays.
As expected RepAvgILS was the fastest ILS-based heuristic due to its simple repairing strategy, whereas PHILS required the longest time (26.12% slower) to find the final solution. However, the execution times of both SILS and TRILS, approx. 1.2% and 1.5% slower, respectively, are very close to that of RepAvgILS. In any case our approaches are able to generate a plan in under 15ms (on average) which is a nice achievement considering this includes the adjustment time and interaction with the route planner.
Conclusion. SILS, TRILS and PHILS manage to produce only feasible plans thanks to the novel interactive aspect, i.e. the two-way lfow of information between the core approach, which assembles the solution, and the route planner. Our results also show that more infeasible plans are produced when the time budget is large or the visit ends late (visits are closer to the closing times of all POIs). 7
We presented, SILS, TRILS and PHILS, three novel approaches to solve the tourist trip design problem with travel instructions (TTDPTI). This problem is an extension of the TTDP which, in addition T 6 1 5 4 5 2 V 12 60 36 12 58 35 5 ,3 1 4 4 5 2 2 7 5 8 6 7 2 8 2 0 : 6 1 0 0 : 2 0 : 8 0 0 0 0 : 0 2 1 0 0 : 2 0 0 : 2 1 1 1 8 9 5 9 3 5 ,1 ,7 ,5
6 0 4 8 9 4 6 8 S 0 R 0 2 T ,9 ,8 6 0 , 7 3 3 , 2 ,2 0 0 6
3 5 9 8 1 9 7 4 0 4 1 2 1 4
8 ,2 , 1 5 9 12 8 R ,5 ,7 , 3 ,5 ,
0 ,
A 6 8 1 6 8 10 h t i w
S S R 0 , L I A S 9 8 3 , 4 1 9 7 4 9 r 6 ,0 ,9 ,4 ,6
e 5 ,5 3
, 0 8 8 s t m i p x e S g v A R e o s t l u s e R : 2 n e m i r e S L I S h t f o s t l u s e R e l s y a l h t i w T y a l h t i w R T 1 5 9 12 3 1 9 4 9 7 ,5 ,0 ,2 ,0
8 2 ,6 , 5 1 , 6 ,
7 1 2 ,8
8 S ,8 , A 0 7 4 1 1 8 8 7 6 ,1 ,9 ,4 ,7 4 0
7 2 i 5 6 8 5 6 8 r
e S 9 T 9 9 7 6 7 , , , 0 3 y a l ed PR ,52 ,73 ,08 ,8 6 8
3 ,5 ,4 t A 6 8 1 6 8 01 u o P h t i w S ,1 S
R 4 ,9 0 3 , L A 2 7 9 4 7 8 I H 6 8 6 , 7 ,5 7 8 8 ,6 0 7 7 6 , 7
7 , S ,2 ,
6 R 8 2 59 49 1 T 4 77 29 4 2 0 7 4 4
6 3 3 ,
8 3 0 tD ,57 ,99 ,27 ,87 ,97 ,13 S 8 7 7 8 7 7
4 9 S ,8 ,5 ,1 A 0 7 4 , 5 6 1 9 ,4 ,8 0 7 2 5 6 8 5 6 8 ,5 , 5 4 2 5 ,
6 , 1 , 9 0 8 ,9 2 1 m i t I O P e h t f o t u o e m i t i g n t i s i v e n o t s a e l t a e v a h h c i h w s t s e u q e r f o r e b m u N . ) W T V ( w o . d n x i a w e m t mt i n t i
a ’s r I t
s O n P o
c a f eg o d on bu i t e a m l i o t i e m o r f a p e R A . s n a l p i v O . ) S R T ( e r o c S r i a p e R l a t o T . . e . i , d e n a t i b o e r o c s e g a r e v a e r o c S e g a r e v A . s t e s u q e r s n a l p t i s i v l l a r o f e r o c s l l a r e v O . ) S T ( e r a A d n a P R A , o A c .
S : S S R C I C 6 1 . y l a t I , o m o C , 7 1 0 2 , h t 7 2 t s u g u A , 7 1 0 2 to producing a visit plan (i.e. the sequence of POIs to visit in a city), also produces a travel plan with instructions on how to reach those attractions using public transportation. The novelty of these approaches lies in the way the visit plan is dynamically adjusted according to real travel times. While average travel times are still used in the computation for eficiency, the solution is eventually adjusted with the information provided by a route planner. If the adjustment leads to an infeasible plan each approach takes diferent countermeasures to repair it. The search for an optimal solution continues on top of the repaired plan. This makes it possible to not only return feasible plans (without violations of the POI’s time windows) without sacrificing profit, but also to return both visit and travel times in real-time. Moreover, our state-of-the-art route planner is able to model a large variety of events related to public transportation, such as walking times (between stations, to a station to take a bus, etc.), changing vehicles (transfers), but especially to model delays of transportation units. To the best of our knowledge, no previous approach was able to provide travel instructions for the visit plans at this level of realism.
As we showed in our experiments, SILS, TRILS and PHILS are at comparable performance levels in terms of collected profit, while all approaches manage to outperform ILS-heuristics based on estimated travel times even after a repair. Moreover even PHILS, which required the longest execution time, is able to produce plans in real-time.
In the future we would like to extend our approach by modeling further constraints and events. In addition we would like to focus more on the personalization aspect of the TRS. Finally, our approaches could be used to model dynamic changes, too, thanks to the ability to deliver fast plans. If the user deviates from the visit plan, e.g. if she enjoys staying at one place and prolongs the visit, a new plan has to be recomputed together with the travel plans. Our approaches seem to be a good fit for this problem too.