Planning itineraries is a complex task for tourists. While some tourists have their favorite events and plans (e.g., places to visit, ways to travel) precisely in mind, others would like to explore multiple choices of possible events. To improve the user experiences of tourism, we develop a novel itinerary planning framework in which users directly interact with our system by editing displayed itineraries. Our idea is to collect edition-based feedback via editions by users, to estimate user preferences from the editions, and to utilize this data when generating personalized itineraries. To implement this framework, we generalize the maximum likelihood planning framework by introducing a new optimization problem to estimate transition probabilities between POIs with both historical and interaction data. To explain how the maximum likelihood itinerary planning-based method works, we report our proof-of-concept experiments aiming to provide a new perspective for interactive itinerary planning with user interaction.
Background Planning an itinerary (also called a travel plan or trajectory) is a complex task when a tourist plans a trip. Planning often involves places to visit (e.g., points-of-interests, POIs), places to stay (i.e., accommodations), how to travel between places (e.g., transportation and its mode), booking, and payments (if needed). While some tourists have their favorite places and/or plans exactly in mind, others would like to explore several choices to visit. In the literature, optimization-based methods have been studied as an important component for generating itineraries [1, 2, 3, 4]. A well-known optimization problem called the orienteering problem or its variants are often employed [5, 6]. The orienteering problem is the problem of constructing a trajectory (i.e., sequences of POIs) to maximize the benefits from the visited places under travel distances/time constraints. An important process behind the orienteering problem is how to evaluate the benefits of POIs for users. Using some objective values (e.g., an average rate or staying time of the POI) we can build traditional and common itineraries, while we can build personalized itineraries with some subjective values (e.g, a rate or staying time by a specific user ).
Related Work Integrating user preferences for places and/or itineraries with optimization when generating personalized itineraries is promising to improving the user experiences. In previous work, Choudhury et al. [2] constructed a sequence of photographic spots using mean staying times of places to reflect user preferences, and they showed that generated trajectories are comparable with those generated by professionals. Lim et al. [3] utilized estimated staying times per user as user preferences in defining an objective function of the orienteering problem, but feedback is not considered. Roy et al. studied the task of interactively planning itineraries with feedback on POIs [7]. They proposed how to model such feedback and utilize them, but a type of supported feedback is limited. Chen et al. [4] adopted a similar strategy by [7], but formally discussed how historical data of itineraries are taken into account in optimization (this framework is referred as maximum likelihood planning in the literature [8, 9]). Contributions We develop a new framework using both historical data and data collected by interaction with users. A systematic overview of our method is illustrated in Figure 1. We expect that using interaction data is promising to improve the user experience, and then generalize a type of feedback to collect richer data from users to estimate their preferences. Our method generates itineraries based on collected itineraries (Historical data in Fig. 1) and learned transition probabilities (Transition matrix in Fig.1) among point-of-interests (POIs). Further, in order to incorporate with these richer data, we try to update the learned probabilities. Note that we assume that interaction is implemented by some Web interface, and in this paper three types of operations for itineraries, Swap, Ins, and Del of POIs (illustrated in Interaction of Fig. 1), are considered. Our proposed method is a follower of both [7] and [4], but our estimation strategy using user interactions is quite new in the sense that such probabilities can be learned with collected interaction data. In our proof-of-concept experiments, we evaluate how collected interaction data afect the resulted ranked lists of itineraries under our assumption that the diversity on the resulted list is important to design itinerary planning service. We confirm that our framework generates diverse itineraries based on collected data.
Throughout this paper, [ ] = {1, 2, . . . , } for some natural number ∈ Z. Any sequence
is 1-origin. On a finite set of symbols representing POIs, a length -sequence consisting of
elements from is denoted by X = ⟨1, 2, . . . , ⟩, where ∈ for any ∈ [], and
= |X|. A sequence represents an itinerary, where a user visits 1 first, 2 second, and
in last. A direct travel from to in X is written as → ∈ X. In other words, for some
∈ [|X| − 1], it holds that = and +1 = . Further, we write ∈ X if and only if there
exists ∈ [|X|] such that = . In this paper, we naturally generalize this relation ∈ for sets
= {X1, . . . , X||} of sequences. Our framework generates a ranked list of itineraries, and a
length- list ℒ = ⟨X(
The orienteering problem is a well-studied combinatorial optimization problem [5], and it is applied to generate itineraries in the literature [2, 3, 6]. Without loss of generality, we assume that 1 ∈ is the start POI and ∈ is the goal POI when planning itineraries. The naive orienteering problem is defined on a complete graph = (, ); the vertex set represents a set of POIs, and the edge set represents travels among POIs in , and the problem involves ifnding a tour on with some objectives and constraints. We assume that , and , represent the travel time and distance from to , respectively. max is the total travel time, and the score Score() for each POI ∈ is given. We prepare decision variables {, ∈ {0, 1} | (, ) ∈ } and { ∈ Z | ∈ } as , = 1 if and only if is visited after , and represents the order when is visited. Then, the orienteering problem is formally described below.
− 1 max ∑︁ ∑︁ Score() · , , =2 =2 − 1 ∑︁ 1, = ∑︁ , = 1, =2 =1 − 1 ∑︁ , = ∑︁ , =1 =2 − 1 ∑︁ ∑︁ , , ≤ max =1 =2
1 = 1, = , 2 ≤ ≤ − + 1 ≤ ( − 1)(1 − , ) , ∈ {0, 1}, ∈ Z (∀ = 2, . . . , − 1)
(∀ = [ ] ∖ {1}) (∀, ∈ [ ] ∖ {1}) (∀, ∈ [ ]) (1a) (1b) (1c) (1d) (1e) (1f) Note that Eq. (1a) requires us to travel popular POIs in . Constraints Eq. (1b) ensure the resulted tour is valid. Constraints Eq. (1c) are for bounding the total travel time with respect to max. Constraints Eq. (1d) and Eq. (1e) are from the well-known MTZ-constraint to avoid sub-tours [10]. Constraints Eq. (1f) define variables.
To consider the distance among POIs, a multi-objective function based on Eq. (1a) can be adopted with , ∈ R:
⎛ ⎞ ⎛− 1 ⎞
m,ax − × ⎝∑︁ ∑︁ , · , ⎠ + × ⎝ ∑︁ ∑︁ Score() · , ⎠
=1 =1 =2 =2
(
Let X be a (feasible) itinerary and be the set of all feasible itineraries. In the following, we
focus on the case of |X| = for any X ∈ . The goal of maximum likelihood planning is to solve
maxX∈ Pr(X). This problem setting has been attracted much attention in the literature [4, 8,
9]. Under a first order Markov chain approximation, Pr(X) for X = ⟨1, 2, . . . , ⟩ can be
approximated as Pr(X) ≈ Pr(1)Pr(2 | 1) . . . Pr( | − 1). An implicit constraint
Pr(1 = 1) = 1 on our itinerary planning indicates the following:
arg max Pr(X) ≈ arg min
, ,
∑︁ − log Pr(+1 = | = ) ·
(
Typical optimization problems and their solvers just output an optimal solution. However,
displaying multiple solutions is preferred (e.g., on a Web) in applications. We now need to
compute (possibly) top- solutions with existing solvers, and some known methods are already
proposed [11], where we need to fix an order among decision variables and to iteratively solve
sub-problems. Instead of this procedure that requires some algorithmic design, we use the
following implementation to obtain solutions. Let ℒ() be the ordered set of solutions and
ℒ(0) = ∅. To generate a next solution (i.e., -th solution), we solve the optimization problem
under additional constraints of X ̸= X() for X() ∈ ℒ(− 1). Finally, we have an ordered set
ℒ() = {X(
We propose a new framework in which users directly interact with our system by editing displayed itineraries. Our motivation to design this framework is collecting edition-based feedback via editions by users, estimating user preferences from the editions, and using such data when generating personalized itineraries. To implement this framework, we generalize maximum likelihood planning by defining a new optimization problem to estimate transition probabilities among POIs with interaction data.
A user interacts with service interfaces (e.g., Web/mobile app). We collect edition-based feedback from the user representing his/her preference among itineraries. In our system, the following three types of editions are considered.
Swap For X = ⟨1, 2, . . . , |X|⟩, a swap of the two adjacent POIs generates a new itinerary X′ = ⟨1′, 2′, . . . , |′X|⟩, where there exists ∈ [|X|− 1] such that ′ = +1, ′+1 = and ′ = for all ′ ∈ [|X|] ∖ {, + 1}.
Insertion For X = ⟨1, 2, . . . , |X|⟩, an insertion of a new location ′ generates a new X′ = ⟨1′, 2′, . . . , |′X′|⟩ such that |X| + 1 = |X′| and for some ∈ |X| ∖ {1, } it holds that ′ ̸∈ X, X = X′ for ≤ − 1, > .
Deletion For X = ⟨1, 2, . . . , |X|⟩, a deletion of some location ′ ∈ X generates a new X′ = ⟨1′, 2′, . . . , |′X′|⟩ such that |X| − 1 = |X′| and for some ∈ |X| ∖ {1, } it holds that X = X′ for ≤ − 1, > .
Note that these are diferent from existing work (e.g., [7]) that uses feedback only for POIs.
We propose a new itinerary planning method using feedback from user editions defined in Sec. 3.1. Our idea consists of the following three steps.
1. converting the estimation task of {, },∈[] as an optimization problem,
2. optimizing our generalized optimization problem from (
Existing methods estimated , by counting historical data (e.g., historical trajectories or routes) [4, 8]. A simple method to estimate , is counting data in as , = |{→∈}| . We |{∈}| cast this estimation problem as the following optimization problem:
⃒ ⃒ 2 ^ := arg min ∑︁ ⃒⃒ , − |{ → ∈ }| ⃒⃒ subject to ∑︁ , = 1(∀ ∈ [ ]) , ⃒ |{ ∈ }| ⃒ (4) Here Eq. (4) can be solved by closed formula and a solution of Eq. (4) is denoted by ^ below. Note that other variants have been discussed [8, 9]; For example, the Laplace smoothing with > 0 is possible to estimate ^ , , and this can also included in Eq. (4). In the following, we write the term ∑︀, ⃒⃒⃒ , − |{|{→∈∈}|}| ⃒⃒⃒ 2 with a loss function data(, ).
Our key idea in this paper is generalizing Eq. (4) to consider user feedback data using penalty functions. Intuitively, we define a new objective functions like data(, ) + (, , int), where (, , int) is the penalty term related to all of the estimated probabilities , historical itinerary , and feedback data int collected from users. In practice, we propose the following methods for the three types of editions.
Swap Let us explain using examples of length-4 sequences X = ⟨1, 2, 3, 4⟩ and X′ = ⟨1, 3, 2, 4⟩. For X and X′, we encode the relation X ≺ X′ by Pr() < Pr(′). With our approximation, we have 1,2 2,3 3,4 < 1,3 3,2 2,4 . Then, we adopt a loss term swap (1,2 2,3 3,4 − 1,3 3,2 2,4 ) for each 4tuple (1, 2, 3, 4), and add this term to our learning problem in Eq. (4) (see also Swap in Fig. 1).
Insertion For two example length-3 and 4 itineraries X = ⟨1, 2, 3⟩ and X′ = ⟨1, 2, 4, 3⟩, the insertion is encoded by Pr(X) ≤ Pr(′). Similarly, we should have 2,3 ≤ 2,4 4,3 , and a loss function ins is adopted as a penalty term (see also Ins in Fig. 1).
Deletion In contrast, for two example length-4 and 3 itineraries X = ⟨1, 2, 3, 4⟩ and
X′ = ⟨1, 3, 4⟩, we can use a loss function del as well (see also Del in Fig. 1).
In summary, we can collect datasets int by designing interfaces, and data like the above example (1, 2, 3, 4) for Swap are stored to modify the transition probability , . Here we define a new objective function to estimate , using both and int := swap ⊔ins ⊔del as follows.
:= × data(, ) + 1 × + 2 ×
∑︁ (2,3,4)∈ins
∑︁ (1,2,3,4)∈swap ins(2, 3, 4) + 3 × swap(1, 2, 3, 4)
∑︁ (1,2,3)∈del del(1, 2, 3).
(5) We write ˜ := arg min ( ; , 1, 2, 3) subject to ∑︀ , = 1 for all ∈ [ ].
After computing Eq. (5), we obtain ˜ instead of ^ from Eq. (4), where we expect that ˜ can reflect all interaction information from int by soft constraints. We then could obtain diferent itineraries (e.g., top- itineraries) by using ˜ rather than those obtained by ^ .
We explain our framework using toy examples. Let us prepare = 10 synthetic locations and generate , for , ∈ [ ] randomly with , = 0. For our loss function, we adopt the (a) Random , (b) Modified ˜ , (c) Diferences
˜ −
→ ˜
neg (
Frobenius norm for data and the tanh function for swap in Eq. (5), and explain our proposed method works as we expected for Swap operation as an example.
We first prepare a random transition matrix as shown in Fig. 2a. We randomly select 10 tuples (1, 2, 3, 4) that violates the Swap condition to build swap. Here, (1, 2, 3, 4) is neg if 1,2 2,3 3,4 < 1,3 3,2 2,4 , and pos otherwise. We assume that a user says ⟨1, 2, 3, 4⟩ ≺ ⟨ 1, 3, 2, 4⟩. Using parameters = 0.25, 1 = 16, 2 = 3 = 0.0, we compute a modified matrix ˜ (as illustrated in Fig. 2b. − ˜ is also shown in Fig. 2c).
In results, we have 2, 349 neg and 2, 691 pos tuples by (i.e., total 10P4 = 5, 040 tuples), and 2, 518 neg and 2, 522 pos tuples in ˜ , respectively. Out of 2, 349 neg tuples by , 1, 988 tuples remain neg, and 361 tuples become pos. Similarly, out of 2, 691 pos tuples by , 530 tuples become neg, while 2, 161 tuples are pos as well, as summarized in Fig. 2d. For swap, ˜ satisfies the condition for 7 tuples out of 10. We then confirm that 10 interaction samples in swap softly afect a subset of 4-tuples by ˜ . Note that other loss functions for both data and swap are applicable.
We demonstrate how our proposed framework works with crawled real data. In the following experiments, we keep the two functions (the Frobenius norm for data and tanh for swap) for our method, and focus on Swap only in Eq. (5). In this paper, we only evaluate how collected interaction data swap afect the computed ranked list of itineraries. To evaluate this, we compare resulted lists with multiple settings, and quantitatively compare them. Setup We extracted user-generated itineraries from TripHobo and rating data from TripAdvisor1. We found itineraries tagged with Tokyo, and collected individual itineraries. An itinerary consists of several days (i.e., on day 1, on day 2, etc.). We then divided the multi-day itinerary into a set of one-day ones to focus on planning within a day. We collected such one-day itineraries to make a whole set as historical data. From the whole dataset, we only sampled a selected area of Tokyo, named Asakusa2, and we finally have 245 itineraries in our . With 1https://www.triphobo.com/ and https://www.tripadvisor.jp/ (access confirmed at June, 2022.) 2By selecting POIs whose locations are included in the area of latitude [35.443674, 35.825408] and longitude [139, 514896, 139.927981].
(a) ^ (l) ˜ (b) 1st (1) (c) 2nd (2) (d) 3rd (3) (e) 4th (4) extracted itineraries, we also collected a set [ ] of all POIs in the data ( = 29). For each poi ∈ [ ], we obtained Score() from stars recorded in TripAdvisor.
We implemented our top- itinerary planning algorithm (as in Sec. 2.3), set = 5, and tested = 1 and ∈ {0, 1}. To evaluate our method, we compared obtained lists of top-5 itineraries by ^ and ˜ . To learn ˜ , we just randomly sampled 300 pairs as swap from neg 4-tuples as an simulation data. Parameter settings were the same to those in Sec. 3.3.
Visualization of generated itineraries For random start and goal POIs out of 29 POIs, with ^ for both = 0 and = 1 cases, the baseline method generated 10 itineraries in total, as illustrated in Fig. 3, where we had 8 unique itineraries. Using identifiers depicted in Fig. 3, we had ℒ1 = ⟨1, 2, 3, 4, 5⟩ when ^ and = 0, and ℒ2 = ⟨2, 1, 6, 7, 8⟩ when ^ and = 1. With ˜ for both = 0, Fig. 3 illustrates a new itineraries generated through our framework, where we have a new list ℒ3 = ⟨9, 10, 11, 12, 13⟩ when ˜ and = 0. For ˜ and = 1, we have another list ℒ4 = ⟨10, 9, 11, 13, 2⟩. Note that ℒ4 is not illustrated in Fig. 3 as itineraries in ℒ4 are already illustrated.
Evaluations To evaluate itineraries in terms of scores (∑︀− 1 ∑︀=2 Score(), ) and ranking
=2
(i.e., ℒ1, ℒ2, and ℒ3), we first measure total scores and travel costs of each itinerary. Figure 4a
shows a scatter plot of the two terms of Eq. (
(b) Ranking diferent score and sample size circles, and a line between two circles indicates the two itineraries are the same.
In results, Fig. 3, Fig. 4a, and Fig. 4b indicate that we could generate a variety of itineraries by our approach. In other words, our proposed method diversified the ranking results based on interaction data.
We proposed a new framework in which users directly interact with our system by editing displayed itineraries. Our idea is collecting rich feedback via editions by users, and utilizing such data when generating personalized itineraries. Throughout our proof-of-concept experiments, we confirm that our method could diversify ranking generated by top- itinerary generation via the orienteering problem.
In our future work, we will investigate more deeply learning-based methods via interaction data, and plan a quantitative user study to develop interaction and optimization-based itinerary planning method like [2]. [4] D. Chen, C. S. Ong, L. Xie, Learning points and routes to recommend trajectories, in: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, CIKM ’16, Association for Computing Machinery, New York, NY, USA, 2016, pp. 2227–2232. [5] P. Vansteenwegen, W. Soufriau, D. Van Oudheusden, The orienteering problem: A survey,
European Journal of Operational Research 209 (2011) 1–10. [6] Z. Friggstad, S. Gollapudi, K. Kollias, T. Sarlos, C. Swamy, A. Tomkins, Orienteering algorithms for generating travel itineraries, in: Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM ’18, Association for Computing Machinery, New York, NY, USA, 2018, pp. 180–188. [7] S. Basu Roy, G. Das, S. Amer-Yahia, C. Yu, Interactive itinerary planning, in: 2011 IEEE 27th International Conference on Data Engineering, ICDE ’11, IEEE Computer Society, USA, 2011, pp. 15–26. doi:10.1109/ICDE.2011.5767920. [8] R. Canoy, T. Guns, Vehicle routing by learning from historical solutions, in: Proc. of
CP2019, 2019, pp. 54–70. [9] J. Mandi, R. Canoy, V. Bucarey, T. Guns, Data driven vrp: A neural network model to learn hidden preferences for vrp, in: Proc. of CP2021, 2021. [10] C. E. Miller, A. W. Tucker, R. A. Zemlin, Integer programming formulation of traveling salesman problems, Journal of the ACM (JACM) 7 (1960) 326–329. [11] E. L. Lawler, A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem, Management science 18 (1972) 401–405.