标题 | 基于旅游互动平台的线路规划 |
范文 | 邱智麟 黄云 摘要:为帮助旅行者更好的规划旅游线路,以旅行者对这次旅游所能投入的金钱和时间为约束条件,通过对含有位置信息的图片聚类得出当前季节热度最高的景点,然后利用汉密尔顿最短回路算法得出满足条件的路径。 关键词:路径规划;最短路径;汉密尔顿回路;聚类;动态规划 中图分类号:TP312 文献标识码:A 文章编号:1009-3044(2018)08-0172-03 1引言 现在人们在休息时间大多选择出外旅行,这样不仅可以增加和同伴之间的感情,也可以增长自己的见识,放松自己的身心。然而在选择景点的时候,只考虑了哪个景点好玩,没有考虑景点间的路程,因而花费了大量的时间奔走在景点之间。很显然,如果将路径规划应用于此,将减少人们在行程中花费的时间,从而有更多的时间游玩景点。路径规划是指,在具有障碍物的环境中,按照一定的评价标准,寻找一条从起始状态到目标状态的无碰撞路径。也就是说,给定起点和终点,一些约束条件,那么可以返回一条通过各个景点的最短路径。现在也有很多的应用实现了路径规划。如百度地图,可以通过指定起点和终点,出行方式,百度地图返回一条最短路径,而且有考虑当时的交通状况。但是人们出外旅行往往会选择很多的景点,有时甚至不知道该去什么景点,那么路径规划算法就不仅需要考虑所有的景点之间的联系,还要考虑到什么样的景点应该在这条路径上。因为百度地图面向的用户群并不是游客,所以景点推荐功能做的并不完善,只推荐了非常热门的景点,然而很多游客并不看重景点的热门度。携程网上有很多旅游攻略,大多是由本地人所写,所以行程安排可以安排得很妥当,但是攻略数量非常多,这对游客来说,需要阅读大量文章才可能找到一条符合自己期望的路线,这浪费了很多的时间,而且攻略质量参差不齐。总的来说,问题可以总结为以下几点: a)知名景点的资源信息过载而不知名的景点却缺少关注,导致了热门更热,冷门更冷。 b)没有提供一些旅游线路的推荐,传统的地图软件只能从快速便捷的角度推荐一些行走路线,并没有考虑旅游实际过程中(如天气改变)游客的感受等一些问题,这就将导致游客的旅游体验大大下降。 c)网上的资源质量参差不齐,容易误导游客。 随着互联网和智能手机的快速发展,越来越多的游客习惯用手机拍摄景点并分享到自己的朋友圈,于是,便产生了大量含有重要信息的图片,信息包括照片拍摄的位置,时间,其他用户对照片的评分等,这些信息反映了游客的行为模式以及景点的流行度,这为路线规划提供了巨大的帮助。 在现有的线路规划方法中,大多是以用户的GPS轨迹,带有位置信息的图片,旅游攻略为基础,来规划线路。于是,针对以上提出的问题,并结合基于旅游的互动平台的各种数据,我们提出了新的解法。问题假设我们从某一起点出发,最终回到起点,其间经过的路程最短,景点总体风景值最高,并且没有超过用户规定的时间和金钱。具体定义见第三章。其主要流程如图所示。 为解决资源质量参差不齐的情况,我们从网络上爬取大量攻略,将其转换成景点资源描述三元组然后从旅游互动平台上获取带有位置信息的图片,将景点的位置和图片的位置一起进行聚类,得到一个人气很高的景点集合,而不再是那些典型的景点。然后用贪心算法筛选出即满足用户时间约束,也满足金钱约束的景点,最后以景点间的距离为权重,采用哈密顿最短回路方法规划景点间旅游顺序。这样便解决上面说明的问题。 综上所述,本文的主要贡献如下: a)针对景点的季节性以及用户多样的需求,提出了更加完善的路线推荐。 b)不仅考虑了知名景点,也考虑了冷门但好玩的景点。 c)解决了网上资源质量参差不齐,推荐景点不准确的问题。 本文组织结构如下:第二章综述相关研究工作;第三章为问题解决步骤;第四章为结束语。 2相关工作 文献1设计改进了一种基于攻略中景点词频的先分组再定路线的启发式旅行线路规划策略,即首先基于旅游攻略中所提景点频数对景点进行受欢迎程度的排序,然后根据旅行时间、景点类型、景点间距离等过滤条件使用点分配聚类方法将景點进行聚类,最后再在各类中规划最优路线。最终证明了这种启发式策略使得旅行线路的时间分配更加均匀,景点间路程更短,线路的游览时间与景点间距离的费效比更高。因此文献1具有很高的实用价值。但是文献1重点并不在于研究如何规划各个景点间的具体的最优行进路线,而是研究各个景点的游览顺序,以满足线路中各景点间的路程最短,衔接的时间最小。 文献2则是通过大量多源异构的众包数据对路段风景值进行评分,利用基于规则的路线规划算法,在整体路线长度约束下,增加一个或多个风景路段,达到找出起点和终点之间的近似最优风景路线的目的。实验表明,这种方法有效地提高了整体路线的风景值。 文献3则考虑了群体旅游路线推荐,通过研究用户偏好,给出一条整体满意度最高,线路风景值最佳的线路。以上策略存在的一个问题就是没有考虑用户多样的需求,如用户出游的时间,需要花费的金钱等,文献[1-3]只是将风景值高的景点以最短的路径连接起来推荐给用户,这样大大降低了用户的旅游体验。 文献[5-6]则是模拟游客游览全国201个5A景区,很明显,并不是所有的游客都想去游览全国201个5A景区,但是文献[5-6]提出了基于多目标优化的旅游模型,也就是说考虑了用户很多的需求,如游客的出行工具等,这为本文提供了思路。 3解决步骤 3.1数据特点分析 本文的景点信息来源于网络。原始数据具有时间相关,位置相关以及非结构化特征。具体说明如下。 (1)时间相关:时间相关是指原始数据中含有大量与时间有关的信息,如景点参观时长,景点开放时间等。 (2)位置相关:位置相关是指原始数据中含有景点位置,地点名词等信息。 (3)非结构化:对于原始数据,是通过网络爬虫直接获取网页的html文件,其中包含了大量的无用信息,不具备结构化特征,因此需要将其转换。 另外,本文还是用了来自基于Map的旅游平台的数据,主要是包含了位置,时间信息的图片。 3.2原始数据的结构化表示 原始数据的结构化表示是指将需要的数据提取出来,选择合适的数据结构来表示,这样方便于程序设计。根据本文的需要,使用并改进了文献中的景点表述三元组来建立景点信息库。如下表所示,其中url为景点的唯一标识。 3.3聚类 聚类的目的是为了找出热门的景点,因此提出一个假设。如果某个区域分布的照片数量越多,那么该区域的风景质量越好。有日常经验可知,如果人们外出游玩,遇到了一个风景优美的地方,都会通过拍照来记录这个地方,因此,如果某个区域的照片数量非常多,那么这个区域定是一个风景优美的景点。 于是,通过分析照片的空间分布,可以得出热门景点的分布。本文采用的方法是一种基于密度的聚类算法,它能够将足够高密度的区域划分为簇,并且可以在具有噪声的数据中发现任意形状的簇。由上文可知某个区域图片密度越高,就也有可能是一个景点。所以DBSCAN算法符合我们的要求。主要步骤如下。 (1)解析含有经纬度的数据文件,用合适的数据结构缓存到内存中。其中有照片的经纬度,还有景点的经纬度。 (2)计算每个点与其他点之间的欧几里得距离。 (3)计算每个点的K-距离值,对K-距离值集合进行排序。 (4)将K-距离值用散点图的形式表示出来。 (5)根据散点图确定半径Eps的值。 (6)根据MinPts=4和Eps的值,计算所有核心点,并建立核心点与到核心点距离小于半径Eps的点的映射。 (7)根据得到的核心点集合,以及半径Eps的值,计算能够连通的核心点,并得到离群点。 (8)将能够连通的每一组核心点,以及到核心点距离小于半径Eps的点,都放到一起,形成一个。 (9)遍历每个簇,如果其中包含了已知的景点,则将该景点放入集合,如果没有,则说明这是一个未发掘的景点,任取一点放入集合。 具体步骤如下: 图中的点即为图片的拍摄位置,图中含有两个簇,即两个景點,景点范围内照片数量计算公式为: N(i)=簇内的点的数量 景点的评分公式为: (1)初始化。根据需要初始化总金额money和景点数i,以及每个景点的评分grade[i],每个景点的门票钱moneyNeeded[i]和一个空集合,来存放合格的景点。 (2)当i等于0时,也就是浏览最后一个景点时,如果当前剩余的钱能够购买门票,返回这个景点的风景值并将此景点加人集合,否则返回0。 (3)当i不等于0时,可以选择浏览此景点或不浏览,取最大值作为此景点的风景值,并且将最大值对应的景点加入集合。 (4)如果当前金额少于门票钱,则跳过当前景点。 到此,我们找出了所有景点门票和不超过用户的规定金额,并且景点评分综合最高的一组景点组合。 3.5景点的季节性 由上一小节可知,我们已经得出了门票总和不超过用户规定金额的所有景点集合,因为景点带有季节性,所以我们只比对景点的季节性和用户旅游时间所在的季节,如果不同,则将该景点从集合中剔除。此功能看似简单,然而确实各个旅游平台路线推荐时没有考虑到的。这也是本文的亮点所在。 3.6线路规划方法 根据假设,我们从起点出发,经过所有的景点仅且一次,最终回到起点,这是典型的汉密尔顿回路问题。又因为我们希望总路程最短,以景点间的距离作为权重,所以该问题演变成了赋权汉密尔顿回路最小化问题。具体定义如下。给定i个点及i个点两两之间的距离,求一条回路,使之经过所有的点,且经过每个点仅一次,而整条回路的总距离最小。具体解决办法见文献4。 4结语 旅游已经是人们生活中一个必不可少的组成部分,而线路规划是开始旅游前面临的一个非常重要的问题,本文通过对照片的位置进行聚类分析,得出风景值高的景点,然后运用动态规划策略得出在不超过用户的限定金额下的风景值总和最高的风景点集合,然后通过哈密顿最短回路算法得出路径。 |
随便看 |
|
科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。