In this work, we propose an eficient deterministic method based on Expectation-Maximization (EM) to solve the challenging problem of the tourist trip design or Personalized Itinerary Recommendation (PIR) with POI categories. PIR aims to recommend a personalized tour that consists of a sequence of Points of Interest (POIs), which maximizes user satisfaction and adheres to user time budget constraints. Additionally, POIs are divided into categories, so that the tourist is able to provide minimum/maximum limits on the number of POIs belonging to each category. This framework mainly focuses on the POIs sequence selection problem exploiting the personalized POI recommendations provided by a recommender system. The proposed method sequentially solves the PIR problem by providing in each step the POI that is expected to maximize a suitable objective function, taking into account user satisfaction, user time budget, POIs opening hours, POIs category constraints and spatial constraints (e.g. start and end point, POIs locations, etc). The proposed system has been also applied in a version with multiple collaborating instances that improves the exploration of the search space and increases the score of the objective function. The proposed system is also integrated with a complete tourist trip design system. Experimental results and comparisons to existing methods on a large number of synthetic and real datasets demonstrate the high performance, robustness and the computational eficiency of the proposed system.
of previous user preferences [
Collaborative
nEvelop-O LGOBE
https://sites.google.com/site/costaspanagiotakis/ (C. Panagiotakis); http://users.ics.forth.gr/~eva/ (E. Daskalaki);
users for items [
Recommender systems have been also successfully applied to an important and complex
task related to tourists that concerns the planning and scheduling of tour itineraries, which
comprise a sequence of Points-of-Interest (POIs) based on the unique preferences of each tourist
[
The tourist trip design problem or personalized itinerary recommendation (PIR) problem is
an extension of the orienteering problem applied to tourism. In the orienteering problem, a
set of vertices is given, each with a score. The goal is to determine a path, limited in length,
that visits some vertices and maximises the sum of the collected scores [
Therefore, in this work, we study the PIR problem. In order to concentrate on the POIs
sequence selection problem, we assume that the gained user satisfaction per visited POI is
provided to the system (e.g. predicted by a Recommender System based on user preferences). So,
the main goal of this work is to provide a sequence of POIs that maximize user satisfaction under
several given constraints such as user time budget, user defined POI categories, POI opening
hours and spatial constraints (e.g. start and end user points, POIs locations, etc). An advantage
of the proposed method is that it can be easily adapted to the user preference of POIs which is
provided as an input to the proposed method, while other systems try to predict them based on
historical data of user itineraries. Additionally, although the tourist is interested in visiting as
many POIs as possible according to her/his preferences, she/he may wish to avoid visiting too
many POIs that have similar characteristics (e.g., restaurants, art galleries). Similarly to [
Figure 1 depicts an instance of a personalized tour itinerary, where the user starts at point 2 and ends at point 8. In this example, a solution of the proposed framework is plotted with red color, that consists of five POIs (2, 15, 5, 14, 6) which provide high user satisfaction. The category of each POI is shown in parenthesis, while the minimum and maximum limits per category are depicted on the bottom left of Fig. 1(b). It holds that six out of eight user defined POI category
User
Preferences User Time
Budget User Start and
End points POIs categories constraints POIs Opening
Hours POIs Travel
Times (a)
Recommender
System
POIs Sa sfac on
I nerary Recommenda on
Method I nerary (b) (c) constraints (c2,c3,c4,c5,c6 and c7) are also satisfied. The size and the color of a POI correspond to the duration of the visit and the gained user satisfaction, respectively. Additionally, all graph edges are assigned a travelling time. According to the proposed timetable (see Fig. 1(c)), the tour start at 10:00 and ends at 13:46. Therefore, it holds that the selected tour itinerary passes from POIs that provide high user satisfaction, while it respects the user time budget (10:00 to 14:00).
The main contribution of this work concerns the problem formulation of PIR with POI categories based on the maximization of an appropriate objective function, as well as a proposed high performance and computationally eficient deterministic method. Another significant contribution of the proposed system is its ability to control the trade of between the exploration of the search space and its computational cost by changing the number of collaborating system instances. For each visited POI, the proposed objective function takes into account the user satisfaction, POI’s visit duration and its category constraints, as well as the number of already visited POIs, in order to get higher values as the number of POIs increases. In our work, the gained user satisfaction is also related to the POI visit duration making more realistic the proposed objective function. Moreover, we show the high performance and computational eficiency of the proposed framework that is based on an EM schema. Another contribution of the proposed method concerns its applicability, as it can be easily combined with any recommender system (see Figure 1(a) and the the integration of the proposed system to a tourist trip design system of Section 4.3). An additional contribution of this work concerns the creation of a large synthetic public dataset used to test the Personalized Itinerary Recommendation systems under diferent values of the problem parameters.
the itinerary recommendation problem. In Section 3, we present the main problem formulation of itinerary recommendation that we study in this paper. Section 4 describes the proposed itinerary recommendation method. Section 5 describes the experimental setup along with the obtained results. Finally, conclusions and future research directions are provided in Section 6.
In recent years, with the popularity and explosive growth of location-based social networks
and smartphones, demographics, user preferences, and space-time information and ratings of
itineraries for POIs visited by tourists, are easily collected providing rich datasets that can be
used to infer user interests. This huge information collection has been exploited by PIR systems,
thus improving the quality of personalized recommendations. Therefore, a large number of
diferent techniques appear in the literature for itinerary recommendation [
in cities based on categorized POIs from Wikipedia and albums of geo-referenced photos from Flickr. It aims to plan a tour comprising POIs that maximize tourists’ personal interests while adhering to a specific visiting time budget. The PersTour algorithm [ 16] considers both POIs’ popularity and user preferences to recommend suitable POIs to visit and the amount of time to spend at each POI. PersTour personalize a POI’s visit duration based on the relative interest of individual users, instead of relying on the average visit duration of a POI for all users. PersTour introduces two adaptive weighting methods to automatically determine the emphasis on a POI’s popularity and the user interest preferences.
The method proposed in [17] recommends emotionally pleasing tours in a city. To quantify the extent to which urban locations are pleasant, data from a crowd-sourcing platform have been used. The construction of the best itinerary from source to destination is performed in four steps:
exploration, the path with the lowest (best) average rank is stored.
set of high-ranked tourist attractions and restaurants with respect to several constraints. GA uses natural selection and genetic principles to solve the optimization problem of itinerary recommendation. It uses multistage processing such as initialization, selection, crossover, and mutation to generate and refine the candidate solution.
AGAM [19] is another genetic algorithm with crossover and mutation probabilities for this problem. In this algorithm, diferent weights are allocated to every factor to generate a PIR for better results that meets many kinds of tourists’ preferences. In the performance evaluation section, the experimental results of the proposed method are compared to [17] and [18]. UTP [20] recommends interesting locations in the itineraries that similar tourists have traveled to before, based on a collaborative filtering algorithm with time preferences. The DCC-PersIRE method [10] solves the PIR problem by integrating user-POI visits, POI textual information and
search based algorithm has been proposed to solve the PIR problem. In a more recent work, the PWP algorithm [21] recommends multiple itineraries based on the interests of visitors, the popularity and the cost of itineraries. PWP efectively optimizes interest, popularity and cost during the selection of each itinerary using the NSGA-II approach via genetic operators. An itinerary list is generated by comparing local and global tourists.
Recently, extra practical tourism constraints have been included in the tourist trip design
problem such as mandatory visits, limits on the number of locations of each category, as well as
in which order selected locations are visited [
Group itinerary recommendation methods provide itineraries with a balance between group preferences and the given temporal and spatial constraints. AMT-IRE [22] is designed to schedule visits to POIs of interest based on the overall group preferences provided in the form of a sequence with time constraints. The proposed AMT model jointly calculates group member preferences and overall group preferences via the attention mechanism. The predicted overall group preferences are used in a variant of the orienteering problem and an iterated local searchbased algorithm recommends group itineraries. Another group itinerary recommendation methods is proposed in [23], that receives a set of must-visit and preferred points of interest from each tourist and forms multi-day tours that cover all must-visit points. The proposed framework attempts to maximize fairness among group members. The problem of next POI recommendation considers the sequential information of users’ check-ins in addition to users’ preferences. In [24], the Spatio-Temporal Gated Network has been proposed to model personalized sequential patterns for users’ long and short term preferences in the next POI recommendation. In [25], the proposed system, that is also based on a neural network architecture, has been applied to recommend the next personalized travel destinations to airlines’ customers.
and simultaneously we present the stepping-stones where our developments are based on. We start below by defining the personalised itinerary recommendation problem.
(e.g. city map) with POIs = { 1, ...., }. Let be the traveling time matrix ( × ) of the pair-wise distances for all POI1 pairs. Let be the set of POI categories (e.g. restaurant, museum, beach, shops etc.). For each category ∈ , the minimum ( ) and the maximum ( preferable number of POIs belonging to category , according to user preferences is also given. )
locations (POIs) of the tour. Hereafter, for simplicity reasons, we will assume that 1 ≠ , however, our method is able to work even if the starting and ending locations coincide ( 1 = ).
and the time budget (duration) of the tour. This means that the tour itinerary should end at +
or earlier. defines the gained user satisfaction per hour by the visit of POI . In our framework, is computed ofline e.g. by a recommender system based on user preferences or other features (travel, history, etc.) as depicted in Figure 1(a).
In the definition of itinerary , we have included the visited POIs as well as the corresponding temporal information. Therefore, an itinerary is defined by a sequence of triples, where each triple ( , , ) is comprised by the visited POI with the corresponding arrival and departure times . The case that a user can pass from a POI without visiting it, is also supported, which means that = . Thus, we denote by () , the sequence of visited triples ( , , ) of itinerary , for which it holds that > . Therefore, according to the itinerary recommendation problem definition, itinerary should meet the following constrains: 1. ∀ ∶ ∈ () it holds that [ , ] ⊆ . This means that the corresponding POI should be open during the visit. 2. ∀ ∶ ∈ (), ≥ 2
it holds that the arrival time is given by = −1 + −1 , .
1 can be computed by applied Johnson’s algorithm on the graph of POIs in ( 2), under the assumption that the number of graph edges is ()
which is usually true for city maps. 3. The itinerary should start at POI 1, meaning that the first triple of should be (1) = ( 1, 1, 1). 4. 1 = , meaning that the tour itinerary starting time is the same with the arrival time at 1. 5. The itinerary should end at POI, meaning that the last triple of should be the (||) = ( , , ).
Additionally, the number of categories ∈ maximized: satisfying the following condition should be , where (()) work. 3.1. Evaluating an itinerary
is the category of () . Table 1 summarizes the notation used throughout this Solving the itinerary recommendation problem amounts to finding the legal (i.e. satisfying the pre-mentioned problem constrains) itinerary ∗ that maximizes an appropriately defined objective function . In notation, ∗ = ∈ (), where is the set of legal itineraries according to the problem constrains.
In order to assess this itinerary, we propose an objective function that has the following properties: • The main goal of the objective function is to achieve the highest user satisfaction, while respecting the given problem constraints. • For each category ( ∈ ), we take into account the corresponding constraint (see Eq. 1), so that the largest number of constraints satisfied, the more preferable an itinerary . • For each POI ( ) of , we take into account the corresponding gained user satisfaction per hour that is multiplied by the visit duration − . Intuitively, the larger gained satisfaction, the more preferable the itinerary . • The number of visited points | ()| also increases the value of the objective function. • The value of the objective function for legal itineraries is non-negative.
• The value of the objective function for non legal itineraries is set to −∞. The aforementioned properties are well captured by the objective function () ≤ 1 follows: defined as () = ∑(())=
⎧ ⎪
1, ⎪⎨ ⎩ ∑(())= 1 1 , if ∑(())= , if ∑(())= 1 < if ≤ ∑(())= 1 > 1 ≤ (1) (2) (3) () = () = ∑ () ∈ (1 + (| ()|)) ⋅ ∑( , , )∈ ⋅ ( − )
(1 + ()) ⋅ () = { ()+ ()
||+1 −∞ if ∈ if ∉ When is a legal itinerary, () is defined by the sum of () and () .
1() = 1 () = ∈∶ ∈∶ ∑ ∑ ∑(())= ∑(())= < < () 1 • () • ()
sums the gained user satisfaction multiplied by the corresponding visit duration (see Eq. 5). The term (1+(|()|)) 1+()
≤ 1 is used to slightly increase the value of the objective function as the the number of visited points | ()| increases.
captures the satisfied categories’ constraints by counting the number of categories satisfying the corresponding constraints (second branch of () ). For those categories that don’t satisfy the categories’ constraints, it holds that – ∑ – ∑ (())= (())= 1 < 1 > (number of categories with POIs less than (number of categories with POIs more than ) or ), category limit or
(see Eq. 3). two terms are included. Both terms increase as ∑(())=
() ≤ 1
.
In our implementation, an itinerary that satisfies more POIs categories constraints ( () ) is more preferable, even if it yields less gained user satisfaction ( () ). Therefore, () is influenced by rather than the () . This is also verified by the fact that () ≤ || and According to the proposed methodology, the following function () that expresses the expected value of the objective function () is maximized. () is defined by the sum the of the excepted values of () and () ( () + extra included POIs from these categories, are only expected to increase the value of (.) . The expected value of 1() is computed under the assumption that it linearly increases with the duration of itinerary respecting the upper limit: 1() ≤ 1 to the number of categories that satisfy the constraint ∑ (())= () (see Eq. 10). 1
() is equal 1 < (see Eq.9).
(4) (5) (6) (7) (8) () = () − () = ⋅ () =
− 1 () = () +
The computational cost of the exhaustive method for determining the optimal itinerary by maximizing the objective function defined in Eq. 6 is ( ⋅ ( − 2)! ⋅ 2 there exist 2−2 diferent itineraries in a map of − 2 POIs (assuming the first and last POIs are given). Factor ( − 2)! results from the number of permutations, since the order of POIs should also be considered. The evaluation of the objective function that costs (| ()|) = () is included in term ( − 1)! . This is too costly. Hereafter, we capitalize on the properties and the structure of the problem to propose an algorithm that provides an almost optimal solution in −2 ) = (( − 1)! ⋅ 2 ), since polynomial time. 4. Personalized itinerary recommendation 4.1. PIREM algorithm
The PIREM algorithm: In this work, we propose an iterative optimization method, described in Algorithm 1, that sub-optimally solves the problem in ( ⋅
of given POIs, under the assumption that itinerary length increases linearly with , as shown in our experimental results. According to the proposed method, the itinerary recommendation problem is solved by sequentially adding the most suitable unvisited POI in the current itinerary, the one that maximizes the expected value of the objective function, as this is defined in Eq. ( 12).
, , , , ∈ {1, ..., } , , , ∈ as described in Section 3. The goal of the proposed method is to compute a solution for the PIR problem that is denoted by ∗ in Algorithm 1. The first four lines of Algorithm 1 is the initialization phase. Variable that counts the number of changes in each main iteration of the method is set to zero, as well as the current optimal value of the objective function . The set of the indexes of visited POI is initialized to the empty set, while the first triplet of ∗ is set equal to {( 1, , )}
, according to the problem definition.
In the main loop of the proposed PIREM method (lines 5-26 of Algorithm 1), we get the set of the indexes of all unvisited POIs (line 6 of algorithm 1), that will be used to find the next visited POI. Additionally, we set = 0 . In the computation of , we ignore the ending POI ( = {1, ..., − 1} − ), since this is definitely inserted after the last visited POI ∗ ( ∗(||)) at the , , , , ∈ {1, ..., } , , , ∈ .
26 until ≠ 0 ∨ = ∅ ; 27 ( , , ) = ∗(||) 28 if + (, ) + ≤ +
then 29 31 32 30 else 33 end ∗ = ∗ ∪ {( , + (, ),
+ (, ) + )} ∗ = ∗∪ {( , + (, ), + (, ))} input : , , , , output : ∗. 1 = 0 2 = ∅ end of the method (lines 27-32 of algorithm 1). This loop terminates when no changes take place in the main loop or the set is empty.
Subsequently, in the second loop (lines 8-21 of Algorithm 1), we evaluate whether the insertion of each unvisited POI , ∈
at the position of the current optimal itinerary ∗ (see the third for loop of line 9) is legal according to the problem constraints and whether it improves the current optimal value of
(expected value of the objective function). If both of the following statements are true, it means that the insertion the insertion of at position of is valid (see lines 10-11 of Algorithm 1):
2. Tour ends at time + or earlier.
(see lines 13-18). The current optimal itinerary ∗ and set are updated in this loop (see lines and we update 22-25), so that the most suitable POI is inserted at the most suitable position of ∗. 4.2. M-PIREM algorithm The resulting solution of PIREM may land on a local minima of the objective function due to the sequential optimization. Thus, we propose an extended version with multiple ( ) collaborating instances of PIREM, called M-PIREM to improve the PIREM solution via a better exploration of the search space. Parameter controls the trade of between search space exploration and computational cost, by changing the number of collaborating instances. Hereafter, the M-PIREM algorithm is presented.
1. Let be the set of collaborating itineraries (instances of PIREM ). In the initialization step, the set of visited POIs of the itinerraries , {}, ∈ {1, ..., } is set to the empty set, while the first triplet of each itinerary is set equal to {( 1, , )} , according to the problem definition.
( − = ∈ () ). Then, we apply an iteration of the main loop of the PIREM method, to get an new valid itinerary ( +) that does not exist in 2.
value, by the new one ( +). This process is repeated until the expected value of the objective function cannot be further improved.
solutions in , in order to better avoid local minima. The computational cost of this method is
( ⋅ ⋅ 3). It holds that the solutions provided by M-PIREM are better or equivalent to the
corresponding solutions of PIREM. In our experiments, we used = 32 .
4.3. Integration with a tourist trip design system
The proposed system is integrated with the Visit Planner App (Fig. 2(a)) that is a complete
tourist trip design system (mobile app). According to Visit Planner App, the tourist gives her/his
preferences by providing ratings on several POIs (Fig. 2(b)), so that a recommender system
([
2If the case itinerary − is not a new itinerary, that does not exist in set , we select the itinerary from with the second lowest expected value and so on.
(a) (b) (c) (d) (e)
5.1. Synthetic and Real Datasets
(16 diferent experiments per dataset) to study the performance and computational eficiency of the proposed methods and other methods from the literature under several problem parameters.
Each of the 64 synthetic datasets is generated by adding POIs at random positions on a 2D-map, where ∈ {32, 64, 96, 128} . The roads (edges) of each map are generated as follows, we sequentially connect the closest POIs according to the following rule: An edge is created if the distance between its middle point and the rest edges exceeds a predefined threshold in order not to create edges that are very close to each other. This is also almost true on real maps. In order to create the 64 synthetic datasets, we have created 16 maps for every value of , following the aforementioned procedure. Subsequently, we set the parameters for each POI of each synthetic dataset. Parameters and are selected randomly from {0.25, 0.5, 0.75, 1} and {[9:00, 24:00], [12:00, 21:00] , [9:00, 14:00], [14:00, 24:00], [9:00, 14:00] ∪ [17:00, 21:00]}, respectively.
the starting and ending locations of the tour from the available POIs. For each setup, we set
the starting time of tour at 9:00 ( = 9:00), while the time budget is randomly selected from
{5, 6, 7, 8, 9}. The value of parameter is randomly selected in [
Vienna, Budapest and Delhi cities presented in [16]. Vienna, Budapest and Delhi datasets comprise a set of users and their visits to = 28 , = 38 and = 23 POIs, respectively. The real datasets comprise a set of users and their visits to POIs naturally clustered into 6-8 diferent POI categories based on geo-tagged YFCC100M Flickr photos. For the real dataset, we create 256 diferent experimental setups following the same procedure applied on the synthetic datasets (see previous paragraph). The value of parameter of a POI is given by the ratio of the POI visits according to the data provided by [16].
In synthetic datasets, we used 8 diferent POI categories, thus, the category of each POI of a synthetic dataset is randomly selected from a predefined set of eight values. Additionally, we used four diferent strategies for the and parameter setting. Therefore, the experimental setups of each synthetic and real dataset, are equally divided into the following four classes determined by parameters
and
and extended the two diferent setups (Tight and Flexible) proposed in [
is randomly selected from the set {0, 1, 2} and
= . This class simulates tight cases, where the user want to visit a specific number of POIs according to their categories. 2. Semi-flexible : For each ∈ , it holds that and = {1, }. This class simulates semi-flexible cases, where the user want to visit specific number of POIs according to their categories with the flexibility that each category can be visited ≥ 1 and 0 ≤ − ≤ 1 times. 3. Flexible: For each ∈ , it holds that
is randomly selected from the set {0, 1, 2} and
= lfexible cases, where it holds that 1 ≤ − + , where is randomly selected from the set {1, 2, 3}. This class simulates is randomly selected from the set {0, 1, 2}
in Section 4. In order to show the importance of the EM criterion, we have implemented a variant of the proposed PIREM method that maximizes the value of objective function () instead of () . This variant is called PIRM.
the following PIR methods [17, 18]. Both methods are described in Section 2. Hereafter, the method proposed in [17] that is based on shortest paths is called SPM and the genetic algorithm proposed in [18] is called GA. Both methods have been modified to maximize the proposed objective function () .
jective function ()
that measures the quality (user satisfaction and POIs categories constraints satisfaction) of the recommended itineraries according to the problem definition (see Section 3).
4. No Categories: constraints.
= 0 and 5.2. Baseline algorithms
= ∞. This class simulates cases without POIs categories M-PIREM PIREM PIRM SPM GA 0.889 0.870 0.910 0.888 The average values of objective function F for the five methods on the synthetic datasets for diferent values of and class of POIs categories constraints. The average values of Precision (left part) and objective function F (right part) for the five methods on the Vienna, Budapest and Delhi datasets for diferent values of class of POIs categories constraints. their execution times. All the analysis has been done using MATLAB 2020a on an Intel i7 core 3.20GHz with 32 GB RAM3. 5.3. Comparisons
size and class of POI category constraints. PIREM also shows high performance results since it outperforms all other methods under any map size and class of POI category constraints.
are obtained by SPM and PIRM. The methods’ ranking obtained for each value of and class of
Figure 3 shows the average precision ( ) of each method on the synthetic datasets for diferent values of (Fig. 3(a)), POI category constraints classes (Fig. 3(b)) and time budget (Fig. 3(c)).
yields the best itinerary according to the objective function () criterion over all methods. The
M-PIREM PIREM PIRM SPM GA results of Fig. 3, concerning the ranking of the methods, agree in most cases with the results of Table 2. Figure 3 shows that the proposed M-PIREM method clearly outperforms all the methods, having average precision more than 89.5% under any value of , POI category constraint class and time budget. The average precision of M-PIREM and PIREM for all datasets is 94.3% and
Table 3 presents the average values of precision Pr (left part) and objective function F (right part) for the five methods on the three real datasets (Vienna, Budapest and Delhi) for diferent values of class of POIs categories constraints. The results agree with the corresponding results on the synthetic datasets (see Table 2 and Fig. 3). It holds that the proposed M-PIREM method clearly outperforms all methods under dataset, criterion and class of POI category constraints.
space for simple problem instances (low values of ). Additionally, the outperformance of the proposed method M-PIREM compared to the rest systems slightly increases for more complex problem instances under real (see Budapest dataset on Table 3) and synthetic datasets (see = 128 on Table 2). 5.4. Evaluation of the proposed methods
(see Fig. 3, Table 2 and 3). In all experiments performed, M-PIREM and PIREM clearly outperform the PIRM method. According to the results of Table 2, it holds that on average, the user satisfaction, as measured by the proposed objective function, is about 17% higher when the EM criterion is used.
Figure 4 presents several results for the proposed top performing method M-PIREM on the synthetic and Vienna datasets. Vienna dataset is selected since it better represents the real datasets according to dataset size (complexity) criterion. In Figs. 4(a) and 4(c), the average values of objective function F for the M-PIREM method under diferent values of are depicted on the synthetic and Vienna datasets, respectively. As expected, the higher the value of , the higher the obtained user satisfaction. For the synthetic datasets, when > 32 , the improvement of the obtained solutions is not so critical, thus the selection of parameter = 32 ofers a good balance for the trade of between search space exploration and computational cost, which increases linearly with . The Vienna dataset is less complex ( = 28) , thus when > 24 , the
POIs for diferent values of time budget for the M-PIREM method (M = 32) for Vienna and synthetic datasets, respectively. As expected, the itinerary length increases linearly with .
standard deviation = 2.1 . For the less complex Vienna dataset, the average itinerary length over the 256 experiments is 6.1 with standard deviation = 1.2 . 5.5. Computational eficiency Due to the low computational cost of the proposed methods (( ⋅ 3) and ( ⋅ ⋅ 3)), they have higher computational eficiency compared to SPM and GA. Over all synthetic datasets, it holds that on average M-PIREM is about 5.5 and 140 times faster than SPM and GA, respectively. Concerning PIREM, it appears to be about 322 and 8120 times faster than SPM and GA, respectively. The average execution time over all synthetic datasets of M-PIREM with M = 32 is
In this work, the challenging problem of PIR with POI categories has been solved by a successive selection of POIs approach based on EM. We focus on the POIs sequence selection problem exploiting the personalized POI recommendations provided by a recommender system. More specifically, we propose the PIREM method that sequentially selects unvisited POIs taking into account user interests, user time budget and POI opening hours, spatial constraints and POIs categories. The proposed M-PIREM method with multiple collaborating instances improves the obtained results of PIREM. The number of instances parameter of the M-PIREM method balances the trade of the search space exploration and the computational cost.
The proposed system has been successfully integrated with the Visit Planner App, a complete tourist trip design system. Additionally, it has been successfully applied on synthetic and real datasets providing high performance results by maximizing user satisfaction, respecting user defined POIs categories constraints and adhering to user time budget. We have performed 1024 experiments on 64 diferent synthetic maps of POIs and 256 experiments on three real datasets, where the problem parameters (user time budget, number of POIs, POIs opening hours and spatial constraints, POIs categories, etc.) vary. All the experiments demonstrate the proposed framework outperforms various state-of-the-art baselines on solution quality as well as computational eficiency. In the future work, we focus on the further development and the evaluation of the Visit Planner App. Additionally, we will study the problem of group itinerary recommendation [22], that can be defined as an extension of the PIR according to the proposed problem formulation.
the Operational Program Competitiveness, Entrepreneurship and Innovation, under the call
[10] L. Chen, L. Zhang, S. Cao, Z. Wu, J. Cao, Personalized itinerary recommendation: Deep and collaborative learning with textual information, Expert Systems with Applications 144 (2020). doi:10.1016/j.eswa.2019.113070. [11] S. Markaki, C. Panagiotakis, D. Lasthiotaki, Image sorting via a reduction in travelling salesman problem, IET Image Processing 14 (2020) 31–39. [12] G. Gutin, A. P. Punnen, The traveling salesman problem and its variations, volume 12,
[13] P. Vansteenwegen, W. Soufriau, G. V. Berghe, D. Van Oudheusden, Iterated local search for the team orienteering problem with time windows, Computers & Operations Research 36 (2009) 3281–3290. [14] M. De Choudhury, M. Feldman, S. Amer-Yahia, N. Golbandi, R. Lempel, C. Yu, Automatic construction of travel itineraries using social breadcrumbs, in: Proceedings of the 21st ACM Conference on Hypertext and Hypermedia, 2010, pp. 35–44. [15] I. R. Brilhante, J. A. Macedo, F. M. Nardini, R. Perego, C. Renso, On planning sightseeing tours with tripbuilder, Information Processing & Management 51 (2015) 1–15. [16] K. H. Lim, J. Chan, C. Leckie, S. Karunasekera, Personalized trip recommendation for tourists based on user interests, points of interest visit durations and visit recency, Knowledge and Information Systems 54 (2018) 375–406. doi:10.1007/s10115-017-1056-y. [17] D. Quercia, R. Schifanella, L. M. Aiello, The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city, in: Proceedings of the 25th ACM conference on Hypertext and social media, 2014, pp. 116–125. [18] B. S. Wibowo, M. Handayani, A genetic algorithm for generating travel itinerary recommendation with restaurant selection, in: 2018 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), IEEE, 2018, pp. 427–431. [19] P. Yochum, L. Chang, T. Gu, M. Zhu, An Adaptive Genetic Algorithm for Personalized Itinerary Planning, IEEE Access 8 (2020) 88147–88157. doi:10.1109/ACCESS.2020. 2990916. [20] Y. L. Hsueh, H. M. Huang, Personalized itinerary recommendation with time constraints using GPS datasets, Knowledge and Information Systems 60 (2019) 523–544. doi:10.1007/ s10115-018-1217-7. [21] J. L. Sarkar, A. Majumder, A new point-of-interest approach based on multi-itinerary recommendation engine, Expert Systems with Applications 181 (2021) 115026. [22] L. Chen, J. Cao, H. Chen, W. Liang, H. Tao, G. Zhu, Attentive multi-task learning for group itinerary recommendation, Knowledge and Information Systems 63 (2021) 1687–1716. [23] M. Kargar, Z. Lin, A socially motivating and environmentally friendly tour recommendation framework for tourist groups, Expert Systems with Applications 180 (2021) 115083. URL: https://doi.org/10.1016/j.eswa.2021.115083. doi:10.1016/j.eswa.2021.115083. [24] P. Zhao, A. Luo, Y. Liu, F. Zhuang, J. Xu, Z. Li, V. S. Sheng, X. Zhou, Where to go next:
[25] A. Dadoun, R. Troncy, M. Defoin-Platel, G. Solano, Predicting your next trip: A knowledge graph-based multi-task learning approach for travel destination recommendation, in: 2021