# Personalized Tour Itinerary Recommendation Algorithm Based on Tourist Comprehensive Satisfaction
## 4 Method
### Time Planning Algorithm Based on Tour Itinerary Planning Satisfaction
* / TotalSeleNum \(\leftarrow\) 0; for Iterations \(\leftarrow\) 1 to maxLoopdo  IsPass \(\leftarrow\) True NodeSet \(\leftarrow\) BaseNodeSet; while(IsPass \(=\) True)do  PreviousNodeSet \(\leftarrow\) NodeSet ; \(N\leftarrow\) SelectNextNode();  TotalSeleNum \(\leftarrow\) TotalSeleNum \(\leftarrow\) TotalSeleNum \(+\)  NodeSet \(\leftarrow\) UpdateNodeSet(NodeSet, \(N\));  IsFound, IsPass \(\leftarrow\) HashSearch(HTable, Hash(NodeSet)); ifIsFound \(\
eq\) Truethen  IsPass, \(I_{top}\gets\) LKH_TP(NodeSet, abridged);  HashInsert(HTable, Hash(NodeSet), \(\mathit{IsPass}\));  IsFound, TPSS, \(I_{top}\gets\) HashSearch(HTable2, Hash(PreviousNodeSet)); ifIsFound \(\
eq\) Truethen  TPSS, \(I_{top}\gets\) LKH_TourPlan(PreviousNodeSet, unabridged);  HashInsert2(HTable2, Hash(PreviousNodeSet), TPSS, \(I_{top}\));  Reward\(I_{top}\leftarrow\) CalculateRaturat(PreviousNodeSet, TPSS);  TimeEfficiency\({}_{I_{top}}[]\leftarrow\) CalculateTimeEfficiency(PreviousNodeSet, \(I_{top}\));  BackPropagationR \(\big{(}NodeRecordR,\)\(I_{temp},\)\(\mathit{Reward}_{I_{top}}\big{)}\);  BackPropagationV \(\big{(}NodeRecordV,\)\(I_{temp}\big{)}\);  BackPropagationTE \(\big{(}NodeRecordTE,\)\(I_{temp},\)\(\mathit{TimeEfficiency}_{I_{temp}}[]\big{)}\);  CategoryR\({}_{I_{temp}}\)\(\leftarrow\) CalculateCategoryR(PreviousNodeSet, Rtype);  CSS\({}_{I_{top}}\gets\) Reward\({}_{I_{top}}+\) CategoryR\({}_{I_{top}}\)\(\mathit{I_{list}}\gets\) List\(\cup\)I\({}_{temp}\) Return itinerary \(I\)withmaxCSS from \(I_{list}\);
```

**Algorithm 3** MCTSLKH_TR--Overview of Algorithm

In each iteration, we decompose the itinerary recommendation task into two parts: node selection and itinerary planning, which are completed using the MCTS algorithm and the itinerary planning algorithm, respectively. The MCTS algorithm is responsible for selecting unordered node combinations, while the itinerary planning algorithm generates complete itineraries. Subsequently, the optimal itinerary recommendation result is selected based on overall satisfaction. This process differs from conventional MCTS algorithms, which gradually determine the sequence of actions, but it is better suited to our itinerary recommendation problem. It ensures the quality of itinerary planning and makes itinerary rewards more valuable, thereby promoting the selection of subsequent high-quality nodes. Additionally, this approach can reduce the computational complexity and provide more powerful personalized services through independent itinerary planning optimization algorithms. The recommended itinerary provided in each iteration gives feedback to the relevant candidate nodes through a reward function, where the reward function is represented by Equation (14) and includes all parts of the objective function except for the reward for diversity in attraction types. This is because the diversity in the attraction types of the itinerary is independent of the quality of the nodes, and the related requirements are optional. \[\mathit{Reward}=\mathit{TUS}(I)*\mathit{ISAS}(I)*\mathit{FS}(I) \tag{14}\]

We simultaneously calculate both the time efficiency of nodes and the diversity of scenic categories within the itinerary. The time efficiency of a node within an itinerary is defined using Equation (15), where \(a_{last}\) represents the previous node \(a_{i}\) in the itinerary, \(a_{next}\) represents the next node \(a_{i}\) in the itinerary, and \(TDur\) represents the travel time between these two points. The time efficiency of nodes is also propagated to every recommended node within the itinerary. This indicator is highly correlated with the time utilization rate of the itinerary and can highlight the inherent properties of the nodes themselves. Its average value can indirectly evaluate the positional attributes of the nodes, which we use as a heuristic factor considered in the selection node function.