1 Introduction
-
We propose a new POI selection heuristic for personalized itinerary recommendation by considering visitors’ various preferences, i.e., POIs popularity, visitors interest, prior visitors visiting, queuing and traveling time.
-
We introduce an effective itinerary reward function-based level of trade-off among prior visitors visiting time, POI popularity, visitor interests and queuing time.
-
We propose adaptive MCTS-based reinforcement learning algorithm EffiTourRec to make visitor itinerary recommendation more effective and efficient by using the new POI selection heuristic and reward function strategy.
-
In addition, to improve the time efficiency of our proposed method, we use MCTS pruning technique to reduce search space by filtering out non-optimal and duplicate itineraries in the early stages.
-
We evaluate our proposed algorithm on five theme parks datasets to show our proposed method’s effectiveness and efficiency against various state-of-the-art baselines. We test on theme parks datasets because that is what [36] did to compare the itinerary recommendation with queues.
-
Experiment results demonstrate the effectiveness of our proposed method over baselines; our method outperforms the current state-of-the-art by 21.04% to 50.24% in precision, 7.83% to 21.23% in F1-score, 8.36% to 43.96% in visiting time ratio with total time. It also shows that the efficiency of our proposed EffiTourRec algorithm outperforms than the baselines by reducing 51.62% to 66.59% execution time and 47.49% to 61.99% moves in MCTS compared to the best baseline PersQ algorithm.
2 Related work
2.1 General itinerary recommendation
2.2 Personalized itinerary recommendation
2.3 Personalized itinerary recommendation with queuing time awareness
2.4 Top-k POI recommendation
2.5 Sequences of locations
2.6 Discussion of differences with previous works
Algorithms | Popularity based | Interest based | Queue time | Visit time | Travel time | Heuristics based | Construct itinerary | Pruning technique |
---|---|---|---|---|---|---|---|---|
UBCF [53] | \(\checkmark \) | \(\checkmark \) | ||||||
IHA [55] | \(\checkmark \) | \(\checkmark \) | min | min | Heuristic | |||
TripBuilder [2] | \(\checkmark \) | \(\checkmark \) | \(\checkmark \) | |||||
pirT [25] | \(\checkmark \) | \(\checkmark \) | min | min | A* | \(\checkmark \) | ||
\(\checkmark \) | \(\checkmark \) | min | min | \(\checkmark \) | ||||
PersQ [36] | \(\checkmark \) | \(\checkmark \) | min | min | min | MCTS | \(\checkmark \) | |
EffiTourRec | \(\checkmark \) | \(\checkmark \) | min | max | min | MCTS | \(\checkmark \) | \(\checkmark \) |
3 Preliminaries
4 Problem definition
5 Proposed EffiTourRec method
5.1 Monte Carlo tree search
5.2 Efficient move pruning
5.3 EffiTourRec algorithm
6 Experiments
Theme Park | # Photos | POI Visits | # Visitors | # POIs | # Visit Sequences |
---|---|---|---|---|---|
Disney Land (disland) | 181,735 | 119,987 | 3,704 | 31 | 11,758 |
Epcot (epcot) | 90,435 | 38,950 | 2,725 | 17 | 5,816 |
California Adventure (caliAdv) | 193,069 | 57,177 | 2,593 | 25 | 6,907 |
Disney Hollywood (disHolly) | 57,426 | 41,983 | 1,972 | 13 | 3,858 |
Magic Kingdom (MagicK) | 133,221 | 73,994 | 3,342 | 27 | 8,126 |
6.1 Datasets
6.2 Baseline algorithms
-
Personalized Tours with Queuing Time Awareness (PersQ) [36]: Itinerary starts at starting POI, selects potential POIs based on maximum popularity and interest, minimizing queuing time and completes the itinerary at ending POI within a time budget.
-
Personalized Tour Recommendation (PersTour) [39]: This algorithm recommends itineraries based on POI popularity and time-based visitor interest within budget time.
-
Tour Recommendation with Interest Category (TourRecInt) [35]: The algorithm introduces mandatory visit POI category-based tour recommendation system in which visitors are most interested in visit frequently visited POIs category.
-
Trip Builderer Algorithm (TripBuilder) [2]: The main objective is to define visitor interest by the spending time of visited POI of a certain category, corresponding to his/her total visiting time.
-
Iterative Heuristic Approximation (IHA) [55]: A heuristic-based recommendation system that starts with a tour staring \(p_i\), completes at \(p_n\) and repetitively adds new POI into the itinerary until the budget time is reached.
-
User-Based Collaborative Filtering for Itineraries (UBCF)[53]: One of the popular user-based collaborative filtering variations is proposed to recommend a set of top-k POIs for another user to utilize user interest similarities.
6.3 Performance evaluation
-
Precision: The ratio of POI recommended itinerary I that are present in a visitor’s real-life visit sequence. Let \(P_{real}\) be the set of POIs in the real visit sequence and \(P_{rec}\) be the set of POIs recommended in itinerary I, the tour precision is defined as: \(Precision =\frac{|P_{real} \bigcap P_{rec}|}{|P_{rec}|}\).
-
Recall: The proportion of POI visits in a visitor’s real-life visit sequence that also be present in the recommended itinerary I. Using the same notation for \(P_{real}\) and \(P_{rec}\), the tour recall is defined as: \(Recall =\frac{|P_{real} \bigcap P_{rec}|}{|P_{real}|}\).
-
F1-Score: The harmonic mean of both tour recall \(IR_I\) and tour precision \(IP_I\) of an itinerary I, defined as: \(F1-Score =\frac{2*IP_I*IR_I}{IP_I + IR_I}\).
-
Popularity: The average popularity of all POIs in a recommended itinerary I, exposed as: \(Popularity = \frac{1}{|I|}\sum _{p_i \in I}{PoP(p_i)}\).
-
Interest: The average interest of all POIs in a recommended itinerary I, exposed as: \(Interest = \frac{1}{|I|} \sum _{p_i \in I}{IoP(p_i)}\).
-
Rank: The average rank of our proposed EffiTourRec algorithm is defined based on popularity and interest scores ranked compare with other algorithms, exposed as: \(Rank = \frac{1}{|I|} \sum _{p_i \in I}{MaxRange - \big (\frac{Norm(PoP(p_i)) + Norm(IoP(p_i))}{2}} \times MaxRange \big ) + 1\), where Norm(.) is a normalization function converts score within [0,1] and MaxRange is maximum Rank value (we assume 1 = best and 12 = worst).
-
Visiting Time Cost Ratio (VTCR): The ratio of visiting time of an itinerary I, relative to itinerary total time, defined as:\(VTCR = \sum _{p_i \in I, i \ne 1} \frac{VDoP(p_i)}{TDoP(p_{i-1},p_i) + VDoP(p_i)+Queue^t_{p_i}}\).
-
Queuing Time Cost Ratio (QTCR): The ratio of queuing time an itinerary I, relative to itinerary total time, defined as:\(QTCR = \sum _{p_i \in I, i \ne 1} \frac{Queue^t_{p_i}}{TDoP(p_{i-1},p_i) + VDoP(p_i)+Queue^t_{p_i}}\).
-
Queue Time Popularity Ratio (QTPR): The ratio of queuing time an recommended itinerary, relative to the popularity of an itinerary I, defined as:\(QTPR = \sum _{p_i \in I} \frac{Queue^t_{p_i}}{PoP(p_i)}\).
-
Maximum Queuing Time (MQT): The average queuing time of POIs in itinerary I, relative to their maximum queuing time, defined as:\(MQT = \frac{1}{|I|} \sum _{p_i \in I} {\frac{Queue^t_{p_i}}{Max_{t \in T}(Queue^t_{p_i})}}\).
-
Execution Time: Execution time means algorithm run time to recommend itineraries for particular datasets.
-
Number of Moves: The total number of POI moves require to create itineraries for particular datasets.
6.4 Results and discussion
6.4.1 Precision, recall and F1-score
6.4.2 Popularity, interest and rank of POI
Datasets | EffiTourRec | PersQ | PersTour | TourRecInt | TripBuilder | IHA | UBCF | |
---|---|---|---|---|---|---|---|---|
disland | Popularity | \(\mathbf{3822 }\pm \mathbf{64 }\) | \(2860\pm 49\) | \(2443\pm 41\) | \(3263\pm 48\) | \(2940\pm 41\) | \(1651\pm 33\) | \(2314\pm 42\) |
Interest | \(157.8\pm 20.2\) | \(147.5 \pm 15.9\) | \(100.9\pm 11.1\) | \(122.8\pm 21.1\) | \(109.8\pm 12.5\) | \(\mathbf{173.2 }\pm \mathbf{18.6 }\) | \(127.3\pm 11.3\) | |
Rank | \(5.65\pm 0.06\) | \(6.05\pm 0.07\) | \(5.75 \pm 0.09\) | \(5.76 \pm 0.07\) | \(5.98\pm 0.10\) | \(\mathbf{4.47 }\pm \mathbf{0.04 }\) | \(5.68\pm 0.05\) | |
Epcot | Popularity | \(\mathbf{2376 }\pm \mathbf{64 }\) | \(1927\pm 44\) | \(1415\pm 31\) | \(1376\pm 29\) | \(1377\pm 33\) | \(1666\pm 35\) | \(1175\pm 28\) |
Interest | \(\mathbf{23}.21 \pm \mathbf{2}.4 \) | \(22.61\pm 1.9\) | \(15.1\pm 1.3\) | \(15.1\pm 1.2\) | \(18.8\pm 2.0\) | \(21.7\pm 1.5\) | \(12.2\pm 1.0\) | |
Rank | \(\mathbf{4}.60 \pm \mathbf{0}.11 \) | \(4.89\pm 0.12\) | \(5.38\pm 0.09\) | \(5.08\pm 0.10\) | \(5.50\pm 0.10\) | \(4.69\pm 0.08\) | \(6.06\pm 0.08\) | |
caliAdv | Popularity | \(\mathbf{2834 }\pm \mathbf{37 }\) | \(1603\pm 26\) | \(1518\pm 41\) | \(1554\pm 43\) | \(1560\pm 50\) | \(1446\pm 33\) | \(1416\pm 35\) |
Interest | \(\mathbf{242.3 }\pm \mathbf{37.8 }\) | \(238.2\pm 34.1\) | \(145.0\pm 33.2\) | \(188.3\pm 34.1\) | \(161.9\pm 29.9\) | \(239.2\pm 32.7\) | \(130.5\pm 18\) | |
Rank | \(\mathbf{4.14 } \pm \mathbf{0.09 }\) | \(5.71\pm 0.08\) | \(5.58\pm 0.08\) | \(5.3\pm 0.08\) | \(5.56\pm 0.13\) | 4.19 ± 0.06 | 5.84 ± 0.07 | |
disHolly | Popularity | \(\mathbf{3142 }\pm \mathbf{74 }\) | \(2480\pm 54\) | \(1990\pm 51\) | \(2016\pm 52\) | \(1803\pm 54\) | \(2976\pm 44\) | \(1737\pm 47\) |
Interest | \(15.6\pm 1.3\) | \(\mathbf{16.2 }\pm \mathbf{1.4 }\) | \(12.0\pm 1.2\) | \(12.4\pm 1.2\) | \(11.9\pm 1.1\) | \(16.1\pm 1.4\) | \(11.4\pm 1.1\) | |
Rank | \(\mathbf{3.61 }\pm \mathbf{0.13 }\) | \(4.33\pm 0.14\) | \(4.73\pm 0.10\) | \(4.33\pm 0.12\) | \(4.53\pm 0.10\) | 3.65 ± 0.08 | \(4.98\pm 0.09\) | |
MagicK | Popularity | \(\mathbf{3724 }\pm \mathbf{78 }\) | \(1960\pm 35\) | \(1767\pm 79\) | \(1629\pm 70\) | \(1591\pm 68\) | \(2125\pm 26\) | \(1616\pm 36\) |
Interest | \(\mathbf{31.16 }\pm \mathbf{2.7 }\) | \(30.41\pm 2.3\) | \(18.4\pm 0.4\) | \(18.2\pm 2.6\) | \(26.2\pm 2.4\) | \(27.6\pm 2.4\) | \(14.2\pm 0.9\) | |
Rank | \(\mathbf{4.27 } \pm \mathbf{0.09 }\) | \(5.70\pm 0.09\) | \(5.84\pm 0.12\) | \(5.91\pm 0.15\) | \(6.09\pm 0.14\) | \(4.36\pm 0.06\) | \(6.07\pm 0.06\) |
6.4.3 Visiting, travel and queuing time metrics
EffiTourRec | PersQ | PersTour | TourRecInt | TripBuilder | IHA | UBCF | ||
---|---|---|---|---|---|---|---|---|
disland | VTCR | \(\mathbf{0.180 }\pm \mathbf{0.002 }\) | \(0.129\pm 0.002\) | \(0.118\pm 0.003\) | \(0.120\pm 0.002\) | \(0.123\pm 0.003\) | \(0.07\pm 0.001\) | \(0.11\pm 0.002\) |
QTCR | \(\mathbf{0.765 }\pm \mathbf{0.003 }\) | \(0.809\pm 0.003\) | \(0.849\pm 0.004\) | \(0.853\pm 0.003\) | \(0.847\pm 0.004\) | \(0.89\pm 0.002\) | \(0.83\pm 0.003\) | |
QTPR | \(\mathbf{0.760 }\pm \mathbf{0.012 }\) | \(0.91\pm 0.02\) | \(1.42\pm 0.05\) | \(1.08\pm 0.004\) | \(1.19\pm 0.03\) | \(1.71\pm 0.03\) | \(1.32\pm 0.04\) | |
MQT | \(0.154\pm 0.002\) | \(0.121\pm 0.002\) | \(0.172\pm 0.005\) | \(0.152\pm 0.006\) | \(0.152\pm 0.005\) | \(0.151\pm 0.002\) | \(\mathbf{0.118 }\pm \mathbf{0.002 }\) | |
Epcot | VTCR | \(\mathbf{0.328 }\pm \mathbf{0.008 }\) | \(0.264\pm 0.006\) | \(0.18\pm 0.004\) | \(0.18\pm 0.004\) | \(0.195\pm 0.005\) | \(0.13\pm 0.003\) | \(0.21\pm 0.005\) |
QTCR | \(\mathbf{0.586 }\pm \mathbf{0.009 }\) | \(0.636\pm 0.007\) | \(0.77\pm 0.004\) | \(0.77\pm 0.004\) | \(0.76\pm 0.005\) | \(0.80\pm 0.003\) | \(0.71\pm 0.005\) | |
QTPR | \(\mathbf{0.893 }\pm \mathbf{0.02 }\) | \(0.96\pm 0.025\) | \(1.68\pm 0.042\) | \(1.74\pm 0.044\) | \(1.74\pm 0.051\) | \(1.47\pm 0.03\) | \(2.25\pm 0.09\) | |
MQT | \(\mathbf{0.121 }\pm \mathbf{0.004 }\) | \(0.125\pm 0.004\) | \(0.183\pm 0.004\) | \(0.181\pm 0.004\) | \(0.175\pm 0.004\) | \(0.195\pm 0.003\) | \(0.158\pm 0.004\) | |
caliAdv | VTCR | \(\mathbf{0.30 }\pm \mathbf{0.006 }\) | \(0.207\pm 0.004\) | \(0.127\pm 0.004\) | \(0.126\pm 0.004\) | \(0.138\pm 0.005\) | \(0.08\pm 0.002\) | \(0.13\pm 0.003\) |
QTCR | \(\mathbf{0.631 }\pm \mathbf{0.008 }\) | \(0.682\pm 0.005\) | \(0.829\pm 0.006\) | \(0.829\pm 0.005\) | \(0.809\pm 0.006\) | \(0.85\pm 0.004\) | \(0.79\pm 0.005\) | |
QTPR | \(\mathbf{0.623 }\pm \mathbf{0.03 }\) | \(0.815\pm 0.02\) | \(1.86\pm 0.04\) | \(1.33\pm 0.06\) | \(1.49\pm 0.07\) | \(2.02\pm 0.16\) | \(1.88\pm 0.09\) | |
MQT | \(\mathbf{0.096 }\pm \mathbf{0.003 }\) | \(0.097\pm 0.002\) | \(0.143\pm 0.008\) | \(0.146\pm 0.005\) | \(0.143\pm 0.004\) | \(0.159\pm 0.003\) | \(0.139\pm 0.003\) | |
disHolly | VTCR | \(\mathbf{0.255 }\pm \mathbf{0.007 }\) | \(0.239\pm 0.006\) | \(0.20\pm 0.005\) | \(0.20\pm 0.005\) | \(0.20\pm 0.004\) | \(0.114\pm 0.004\) | \(0.194\pm 0.005\) |
QTCR | \(\mathbf{0.693 }\pm \mathbf{0.007 }\) | \(0.696\pm 0.006\) | \(0.769\pm 0.006\) | \(0.77\pm 0.005\) | \(0.768\pm 0.005\) | \(0.849\pm 0.004\) | \(0.754\pm 0.006\) | |
QTPR | \(\mathbf{0.769 }\pm \mathbf{0.04 }\) | \(0.915\pm 0.05\) | \(1.99\pm 0.13\) | \(1.96\pm 0.12\) | \(2.22\pm 0.14\) | \(0.98\pm 0.03\) | \(2.01\pm 0.09\) | |
MQT | \(\mathbf{0.143 }\pm \mathbf{0.004 }\) | \(0.150\pm 0.004\) | \(0.18\pm 0.005\) | \(0.18\pm 0.005\) | \(0.18\pm 0.005\) | \(0.208\pm 0.005\) | \(0.20\pm 0.006\) | |
MagicK | VTCR | \(\mathbf{0.254 }\pm \mathbf{0.004 }\) | \(0.199\pm 0.003\) | \(0.126\pm 0.003\) | \(0.123\pm 0.003\) | \(0.155\pm 0.006\) | \(0.07\pm 0.002\) | \(0.16\pm 0.003\) |
QTCR | \(\mathbf{0.676 }\pm \mathbf{0.004 }\) | \(0.70\pm 0.004\) | \(0.842\pm 0.004\) | \(0.834\pm 0.006\) | \(0.802\pm 0.005\) | \(0.87\pm 0.002\) | \(0.77\pm 0.004\) | |
QTPR | \(\mathbf{0.669 }\pm \mathbf{0.02 }\) | \(0.83\pm 0.02\) | \(1.59\pm 0.03\) | \(1.47\pm 0.04\) | \(1.42\pm 0.06\) | \(1.14\pm 0.03\) | \(1.58\pm 0.04\) | |
MQT | \(\mathbf{0.111 }\pm \mathbf{0.003 }\) | \(0.12\pm 0.002\) | \(0.18\pm 0.006\) | \(0.173\pm 0.004\) | \(0.148\pm 0.005\) | \(0.198\pm 0.003\) | \(0.161\pm 0.003\) |
6.4.4 Runtime analysis between existing methods and EffiTourRec
Datasets | EffiTourRec | PersQ | PersTour | TourRecInt | TripBuilder | Efficiency |
---|---|---|---|---|---|---|
disland | 0.34 | 0.69 | 4.2 | 5.06 | 5.74 | 50.72% |
Epcot | 0.21 | 0.35 | 1.57 | 1.59 | 1.87 | 40.00% |
caliAdv | 0.26 | 0.64 | 3.6 | 3.8 | 4.01 | 59.39% |
disHolly | 0.16 | 0.31 | 0.74 | 0.88 | 1.02 | 48.39% |
MagicK | 0.22 | 0.68 | 8.95 | 6.93 | 5.63 | 67.64% |
6.4.5 Number of moves analysis between EffiTourRec and Existing Method
Algorithms | disland | Epcot | caliAdv | disHolly | MagicK |
---|---|---|---|---|---|
PersQ | 6087171 | 2069796 | 4838537 | 1334913 | 5165181 |
EffiTourRec | 3492072 | 997044 | 1795576 | 638150 | 2068937 |
Moves Reduce | 42.63% | 51.83% | 62.89% | 52.19% | 59.77% |