# Personalized Tour Itinerary Recommendation Algorithm Based on Tourist Comprehensive Satisfaction
## 4 Method
### Time Planning Algorithm Based on Tour Itinerary Planning Satisfaction
\[\mathit{TimeEfficiency}_{a_{i}}=\frac{\mathit{EVDur}_{a_{i}}}{\mathit{EVDur} _{a_{i}}+\mathit{TDur}(a_{last},a_{i})+\mathit{TDur}(a_{i},a_{next})-\mathit{ TDur}(a_{last},a_{next})} \tag{15}\]

The diversity of scenic categories is calculated based on user preferences using Equation (5) or (6). The scenic category diversity reward, combined with the reward function, constitutes the objective function value of the itinerary. In the process of incorporating scenic spots into the itinerary, the itinerary planning algorithm is used to determine whether it is still possible to insert additional spots. In such cases, optimizing the itinerary planning results is meaningless. Therefore, the itinerary planning algorithm is designed to exit as soon as an eligible itinerary planning is found (Lines 14), while a complete itinerary planning is performed when computing the final results in each iteration (Lines 18). Additionally, because the same node combination will yield the same result through itinerary planning, we utilize two hash tables to store obtained itinerary planning results, thus avoiding duplicate calculations (Lines 12-19). We enhance the efficiency of the algorithm through these measures. Algorithm 4 outlines how to select the next node to add to the itinerary. We traverse the candidate scenic spots outside the current itinerary (Line 3), first obtaining the number of times each node has been selected. If a node has never been selected before, we directly choose that node (Lines 4-5). Next, we avoid adding nodes known to make the current itinerary infeasible through hash table queries (Lines 6-8), thereby improving the effectiveness of node additions and the diversity of node combinations. Then, we utilize the Upper Confidence Bound (UCB) algorithm to select the node with the highest UCB index from the remaining candidate nodes to add to the current itinerary (Lines 9-19). The UCB algorithm applied to tree structures is commonly referred to as the UCT algorithm [32], typically with the objective of maximizing (16). The first part represents the exploitation value of the node, while the second part represents the exploration value of the node. Here, the parameter \(C_{p}\) determines the emphasis on exploring nodes. We set \(C_{p}\) to \(1/\sqrt{2}\) to balance exploitation and exploration. \[UCT_{n}=\frac{Total{Reward}_{N}}{VisitCount_{N}}+2C_{p}\sqrt{\frac{2\ln{VisitCount _{CurrN}}}{VisitCount_{N}}} \tag{16}\]

\[UCB_{n}=\alpha_{H}*\frac{Total{Time}Efficiency_{N}*SAS_{N}}{VisitCount_{N}}+ \frac{Total{Reward}_{N}}{VisitCount_{N}}+2C_{p}\sqrt{\frac{2\ln{Total}SeleNum}{ VisitCount_{N}}} \tag{17}\]

Our UCB formula (as outlined in Equation (17)) significantly improves upon the original UCT algorithm. Because the candidate nodes have different intrinsic properties, we introduce a heuristic term \(Total{Time}Efficiency_{N}/VisitCount_{N}*SAS_{N}\) that considers the average time efficiency and attractiveness of the nodes. It is beneficial for selecting nodes that maximize the rewards of the itinerary. Moreover, since our node visit order depends on the itinerary planning algorithm, the choice of the next node is independent of the currently expanded node. We replace the selection count of the current node in the exploration term with the total count of selections for all nodes. To control the influence weights of both components, we normalize both the exploitation and heuristic parts, with \(\alpha_{H}\) denoting the weighting coefficient for the heuristic term. ## 5 Experiment and Example Analysis

This section introduces four sets of experiments related to the algorithm and provides an in-depth analysis of the experimental results. Specifically, Section 5.2 describes in detail the process of setting the number of iterations and heuristic weights in the algorithm. Section 5.3 analyzes the effectiveness of heuristics in the itinerary planning algorithm. Section 5.4 analyzes the effectiveness of the selection function in the itinerary planning algorithm.