# Personalized Tour Itinerary Recommendation Algorithm Based on Tourist Comprehensive Satisfaction
## 4 Method
### Time Planning Algorithm Based on Tour Itinerary Planning Satisfaction
The proportion of itinerary time (\(TimePropo\)), which represents the ratio of the total duration of the recommended itinerary to the user's planned travel duration;
2. Itinerary Scenic Spot Attractiveness Score (\(ISAS\));
3. Time Utilization Score (\(TUS\));
4. Feasibility Score (\(FS\));
5. Comprehensive satisfaction score (\(CSS\));
6. \(Runtime\). These evaluation metrics can be used to comprehensively measure the quality and practicality of the recommended itinerary solutions. The experimental results are shown in Table 7, which also includes several values relevant to the evaluation metric calculations, such as the number of recommended attractions (\(RecNum\)), the actual duration of attraction visits planned in the itinerary (\(AVisDur\)), the duration of the itinerary (\(ItinDur\)), and the itinerary penalty (\(Penalty\)). Table 8 outlines the average values of these metrics across the three cases. We analyze the results as follows:

1. _TimePropo_: It can be observed that the recommended itineraries generated by all three algorithms effectively utilize the planned travel time of the tourists. The average _TimePropo_ exceeds 96% across the board. Maximizing the use of time under time constraints is a fundamental requirement for tourists and is also a necessary condition for enhancing comprehensive satisfaction. 2. _TUS_, _ISAS_, _FS_, _CSS_: Among the CSS and related evaluation metrics, our algorithm achieves the best results in CSS and TUS across all three cases. The average CSS surpasses that of the GreedyLKH_TR algorithm by 9.84% and exceeds that of the MCTS_TR algorithm by 14.85%. Similarly, the average TUS outperforms that of the GreedyLKH_TR algorithm by 13.20% and that of the MCTS_TR algorithm by 15.99%. Over the accumulated 9-day itineraries in the three cases, our algorithm provides an additional 610 min and 787 min of attraction visitation time compared to the GreedyLKH_TR and MCTS_TR algorithms, respectively. The FS of all three algorithms is relatively similar across the three cases, indicating that the itinerary results generated as part of the algorithm based on time planning closely match the tourists' expectations. While the average ISAS of our algorithm is slightly lower than that of the two baseline algorithms, since the improvement of ISAS is direct and relatively simple, and the proposed algorithm selects the tour itinerary with a slightly lower ISAS but higher comprehensive satisfaction through trade-offs, it can be seen that the optimization ability of the proposed algorithm is superior to the two baseline algorithms. 3. _Runtime_: It can be observed that the MCTSLKH_TR algorithm requires a longer run-time compared to the GreedyLKH_TR algorithm under the same scenarios. However, this disadvantage is acceptable as it still promptly meets the user's needs. According to the time complexity of the LKH algorithm, which is approximately O(n\({}^{2.2}\)) [29], theoretically, the MCTSLKH_TR and GreedyLKH_TR algorithms both have time complexities ranging from O(n\({}^{2.2}\)) to O(n\({}^{3.2}\)). However, the MCTSLKH_TR algorithm only requires a constant number of complete itinerary planning iterations, with the remaining cases only needing to find eligible solutions. This significantly shortens the runtime and can be further accelerated through hash tables. Therefore, the time complexity of the MCTSLKH_TR algorithm is superior to the GreedyLKH_TR algorithm, and it is foreseeable that as the problem scale increases, the runtime required by the MCTSLKH_TR algorithm will outperform the GreedyLKH_TR algorithm.