# Personalized Tour Itinerary Recommendation Algorithm Based on Tourist Comprehensive Satisfaction
## 4 Method
### Time Planning Algorithm Based on Tour Itinerary Planning Satisfaction
```
Input : Node : Related attribute; MRTimePar; AvailableTime; Physical exertion limit; Output : \(TPSS\) and Itinerary schedule;
1\(LKH\_TP()\)
2 CreateCandidateSet();
3\(\mathit{BestTPSS}\gets 0\);
4 forRun \(\gets 1\) toRunsdo
5\(TPSS_{FT}\gets\mathit{FindTour}()\);
6 if\(TPSS_{FT}>\mathit{BestTPSS}\)then
7\(\mathit{BestTPSS}\gets\mathit{TPSS}_{FT}\);
8\(\mathit{RecordBestTour}()\);
9\(\mathit{returnBestTour}\);
10\(\mathit{FindTour}()\)
11\(\mathit{BetterTPSS}\gets 0\);
12 forTrial \(\leftarrow\) 1 toTrialsdo
13\(\mathit{ChooseInitialTour}()\);
14\(TPSS_{LK}\leftarrow\mathit{LinKernighan}()\);
15 if\(TPSS_{LK}>\mathit{BetterTPSS}\)then
16\(\mathit{RecordBetterTour}()\);
17\(\mathit{BetterTPSS}\gets\mathit{TPSS}_{LK}\);
18\(\mathit{AdjustCandidateSet}()\);
19\(\mathit{ResetCandidateSet}()\);
20 return\(\mathit{BetterTPSS}\);
```
**Algorithm 2** LKH_TP--Overview of Algorithm

Lines 11-20 explain the \(\mathit{FindTour}\) function, which conducts trial experiments. In each experiment, it first generates initial tour sequences using a combination of random and heuristic methods, ensuring the sufficient diversity of initial solutions while improving the efficiency. Then, the Lin-Kernighan function attempts to improve the selected initial tour through heuristic \(\lambda-opt\) edge exchanges. For each tour sequence, the objective function value is obtained by calling the time planning algorithm, and this value is used to determine whether an improvement has occurred. Whenever a better tour is found, it is recorded, and the priority of candidate edges is re-ranked. Finally, the best tour among these experimentsis returned, and the original candidate edge set is re-established at the exit from \(FindTour\). For a detailed explanation of the LKH algorithm, please refer to references [28; 29]. The specified node visit order is achieved by adding constraints during the generation of the initial solution and edge exchanges. ### Tour Itinerary Recommendation Algorithm Based on Tourist Comprehensive Satisfaction

We implemented the itinerary recommendation algorithm by combining the algorithm described in Section 4.2 with a variant of the Monte Carlo Tree Search (MCTS) algorithm. The MCTS algorithm is a search algorithm that has been successfully applied not only in artificial intelligence (AI) games such as chess and Go [30] but also in personalized itinerary recommendation [4; 5; 31]. The MCTS algorithm enables us to explore smaller, more promising regions of the solution space without traversing the entire solution space, thereby improving operational efficiency. Algorithm 3 outlines the implementation process of the MCTSLKH_TR algorithm. In each iteration, we start from the user-selected base node combination (line 6), select nodes to add to the current combination, and perform itinerary planning until inserting a scenic spot would result in exceeding the cost limit, total time limit, or inaccessible scenic spots (lines 7-15). Then, the successful itinerary from the previous iteration is recorded as the recommendation for the current iteration, and itinerary-related parameters are calculated and propagated back to relevant candidate nodes (lines 16-27). Finally, the recommendation with the maximum objective function among these itinerary recommendations is returned (line 28). ```
Input : Node : Related attribute; MRTimePar; Physical exertion limit; Travel style; Cost constraint; \(R_{div}\) type; Output : 1 : Itinerary schedule; \(MCTSLKH\_TourRec()\) Preprocessing();  Initialize NodeRecordR, NodeRecordV, NodeRecordTE; /* respectively record the cumulative Reward, visit count, and TimeEfficiency of each node.