Abstract: With the problem that route planning of tourism determines success or failure for travel of tourists by self-driving, the network optimization problem of tourism route planning was solved by using the idea of optimization of partitioning block and layer. The weighted graphs of partitioned network were constructed by using the idea of weighted graph and the nearest neighbor clustering algorithm to divide the scenic spots, and an improved TSP optimal model was established to plan the tourist routes of the scenic spot in the block for self-driving travel,which considers the travel time and driving time as well as visiting time during every time travel process. Then, an improved MTSP optimal model was established by treating each block as a note, treating the travel time of the block as one of the time weights, moreover tourist routes among blocks for self-driving travel were planned by using the simulated annealing algorithm. Next, the one-dimensional Bin Packing(BP)model to solve the minimum number of total tourism years was established through the idea of analogy one-dimensional Bin Packing problem, and whose minimum value was obtained by using cross filling algorithm. Finally, the optimal tourist routes that subjects to multiple constraints were planned for a travel enthusiast by self-driving in Xi’an City who travels through 201 5A level scenic spots in china with applying the proposed method in this thesis.

Key words: network optimization, TSP model, one-dimensional packing model, simulated annealing method, cross filling algorithm

摘要： 针对旅游路线规划决定着自驾旅游者的旅游成败问题,利用分块分层优化的思想解决了旅游路线规划这一网络优化问题。用赋权图和近邻聚类的思想构建分块网络加权图,建立考虑旅游时间、行车时间和游览时间的改进旅行商优化模型,规划区块内景点的自驾旅游路线;然后将各区块视为节点、区块间旅游时间作为时间权值之一,建立改进的多旅行商优化模型,并用模拟退火算法规划出区块间的自驾旅游路线;其次,用类比一维装箱问题的思想,建立了求最少旅游年数的一维装箱模型,并用交叉装填算法求得其最小值;最后,应用提出的方法为西安市的自驾旅游爱好者规划出了满足多种约束的游遍全国201个5A级景区的最佳旅游路线。

关键词: 网络优化, 旅行商模型, 一维装箱模型, 模拟退火法, 交叉装填算法