1、 本科毕业设计(论文)论文题目 基于人群密集度旅游景点最佳路线生成的研究与实现 Research Of Generate Tourist Areas Best Route Based On Population Density基于人群密集度旅游景点最佳路线生成的研究与实现摘要: 随着经济的快速成长，居民收入水平和消费需求都大大提升，外出游玩成为了百姓们的重要生活方式之一，也是大众消费的主要载体。根据我国国家旅游局的预测，直到 2015 年，中国将要成为世界最大的国内旅游市场。因此，提出一个可提供最佳旅游服务的解决方案非常有必要，充分利用最少的时间，在最佳的时间和路线上，得到最大的旅游享受，让旅
2、行的路途中免去烦心的等待和拥挤，不再让节假日旅游里的美丽花海变成人山人海。在旅游的过程中，如果有了智能旅游最佳路线指导，也将大大方便旅游区管理人员的安全保障工作。很多的旅游过程中不安全的因素都可以减少，这也有利于打造一个和谐大同的世界。本课题主要研究旅游过程中的景点路径标识、旅游景点的最佳路径生成、最佳路径相关信息的显示以及管理界面的 UI 交互等。旅游景点的最佳路径生成的核心是应用最短路径生成算法，即 Dijkstra 算法。具体方案是将人口密集度参数和景点距离做权重比处理，得出一个较为满意的最佳路径，生成并展现给用户查询。本课题分析的是一个低成本、高性能的最佳旅游路线指导系统。关键词：旅游
3、；最佳路线；人口参数；路线指导RESEARCH OF GENERATE TOURIST AREAS BEST ROUTE BASED ON POPULATION DENSITY Abstract: Along with development of national economy, the residents income and consumption demand, tourism became a national important lifestyle and “mass consumption“ important carrier. According to the nationa
4、l tourism administration forecast that by 2015, China will become the worlds largest domestic tourism market.Therefore, one can provide the best solution is very necessary, make full use of the least amount of time, in the best time and route, biggest tourist enjoyment, make travel journey from both
5、er waiting and crowded, not to let the beautiful flowers in the holiday travel into a sea of people. In the process of travel, if there is the best route guidance of intelligent tourism, will greatly facilitate tourist area, the security management work. Many unsafe factors in the process of tourism
6、 can be reduced, this also is helpful for building a harmonious world.This topic main research of tourist attractions in the process of path identification, tourist attractions best path generation and the best path information display and management interface UI interaction, etc. Tourist attraction
7、s at the heart of the best path generation is generated by the shortest path algorithm Dijkstra algorithm. The densely populated parameters and attractions do weight than handling distance, it is concluded that a more satisfied with the best route, generate and show to the user query. This topic is
8、a low cost, the analysis of the best travel route guidance system with high performance.Keywords: travel; the best route; population parameter; route guidance目 录1 绪论 .11.1 课题的研究背景和意义 .11.2 国内外研究现状和发展趋势 .21.2.1 国内外研究现状 .21.2.2 发展趋势 .22 最佳路径生成应用总体方案设计 .32.1 功能和需求分析 .32.2 总体结构 .32.3 最短路径算法的比较选取 .42.4 本
9、文研究的主要内容 .53 最佳路径生成应用的实现 .53.1 最短路径计算 .53.1.1 景点设置 .63.1.2 数据管理 .73.2 最佳路径生成 .83.2.1 人口参数的获取 .83.2.2 权重比计算 .93.3 用户操作界面 .103.3.1 用户信息输入 .103.3.2 用户信息查询 .113.4 管理员操作界面 .124 实验结果与分析 .124.1 最佳路径生成显示 .124.2 管理员权限操作 .144.3 后台数据处理 .145 结束语 .15致 谢 .16参考文献 .16附 录 .17浙江传媒学院本科毕业论文 基于人群密集度旅游景点最佳路线生成的研究与实现第 1 页
10、 共 27 页1 绪论随着我国国民经济的不断成长，2010 年中国俨然成为了全球第三大经济体。同时，城乡居民收入和平时生存质量明显有了很大的进步。跟随百姓们的经济延续快速成长，居民收入水平和他们的消费需求都大大提升，外出游玩成为百姓们的重要生活方式之一，也是大众消费的主要载体。通过这些发展实践我们得知，人均 GDP 达 30005000 美元这一阶段是游览休闲等发展型、享受型消费的一个爆发期 1。于是就很自然地，旅游行业作为现代服务业的代表在近些年里发展十分迅猛。1.1 课题的研究背景和意义国家旅游局最新公布的统计数据可以表现出，到 2015 年为止，中国国内的旅游人数估计会到达 33 亿人次
11、，国内人民人均旅游率将上升至 2 次以上，旅游的消费将等同于居民消费总量的 10%2 。依照国家旅游局拟定的发展旅游业十五计划的基本思路来看，到 2020 年为止，中国海外旅游外汇的总收入将会在 580 亿美元以上。而与此同时，国内的旅游将会上升到 29亿人次以上，国内旅游的收入将会升至 20400 亿元人民币以上 3。国际旅游理事会已经预测出，到 2020 年为止，中国旅游消费和旅游投资都接近世界平均水平，旅游业总收入将占中国国内生产总值的 8.64%4。从经济水平上来说，旅游业发达就可获得更多的外汇收入，增加 GDP；对于社会，旅游业帮我们增加了就业机会，它有利于文化遗产的保护、传承；最重
12、要的是，旅游业一直被称为无烟工业，它相对于工业和其它产业来说，对于环境的破坏力度确实要低很多 5。在中国旅游业如此发达的情况下，人们每年可以旅游的节假日却并不多。1999 年 9月 18 日由国务院发布实施了全国年节及纪念日放假办法，并且明文规定了，全体公民放假的假期，如果正好赶在星期六和星期日，那么就应该在工作日的时候进行补假 6。这样的话，在每年春节、五一、十一全体公民度假的 3 天时间里，若加上前后两个周末双休的倒休，于是就形成了每年的那三个假期黄金周。综上所述，正是因为旅游的需求伴随着假日周期的变化而上下波动，所以在这种情况下很多问题就会出现，从而引发旅游市场的供给不平衡，形成供需结构
13、的矛盾 7。在今天，假日旅游作为这样一种集中的休假方式，非常容易使得旅游景区变得人满为患了。对待这类问题，如果我们不去防微杜渐，那么将会对旅游行业的健康发展产生很多负面效应。因此，一个可以提供最佳旅游的解决方案非常有必要，充分利用最少的时间，在最佳的时间和路线上，得到最大的旅游享受，让旅行的路途中免去烦心的等待和拥挤，不再让节假日旅游时候的美丽花海变成人山人海。在旅游的过程中，如果有了智能旅游的最佳路线指导，也将会大大方便旅游景区管理人员们的安全保障工作。旅游过程中不安全的因素很多都可以减少，这也有利于打造一个和谐的世界。浙江传媒学院本科毕业论文 基于人群密集度旅游景点最佳路线生成的研究与实现
14、第 2 页 共 27 页1.2 国内外研究现状和发展趋势“假日旅游”问题变得日益严重，旅游管理也因为这个原因越来越受重视，国内外已经有许多的研究机构渐渐开始对相关的技术进行了很多研究。而对于人流高峰的问题，不仅仅是旅游，而且在交通等方面也备受关注。近几年来，伴随着物联网、云计算，还有三网融合等新一代的信息技术的飞速发展，“智慧城市 ”已经成为了城市发展的新方向，并且也已经在世界范围内掀起了建设的热潮 8。我们相信，“ 智慧旅游” 将会彻底完全地改变我们的传统旅游行为、旅游方式，它会融入到我们的企业经营模式和旅游管理模式之中，“智慧旅游”将会引领旅游进入智能的时代，带着我们迈入智慧生活 9。1.
15、2.1 国内外研究现状 2009 年期间，德、英这两个公司在欧盟的资助下协同开发过一款智能的导游软件，它主要以“增强现实 ”的技术为设计基础，让游客们可以通过声、光和影像，来“亲身”体验那些已经被遗忘了的历史时光 10。这个软件还可以实现路线规划的功能，它可以通过交互式路线规划的一些工具，来量身定做出一个专门贴合游客需求的旅行方案，可以帮助游客远离大众的线路，可以按需独辟蹊径，就完全相当于一个良好的全职导游 11。 2013 年，韩国也推出过一种基于智能手机平台而开发的“I Tour Seoul”的智慧旅游的服务系统 12。这个系统是韩国特地为旅游者们提供的一个掌上移动旅游信息的服务平台。通过
16、这个平台，旅游者们可以实时地获得旅游者当前所在的地方旁边的所有相关的旅游信息。还有一个美国旅游网站 Priceline，在当时曾因为“客户自我定价系统”名噪一时 13。传统的旅游销售都是由商家提供适当的价格，消费者进行选择，而 Priceline 网站却改而采用了由消费者定价格，然后再根据具体情况。Priceline 网站属于那种典型的网络经纪服务，依靠替买卖两方提供信息平台而提取一定的佣金。 1.2.2 发展趋势在这么多智慧旅游的出行指导系统和软件里面，主要技术实现上包括了最短路径算法和 GPS 技术等研究成果，这些高科技产品都是科学家们辛苦研究的成果。从前面国内外旅游指导软件和系统的发展现
17、状来看，目前旅游出行指导系统正在向智能化、网络化的方向迈进。虽然旅游引导系统已有了一定的实验成果，但却仍然存在着很多的问题需要解决，技术上离完全成熟还是有一定差距的。例如在人性化的设置；旅游事件中所有信息的真实性，及时性和可靠性这些方面都还有所欠缺。最短路径问题是可以适用于各种领域的其中最基本的问题之一，并且它和路线导航系统有着密切的关系 14。这个重要问题最早在 20 世纪初就已得到了人们的高度重视，那个时候也有很多的科学家来研究这个重要问题的解决办法。但是一直到 1959 年，荷兰计算机科学家迪杰斯特拉的出现，这一问题才得到了求解的基本思想，并产生了相应的算法。那个时候的迪杰斯特拉提出的这
18、个算法它主要用作解决的问题是：从一个固定的点到其他所有的点的最短路径问题的求解 15。后来慢慢地这个算法不断改进，就成了众所周知的迪杰斯特拉算法，这个算法也成为了一代经典。浙江传媒学院本科毕业论文 基于人群密集度旅游景点最佳路线生成的研究与实现第 3 页 共 27 页在今天比较流行的求解最短路径规划的算法主要有下面三大类：第一种算法是基于图论理论的算法；比如迪杰斯特拉算法及其改进算法，比如 Floyd 算法等等；第二种算法是理论上基于传统人工智能的一种算法，比如 A 机器算法及其改进算法，比如宽度有限算法，比如深度有限算法等等；第三种算法则是建立在智能控制技术的基础上而开发的算法，比如遗传算法
19、，比如人工神经网络算法等等 16。在这里比较值得一提的是，近几年来智能控制技术在路径规划的问题上得到了很广泛的应用，所有都向智能化靠齐。因此人们的研究兴趣也逐渐地从对前两类算法的不断改进而转移到了对第三种算法的进一步开发研究中。2 最佳路径生成应用总体方案设计2.1 功能和需求分析考虑到此应用的适用场合和必要功能，本次设计出的应用需要具备以下功能：（1）用户信息输入功能，即表示用户此时所在地信息；（2）用户信息查询功能，即最佳路径查询；（3）管理员权限操作功能。（4）数据获取和更新功能。2.2 总体结构本次设计是基于该旅游景点应用的功能需求，来确定应用的结构设计，制作了这种旅游景点最佳路径生成
20、的应用。它是以 PC 为操作环境的，结合最短距离的计算，可提供用户和管理员多身份使用的操作界面，是完成出行指导、路线提示的比较好的现代化设备。系统架构：系统架构分为三层。最底层为数据获取；利用网络端口与本地存储系统所需数据，可供业务层使用；中间层为业务层,该层根据需要；按照各种逻辑，读取、组织数据；并向用户输出所需结果；最顶层为表示层，它体现了 UI 交互功能，并为不同的使用者提供不同的业务层服务。本文总体设计方案如图 2-1 所示。表示层用户查询界面 管理员操作界面业务层数据获取地图服务 最佳路径生成 数据操作地图数据景点数据线路数据摄像机数据图 2-1 总体方案设计浙江传媒学院本科毕业论文
21、 基于人群密集度旅游景点最佳路线生成的研究与实现第 4 页 共 27 页2.3 最短路径算法的比较选取就目前而言，关于最短路径求解的相关研究主要有两方面。第一方面是最短路径问题。在拥有完全信息这种确定情况下对于最短路径求解问题的研究中，迪杰斯特拉，Bellman和 Dreyfus 早已经发展出了很多高效的算法。这些高效的算法已经成为了确定情况下的经典首用算法。而在不确定的时候最短路径求解的问题又包含了以下几个方面：Merchantman 以及 Frank 研究出了路段长度可随机变化的、在非时间独立情况下求解最短路径的算法；另外 Sara、 Laue 和 Mouthy 也研究了考虑在不同的费用情
22、况下实现函数最短路径的问题，他们得出的结论是：在期望最短路径时，可以把问题转化成为将边的权重当作期望值来表示以求解出最短路径问题；Tomas 和 Rajeev 也研究出了路段长度为区间范围时候的最短路径求解问题。常见的几种最短路径求解算法的优缺点比较如下：（1）A 算法A 算法是人工智能之中的一种比较典型的启发式搜索算法，这个算法的创新之处在于它选择了下一个被探索的结点时引入了已经知道的路网信息和目标点信息，对于当前点和终点的距离进行适当评估，用来作为选择下一路路径结点的依据。普通 A 算法一般都会采用四方向或者八方向，我们对矢量路网一般采用遍历相连的一种路径法来进行路径探索。一般来说，在城镇
23、的地价定级估价当中，如果不去考虑路网，完全可以采用栅格八方向的方法。而如果通过 A 算法，就可以寻找到任何一个因素因子和其它的各点之间的最短路径了。A 算法不需要找遍整个的搜索空间，只需要根据用户所选择的启发式函数，然后朝着最有可能的方向前进。A 算法相对而言搜索速度比较快，理论上也可以找出最优解，但是在实际的应用过程中，经常会因为选取不正确的启发式函数而导致找不出最短路径，所以往往搜索的成功率并不是特别高。（2）遗传算法遗传算法(简称 GA，Genctic Algorithms)是模拟自然淘汰（达尔文理论）以及遗传选择的进化过程的一种计算模型。遗传算法的主要思想是依照着生物遗传学的自然规律，
24、它是一种具有“生存+检测” 的迭代过程的搜索算法。遗传算法会把每一个有可能的结果解编码成为一个向量，再把每一个向量称为一个染色体，而向量的每一个元素都称为这个染色体的基因。那么所有染色体就可以组成群体。遗传算法按照预定好的目标函数，针对每一个染色体进行估计，按照估计结果可以得出一个适应度的值。遗传算法在最开始的时候先随机地产生一部分染色体，分别计算出它们的适应度，然后再根据这些适应度对所有染色体不断选择、变异、交换等，除去适应度较低的染色体，最后留下适应度较高的染色体。因为新群体的成员都是上一代群体留下来的优秀者，所以在总体上比上一代优秀。遗传算法就是这样反复更替，一直到最后满足了某种预定的优
25、化指标为止。（3）Dijkstra 算法然而经典算法迪杰斯特拉算法却不一样。它的基本思想是先将所有网络结点都分成三部分: 未标记的结点、临时的标记结点和永久的标记结点。在网络中所有的结点首先都要初始化为未标记的结点，然后在搜索的过程中，和最短路径中的结点相互连通的结点作为浙江传媒学院本科毕业论文 基于人群密集度旅游景点最佳路线生成的研究与实现第 5 页 共 27 页临时的标记结点，那么每次循环都要从临时的标记结点中搜索距离目标源点路径长度最短的那个结点，以作为永久的标记结点，一直到找到目标结点或所有的结点都已经成为永久的标记结点，最后结束算法 17。最短路径算法一直以来都是计算机科学和地理信息
26、科学等科研领域所研究的热门话题，有关于它的算法有很多种，其中一种就是传统的迪杰斯特拉算法，它一般情况下都被用于计算出一个固定的节点到所有的其他节点的最小等价路径，且这个算法完全能适应网络拓扑的突发变化，其性能稳定，所以这个算法可以在运输路线规划等领域都应用广泛。所以本文所选取的算法也是迪杰斯特拉算法。2.4 本文研究的主要内容本课题主要对旅游景点最佳路线生成的研究进行设计分析，主要研究旅游过程中的景点路径标识、旅游景点的最佳路径生成、最佳路径相关信息的显示以及管理界面的 UI 交互等。具体如下：（1）首先需要的是获取该旅游景点的地图作为系统应用的背景图片。第一步要做的就是标识出景点实际位置，给
27、出景点间的实际路线，使用户可以通过本系统应用得到关于该景点路线上的信息；（2）然后需要研究出最佳路线生成的方法。本系统设计的方法是最短路径算法和人口密集度参数的权重考虑，在综合考虑这两个因素的情况下，分配不同的权重比，就可以得出一个用以衡量是否为最佳路线的数值。对于最短路径的生成，本系统采用了 dijkstra算法； （3）而对于人口密集度参数，理论上是从已有的摄像头相关应用中获得，可以连接上网络端口然后通过网络获取相关人口密度的数据。所以该研究如果在现实中应用，还需要通过网络端口实时接收相关的数据。也就是需要确保在一定时间频率内，该应用可以获得新的数据，这样才可以实时地计算出每段时间里的最佳
28、路径，给用户真正正确的路线指导；（4）最后需要设计出一个相对较好的用户 UI 界面。界面设计包括用户路线查询界面，管理员登陆界面，管理员数据管理界面，管理员项目增减界面。本次研究需要考虑到旅游区景点的更换情况。如果某条路径发生变化，希望可以实现由管理员来操作改变系统的提初始设置。（5）最后需要对实验结果进行分析和改正，包括对应用调试过程中遇到的问题的解决，以及对未来的展望和实现。3 最佳路径生成应用的实现3.1 最短路径计算本次研究所采用的最短路径算法是迪杰斯特拉改进算法。迪杰斯特拉算法的主要解决的思想是，首先把所有的网络分结点划分为三部分：未标记的结点、临时的标记结点和永久的标记结点。然后在
29、路径网络中，所有的结点首先都必须要先进行初始化，也就是都要划分为未标记的结点，这样的话，那么在搜索过程中我们就要将与最短路径中的结点连通浙江传媒学院本科毕业论文 基于人群密集度旅游景点最佳路线生成的研究与实现第 6 页 共 27 页的那个结点作为临时的标记结点，在计算最短路径时，每次循环都要从临时的标记结点中搜索距离源数值，将路径长度最短的那个结点作为永久的标记结点，一直到找到了目标结点，或者所有的网络结点都成为了永久的标记结点，就可以结束算法 18。这就是该算法寻找最短路离的核心思想。最短路径的计算过程如下：（1）起初的时候让 S=V0，T=其它顶点 ，T 中含有顶点对应的距离数值。如果存在
30、 ，d(V0,Vi)就作为弧上的权值；如果不存在 ，d(V0,Vi)就为。（2）从 T 中选出一个其距离值是最小的那个顶点 W，且不在 S 中，把它加入 S。（3）对于其余的 T 中顶点的距离值进行适当修改：如果加入进 W 作为中间顶点，从V0 到 Vi 的距离值出现缩短，那么就修改这个距离值。（4）不断重复上面所说的步骤 2、3，一直到 S 中包含的所有顶点，即 W=Vi 就截止。最短路径算法效果图如图 3-1 所示。图 3-1 最短路径算法效果图3.1.1 景点设置由于此程序是试用研究，所以本次选用了一个较小的景点，也就是浙江西湖的一部分作为景点设置。具体步骤是：首先打开百度地图，找到浙江杭州西湖，然后找出一些相应景点，把景点做上标记，并用 ABCDEFGH 等分别标记每一个景点，用于程序语言的标记，即在应用程序里它们的出现方式。然后利用画图工具来把景点之间的路都标记出来。这些都是形象化的路径，并非实际路径的表现，所以只是将可以连通并存在可使用路径的两个景点连接起来，并标记出每条路实际距离。还有另一种解决方案。在路径表示和计算中，可以将每个景点的坐标都表示出来，即把界面变成一个二维坐标，以某一点为固定原点，这样就用二维坐标把每一个景点的位置
