基于TSP的旅游景点路线规划研究

论文总字数：31045字

摘 要

近年来，旅游业的发展和生活水平的提高使得利用小长假进行外出旅游成为人们的主流选择。良好细致的旅游路线规划是保证旅游质量的基础。本文主要研究了在旅行商问题的基础上建立路线规划的数学模型，通过蚁群算法进行求解，并以南京市旅游景点为例进行旅游路线规划。

首先，本文综述了旅行商问题和相关启发式求解算法。本文综述了旅行商问题的基本定义、数学模型和求解方法，并对求解该类问题的启发式算法进行理论回顾。

其次，本文分析了求解旅行商问题的蚁群算法和改进策略。本文从模型和算法实现等方面介绍蚁群算法，并对其易陷入局部最优的缺点，从信息素更新方式和参数选取提出改进策略，仿真实验结果表明性能有所提升。

最后，本文对小长假的旅游路线规划进行建模和求解。本文在旅行商问题的基础上改变目标函数和约束条件，建立了旅游路线规划的数学模型，并以南京市旅游景点为例，应用本文改进的蚁群算法对不同偏好的游客求解出路线规划。

关键词：旅游路线规划；旅行商问题；蚁群算法

Abstract

Recent years, due to the development of tourism and the boost of people’s lifestyle, utilizing a holiday to travel has become a mainstream choice. Good and detailed planning of tourist routes is the basis to ensure the quality of tourism. This paper mainly studies the mathematical model of route planning based on the traveling salesman problem, and solves the problem by ant colony algorithm, making the route planning by taking the scenic spots of Nanjing as an example.

Firstly, this paper reviews the traveling salesman problem and related heuristic algorithms. This paper reviews the basic definition, mathematical model and solving means of the traveling salesman problem, and reviews related heuristic algorithms to solve the problem.

Secondly, this paper studies ant colony algorithm and improvement strategy. This paper introduces the biological model and the implementation steps of ant colony algorithm. Considering that ant colony algorithm is prone to get into local optimal solution, this paper proposes an improved strategy for pheromone updating rule and parameter selection, and simulation results show that the performance is improved.

Finally, the tourism route planning for a vacation is modeled and solved in this paper. We change the objective function and constraint conditions on the basis of the traveling salesman problem, and establish the mathematical model of tourism route planning. Taking the scenic spots of Nanjing as an example, this paper solves route plans for tourists with different preferences by applying the improved ant colony algorithm.

Key words: Tourism Route Planning; Traveling Salesman Problem; Ant Colony Algorithm

目 录

摘 要 II

Abstract III

目 录 IV

第一章 绪论 1

1.1 研究背景与意义 1

1.2 国内外研究现状 1

1.3 本文主要内容和安排 2

1.3.1 本文拟解决的问题 2

1.3.2 章节安排与技术路线 3

第二章 TSP和启发式算法的理论回顾 5

2.1 旅行商问题（TSP） 5

2.2 求解TSP的启发算法概述 6

2.3 TSP与旅游路线规划的关联 7

第三章 求解TSP的蚁群算法及改进策略 9

3.1 生物模型 9

3.2 求解TSP的蚁群算法模型及实现 10

3.3 改进策略 13

3.3.1 信息素更新方式 13

3.3.2 参数选取 14

3.4 性能仿真分析 14

3.5 本章小结 17

第四章 基于TSP的旅游路线规划建模与求解 18

4.1 问题描述和分析 18

4.2 数学模型的建立 18

4.2.1 模型假设和简化 18

4.2.2 符号说明 19

4.2.3 模型建立 19

4.3 模型求解和算法实现 21

4.3.1 数据的收集与处理 21

4.3.2 问题的求解 23

4.3.3 求解结果 24

4.4 模型评价 28

4.5 本章小结 28

第五章 总结与展望 29

5.1 本文工作总结 29

5.2 研究展望 29

致 谢 31

参考文献 32

附录 南京市旅游路线规划 34

绪论

研究背景与意义

近年来，国民收入的提升和生活水平的提高使得人们利用小长假进行外出旅行的意愿逐渐提高，民众的旅游消费能力逐渐增强。如今，旅游业已是我国经济中十分重要的一环，其快速的发展也使得人们愈发注重自身的旅游偏好以及旅游的质量。

对于我国目前的旅游市场现状，有几项数据可以充分说明。首先是国家文化和旅游部的数据显示，2018年国内旅游人数55.39亿人次，旅游总收入5.97万亿元，二者增长率分别为10.8%和 10.5% ^[1]。此外，艾瑞咨询报告显示，2017年在线旅游市场交易规模达7384.1亿元，较上年增长25.1%^[2]。最近有关旅游的新闻中总能看见节假日景区拥挤、游客络绎不绝的现象。从这些数据和现象中可以看出，目前国内的旅游市场较为火热，应用互联网进行旅游消费的人数正逐年增加，总体来看旅游业具有较好的发展前景。

正是在这样的背景下，众多旅游网站纷纷建立，成为人们旅游前的必要参考之一。然而，目前旅游网站大多只进行景点推荐，提供景点的基本信息、交通情况及周边住宿餐饮情况，而很少涉及行程安排和具体的线路规划，游客往往只能根据前人的经验进行安排，需要花费大量的时间和精力，影响出行的体验。此外，传统的跟团游形式的旅游路线一般是旅行社设计的一条或多条固定的路线，通常也依赖于旅游经验，其设计需要耗费一定时间，且留给游客自主选择的余地较少。

剩余内容已隐藏，请支付后下载全文，论文总字数：31045字