# Personalized Tour Itinerary Recommendation Algorithm Based on Tourist Comprehensive Satisfaction
## 4 Method
### Time Planning Algorithm Based on Tour Itinerary Planning Satisfaction
An attraction is considered unable to be visited if, upon arrival at the node, it is already past the last entry time for that attraction within the planned travel time. 4. The actual duration of attraction visits planned in the itinerary (\(AVisDur\)). 5. The ratio of \(AVisDur\) to expected visit duration (\(AEVDurRatio\)). The difference between the two values stems from late arrivals at attractions. 6. The itinerary penalty (\(Penalty\)). 7. Tour itinerary planning satisfaction (\(TPSS\)). Due to the inability of the LKH algorithm to produce evaluation metrics beyond the route cost and the evaluation metrics of the LKH_TW algorithm results not encompassing the dining and accommodation time of tourists, for the sake of uniform evaluation criteria, the solution proposed in this paper was adopted as the standard. For the itinerary planning results obtained using the two baseline algorithms, evaluation metrics other than the route cost were calculated using the time planning algorithm proposed in this paper, according to their visiting order. The results of the evaluation metrics are shown in Table 5, and Table 6 analyzes the sources of penalties for each algorithm in the cases (the values in parentheses represent the original results of \(AVisDur\), \(Penalty\), and \(TPSS\)). We analyze the results as follows:

1. _TravelT_: The LKH algorithm achieves the lowest value in all three cases. The LKH_TW algorithm and the proposed method are roughly comparable, but there is no significant enhancement compared to the LKH algorithm. This is because although our objective function does not directly consider route costs, the extent to which routes can be sacrificed to improve the time spent at attractions and itinerary feasibility is limited. In the optimization scenario of the algorithm, time constraints will restrict unreasonable routes. 2. _Timeout_ and _UnableVisit_: Except for Case 1 where all three algorithms provide eligible results, only the proposed method offers eligible results in the remaining cases. In Case 2, the LKH algorithm misses one attraction, while the LKH-TW algorithm exceeds the planned travel time. In Case 3, both the LKH and LKH-TW algorithms miss two attractions. This indicates that the itinerary planning results provided by the two baseline algorithms are likely to be unreasonable in reality. Moreover, as the travel duration increases and the number of itinerary nodes grows, the probability and severity of unreasonable results tend to escalate. 3. _AVisDur_, _AEV DurRatio_, _Penalty_, and _TPSS_: It can be observed that, due to there being fewer constraints, the original _TPSS_ of the results from the LKH_TW algorithm is superior to that of our proposed algorithm, indicating a higher attraction visit time or fewer penalties. However, under unified time planning, its results are comparable to those of the LKH algorithm, resulting in significant losses in attraction visit time and penalties for waiting and late arrivals. This is because it overlooks the necessary dining time expenditure for tourists during travel and does not consider rest and accommodation time in the itinerary based on specific circumstances. This can lead to a disconnect between visitors' actual experiences during travel and the planned \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Case**} & \multirow{2}{*}{**Algorithm**} & \multirow{2}{*}{_Penalty_} & \multicolumn{6}{c}{**Source of Penalty**} \\ \cline{3-8}  & & & _WaitP_ & _LateArrP_ & _MealDeviaP_ & _MealReduP_ & _RestDelaP_ & _PlysFatiP_ \\ \hline \multirow{3}{*}{1} & LKH & 9 & 9 & & & & \\  & LKH\_TW & 13 & & & 8 & 5 & \\  & LKH\_TP & 9 & 9 & & & & \\ \hline \multirow{3}{*}{2} & LKH & 88 + M & 71 & M & 8 & & 9 \\  & LKH\_TW & 344 + M & 112 & 217 + M & 15 & & \\  & LKH\_TP & 68 & 2 & 32 & 25 & & 9 \\ \hline \multirow{3}{*}{3} & LKH & 231 + 2M & 119 & 2M & 59 & & 53 \\  & LKH\_TW & 268 + 2M & 158 & 66 + 2M & & 44 & \\ \cline{1-1}  & LKH\_TP & 189 & & 45 & 15 & 120 & 9 \\ \hline \hline \end{tabular}
\end{table}