Dynamic Programming-Based Travel Route Planning Model

Under China's 144-hour transit visa-free policy, an increasing number of foreign tourists aim to explore multiple cities in-depth within a limited timeframe. In this context, this paper proposes an intelligent route planning model based on dynamic programming. The model integrates the entropy weight method and TOPSIS to evaluate six categories of 12 indicatorsincluding climate, transportation, and cultural factorsto select the top 50 high-scoring cities. By incorporating high-speed rail transit time constraints, a dynamic programming algorithm is designed to optimize tourist itineraries. Experimental results demonstrate that the dynamic programming model covers 11 cities (e.g., GuangzhouShenzhenChangshaWuhanNanjingShanghai) within 144 hours (including 12 hours per city for sightseeing and 4 hours of buffer time), with a total duration of 123 hours, significantly outperforming the greedy algorithm (9 cities, 134 hours). Through state compression and pruning strategies, the model reduces computational complexity from factorial (O(n!)) to exponential (O(n2)), balancing efficiency and optimality. The study validates the models potential to enhance tourist satisfaction and tourism economic benefits, while suggesting future extensions to multi-modal transportation planning and dynamic preference adaptation.