硕士论文
摘 要
近年来,随着旅游消费观念的转变,越来越多游客选择自助旅行,但是面对陌生的景区,复杂的旅游环境,游客很难在没有向导引领的情况下完美的达到旅行目的.本文针对游客外出旅行中面临的旅游路线规划问题,利用图论和运筹学的思想,建立旅游路线规划的数学模型,综合考虑用户出行中的时间、空间等多种需求,实现旅游路线的规划,为用户推荐满足其个人需求的旅游线路.结合上述研究工作,基于 Android 平台完成了云龙湖自助旅游系统的设计和开发.本文主要研究内容如下:
(1)建立基于定向问题的旅游路线规划问题模型.通过对旅游路线规划问题进行系统分析,对比经典路线规划问题模型的优势和不足,选择定向问题作为基础模型.综合考虑景区旅游环境,作出合理假设,确定约束条件,对基础模型进行扩展,建立旅游路线规划问题数学模型.保证在满足总时间约束的条件下以最大化路线收益值为目标选择景点,这些景点构成最终的旅游路线.
(2)提出适用于旅游路线规划问题的改进 A*算法.根据问题需求和算法存在的不足,改进 A*算法的启发规则,算法规则中考虑景点得分以及总时间约束,并结合问题实际,以图最短时间作为算法需要的估计时间.通过实验表明,改进后的 A*算法与传统算法相比,得到的结果路线收益值更大且时间利用率更高,更适合于求解旅游路线规划问题.最后以云龙湖景区为例,使用爬虫技术收集景区数据,完成了景区内景点得分、景点游览时间、交通时间以及泊车时间等条件参数的合理量化,实现了景区内的旅游路线规划.
(3)设计并实现云龙湖景区的自助旅行系统.本文以云龙湖景区为应用实例,根据需求分析,设计自助旅行系统架构和功能模块,系统设计包含景点服务、旅行安全以及路线规划三大模块.以旅游路线规划问题的理论研究成果为基础,利用 Android 编程技术、百度地图 API 以及 GPS 定位技术,开发实现了基于Android 平台的云龙湖自助旅行系统,能够为游客提供景点介绍、路线推荐、电子地图等多种服务.
关键词:定向问题,A*算法,旅游路线规划,自助旅行系统
Abstract
In recent years, with the change of tourism consumption concept, more and moretourists choose self-service travel, but in the face of unfamiliar scenic spots andcomplex tourist environment, it is difficult for tourists to achieve the perfect traveldestination without guiding the collar. This paper aims at the travel route planningproblem faced by tourists during their travels, and uses the ideas of graph theory andoperations research to establish a mathematical model of travel route planning,comprehensively consider the time and space of users' travel, and realize the planningof tourist routes. And recommend travel routes that meet your individual needs. Combined with the above research work, the design and development of theself-service travel system was completed based on the Android platform. The mainresearch contents of this paper are as follows:
(1) Establish a tourism route planning problem model based on orientationproblems. Through systematic analysis of the tourism route planning problem,comparing the advantages and disadvantages of the classic route planning problemmodel, the Orienteering Problem is selected as the basic model. Comprehensivelyconsider the tourist environment of the scenic spot, make reasonable assumptions,determine the constraints, expand the basic model, and establish a mathematicalmodel of the tourism route planning problem. It is ensured that the attractions areselected with the goal of maximizing the return value under the condition of satisfyingthe total time constraints, and these scenic spots constitute the final tourist route.
(2) Propose an improved A-star algorithm for travel route planning problems. According to the problem requirements and the shortcomings of the algorithm, theheuristic rules of the A-star algorithm are improved. The scores of the attractions andthe total time constraints are considered in the algorithm rules, and combined with theactual problem, the shortest time of the graph is used as the estimated time requiredby the algorithm. Experiments show that compared with the traditional algorithm, theimproved A-star algorithm has larger return value and higher time utilization, which ismore suitable for solving route planning problems. Finally, taking Yunlong Lakescenic spot as an example, using reptile technology to collect scenic spot data, thereasonable quantification of the scenic spot scores, scenic spot tour time, traffic timeand other conditions were completed, and the tourism route planning in the scenicspot was realized.
(3) Design and implement the self-service travel system of Yunlong Lake ScenicArea. This paper takes Yunlong Lake Scenic Area as an application example.According to the needs analysis, the self-service travel system architecture andfunction modules are designed. The system design includes three modules: sightservice, travel safety and route planning. Based on the theoretical research results ofthe tourism route planning problem, through the Android programming technology,Baidu map API and GPS positioning technology, the Yunlong Lake self-service travelsystem based on the Android platform is developed and implemented, which canprovide visitors with attractions, route recommendations and electronic maps. Avariety of services.
Keywords: Orienteering Problem; A* algorithm; planning of tourist routes;self-service travel system
目 录
摘 要.............................................................................................................................I
目 录..........................................................................................................................IV
图清单.......................................................................................................................VIII
表清单..........................................................................................................................XI
变量注释表...............................................................................................................XIII
1 绪论............................................................................................................................ 1
1.1 研究背景及意义....................................................................................................1
1.2 国内外研究现状....................................................................................................2
1.3 研究内容................................................................................................................ 7
1.4 技术路线................................................................................................................ 8
1.5 论文的组织结构....................................................................................................9
2 路线规划理论与实现技术 ..................................................................................... 11
2.1 Android 平台 ....................................................................................................... 11
2.2 百度地图 SDK..................................................................................................... 14
2.3 定向问题相关理论.............................................................................................. 15
2.4 定向问题算法...................................................................................................... 17
2.5 本章小结.............................................................................................................. 20
3 基于定向问题的旅游路线规划问题研究 ............................................................. 21
3.1 经典路线规划模型.............................................................................................. 21
3.2 问题分析.............................................................................................................. 23
3.3 基于定向问题的数学模型建立.......................................................................... 24
3.4 A*算法的改进..................................................................................................... 26
3.5 旅游路线规划实现.............................................................................................. 34
3.6 本章小结.............................................................................................................. 40
4 云龙湖自助旅行系统的设计与实现 ..................................................................... 41
4.1 需求分析.............................................................................................................. 41
4.2 开发环境.............................................................................................................. 44
4.3 系统架构设计...................................................................................................... 46
4.4 系统功能模块设计.............................................................................................. 48
4.5 系统实现.............................................................................................................. 51
4.6 系统测试.............................................................................................................. 67
4.7 本章小结.............................................................................................................. 70
5 结论与展望.............................................................................................................. 71
5.1 结论...................................................................................................................... 71
5.2 展望...................................................................................................................... 72
参考文献...................................................................................................................... 73
作者简历...................................................................................................................... 78
学位论文原创性声明 .................................................................................................79
学位论文数据集.......................................................................................................... 80
1 绪论
1.1 研究背景及意义
随着经济的发展和社会条件的改善,人们的生活状态愈发丰富多彩,旅游已经成为群众日常生活的重要组成部分.中华人民共和国文化和旅游部官方网站发布的最新统计数据显示,2018 年国内旅游总人数与上年相比增长超百分之十,旅游总收入比上年增长超百分之十二[1].并且,根据抽样调查显示,2018 年全年国内民众旅游人数高达 55.39 亿人次.由此看来,旅游业已经成为了我国国民经济发展的重要产业[2].
近年来,随着旅游业的不断发展,人们对于外出旅游的消费观念和需求与前几年相比发生了深刻变化.传统的跟团旅游虽然仍在旅游市场占有一定份额,但是由于其古板、程序化、不自由等弊端的愈发突出,逐渐满足不了游客个性化旅 游的需求,目前越来越多的游客选择自助出游[3].自助游是目前较为流行的旅游方式,因其自由、灵活、经济的特性已受到众多旅游者的青睐.游客选择自助出 行时,首要解决的就是旅行过程中路线的规划问题[4].而一个设计合理的旅游路 线既能够帮助旅行者有目的的选择、安排自己的旅游活动,也可以避免游客在景区内"漫游"[5],节省时间和经费开支.然而对自助旅行者而言,在有限的旅游时间,且对游玩景区十分陌生的情况下,面对景区内部众多的旅游景点,很难制 定合理的旅游行程使自己更好的达到游玩目的.因此,提供一个既可以满足用户行程规划需求,又能及时了解景区环境的系统平台必要且迫切[6].
旅游路线规划通常包括旅游起始景点查询、设定预计旅游时间、游览路线确定等环节.因此进行路线设计需要考虑各景点服务时间、交通情况等多种因素.目前一些旅游网站系统已经具备路线规划或推荐的服务功能,例如途牛网、去哪儿网、链景旅行、百度地图等[7],它们为用户出行提供了帮助,但是还存在很多问题.以游客为中心是线路设计与景点选择的基础,但这些系统推荐的旅游路线大多是景区热门景点的简单组合,无法为用户提供精细的决策服务[8].另外,提供给用户的旅游行程规划大多是与旅行社或者是与景区内商家联盟合作的旅游产品,商业气息浓厚.因此,这类软件大多没有充分考虑到游客的个性化需求,推荐结果一定程度上缺乏真实性,很难友好的为用户服务.
近年来,移动互联网和手机通信技术的不断发展和快速进步,为当代旅游信息化的建设和发展提供了极大的便利[9].现代信息技术不仅深刻地影响着现代科学技术、教育、工农业生产乃至经济建设的各个方面,而且影响着人们的生活、工作和娱乐方式[10].手机的普遍化使得人们越来越偏好于随时随地获取旅游信息[11],而一个条理清晰,功能强大的旅游路线推荐系统,可以帮助用户更好地了解相关的旅游信息,因此,基于智能移动终端对智能自助旅游系统进行研究十分必要.目前,市场上应用最普遍的两种智能手机操作系统分别是谷歌的 Android 和苹果的 IOS[12].其中,Android 操作系统是基于 Linux 的真正意义上的开放性平台[13][14].Android 支持手机、平板等多种硬件选择[15],支持 JAVA 的所有类库,为移动端应用开发者提供了很多方便.目前,Android 系统已经逐渐成熟,在当 前市场份额中占有极大的比重.因此,使用 Android 作为云龙湖自助旅行系统的基础平台,可以满足大多数游客的需求.
根据自助游客所面临的旅行问题,结合现有旅行服务系统所存在的不足,本文以基本定向问题为基础,建立数学模型,深入研究旅游线路规划问题和 A*智能优化算法[16],丰富了路线规划的研究方法.并且,以 Android 智能终端为开发平台,云龙湖景区为应用实例,设计并实现可以进行旅游路线推荐及其他服务功能的自助旅行系统[23][24],帮助游客规划个人旅游行程,既有理论研究的必要,也有实际应用的意义.
1.2 国内外研究现状
1.2.1 旅游路线规划
旅游路线规划是当前路线规划研究的热点.游客到达景区后,在对目的地景区不了解,且时间有限的情况下,很难游览完所有的景点.因此为了选择合理的旅游路线往往需要提前进行大量景区内部信息的搜索.现有搜索引擎所能提供的信息过于零散且参考价值较低,旅游网站的推荐结果也参差不齐,需要大量时间进行筛选.例如当用户使用一些旅游推荐系统进行路线推荐时,得到的大多是该景区经典的旅游路线,或者是粉丝量较大的博主推荐的路线攻略,更甚者直接是几个景点的随机组合.很明显这些推荐的结果并没有考虑到用户个性化的需求和现实环境的约束[25].并且,实际旅行环境中,用户可能希望自由的选择游玩起点和终点,也可能会对自己的旅游有一个时间预算等,这些因素都会造成最终路线的不同,而将这些影响因素考虑到旅游路线推荐中是一项很具有挑战性的任务[26].因此,高效、准确的旅游路线推荐服务是游客规划行程的重要依据[27].
旅游路线规划或旅程设计是一个技术性(经验性)非常强的课题[28].国外关于旅游路线规划的研究较多.Ayala 等人提出了一种多目标的城市旅游路线规划系统,该系统允许游客选择两个相距较短的位置,进行步行路线的规划,且路线尽可能穿越有趣的旅游区域[29].Hasuike 等人提出了一种时间依赖型旅游路线的规划问题,并建立路线规划模型,利用改进的Dijkstra算法[30]进行该类问题的求解, 为游客提供了适当的观光路线和时间表,但是该方法没有考虑观光地点的满意度值[31].Cenamor 等人推出了 PlanTour,这是一种新的观光推荐系统,它可以根据用户的旅游天数和社交网络热门旅游信息,为用户推荐旅游路线,该系统包含大多数热门旅游景区,但是更适合预计旅行周期较长的用户,且推荐的路线是固定的[32].Du, Peiming 等人提出了一种基于 GIS 的森林湿地旅游线路优化算法,它可以应用于森林湿地环境的最佳旅游线路规划[33].LinWan 等人提出了一种混合集成学习方法 BAyes-Knn,通过对社交网络上旅行照片的位置标记进行数据挖掘来预测用户的地理偏好,为旅行者规划个性化的旅游路线[34],但是该方法没有考虑景区内的时空约束,例如整个旅行所需的时间和景点的季节性状态.
国内关于旅游线路规划的研究较少,对旅游线路规划深层次的研究较少[35].张子寒等人以南京市主要景区的游览为例[36],建立多种路线规划模型,分别使用动态规划算法、遗传算法[37]等对模型进行求解,证明了时间约束对于景区旅游路线规划结果的重要影响.李渊等人提出了考虑时间约束和游客空间行为特征的旅游路线设计方法[38],实现了针对鼓浪屿的旅游路线的规划.吴青霞等人通过对用户历史旅游足迹进行数据挖掘,利用用户在景点停留时间不同,判断用户兴趣偏好,在给定起始景点、目标景点以及旅行时间限制的条件下为用户推荐一条满足其兴趣爱好的旅游路线[39],但是这种方法没有考虑到单个景点的流行度以及景区内路径交通的复杂性.吴艳琴等人将来自不同在线旅游网站的信息聚合并进行比较,使用 k-means 方法对用户进行聚类,根据个人消费习惯有针对性的对搜索结果进行排序,高频次的路线会优先展示给用户[40],但是用户没有真正参与到旅游路线规划中,因此无法提供精细的决策服务.Liao, Zhixue 等人提出了一种基于随机模拟(RS-H2A)的混合启发式算法,用于解决时间依赖的随机环境中的路线规划问题,并以中国四川的九寨沟为研究案例设计个性化的一日游路线[41].冀紫菁在进行旅游路线规划时,首先建立基于层次分析法[42]的景点推荐模型保证景点选取满足游客的偏好,其次综合考虑景区的开放时间、游客的就餐和休息的时间等因素,建立带时间窗的路线规划数学模型,以解决城市旅游中的路线规划问 题[43],该方法在规划路线时没有考虑总时间约束问题.
目前,一种广泛的求解旅游路线规划问题的方法是将其作为定向问题来进行求解[44].定向问题在实际应用中十分广泛,基本的定向问题可以描述为:给定起点和终点以及限制条件,如何规划一条收益最大的路径[45].定向问题是一个NP-hard 问题[46],在很多实际问题上都有应用.因此,为了更好地解决实际问题,可根据需要,将定向问题的研究扩展为多种类型[47],例如:多目标定向问题[48],团队定向问题[49],时间依赖型定向问题以及有容量约束的定向问题等[50].关于定向问题的具体概念以及扩展和组合形式的应用将在第二章详细展开论述.Vansteenwegen 等人综合考虑旅行约束条件,研究时间约束型定向问题,向用户推荐最优且满足个人兴趣爱好的景点类型构成的旅游路线[54];Gionis 等人通过对景点进行分类,扩展基本的定向问题,综合考虑用户兴趣和景区优点进行路线规划,但是结果路线中景点的访问顺序受限于其所属类型[55];Jossé, Gregor 对基于弧的定向问题(AOP)进行扩展[56],建立了具有时间相关行程时间和时间相关值增益的双重时间依赖的定向问题,但是该模型求解结果为弧收益最高的路线;Gavalas 等人[57][58]多次对旅游路线规划问题进行研究,并将研究结果应用化,实现了旅游路线推荐系统的开发,但是该系统缺少每日游览的时间预算约束;?a?laCergibozan 以土耳其爱琴海地区的部分景点为研究案例,利用改进的遗传算法进 行路线规划问题求解,发现景点的受欢迎程度对路线中旅游点的选择有明显影响[59],但是该方法在进行路线规划时未考虑游客旅行时间的限制.
综上所述,关于旅游景点路线推荐的研究已经取得一些成果,但是上述方法在不同方面存在缺陷并且难以为用户推荐满足其需求的旅游线路.
1.2.2 自助旅行系统
传统旅游多采用跟团旅游模式,而未来旅游业的消费主体开始由团体旅游向散客自助游转变.这种形势下,构建以游客为中心的自助旅游服务系统显得尤为重要,移动终端系统的发展为自助旅行系统[60]的兴起提供了契机.信息化时代,随着互联网的迅速普及,移动终端已经在方方面面影响我们的日常生活.手机作为受众率最高的移动终端,近年来,饱受商家青睐,各类服务软件层出不穷,已经成为人们外出旅游时不可或缺的辅助工具.
国外特别是西方发达国家,率先选择在移动终端上开发服务类智能 APP 软件.并且由于国外的旅游业起步较早,所以早在 1999 年日本就推出了 i-mode[61],这是一款提供美食推荐以及路况查询等旅游服务的手机软件.与此同时,美国也推出了一款手机导游软件,不过该软件仅限于部分场所使用,它的主要功能是对展品进行电子解说.
国外的智能旅游 APP 所提供的各种服务分类十分细化,且功能丰富.美国的 Airbnb 是目前全球最大的民宿在线预订网站,覆盖了世界各地,并且对于每一个想要融入当地生活的旅行者来说,民宿自然是首选,因此,该网站一直深受长期旅行游客的欢迎;Yelp,美食点评与推荐类网站的鼻祖,该软件除了包括美国本土,还覆盖了加拿大、英国、法国、澳大利亚等许多国家;Travelocity 主要业务为各种旅游票务,行程代销,该网站通过与航空公司,旅馆等旅游服务供应商合作,为用户提供了航空、旅馆、船务、租车以及其它旅游产品促销案的代理服务[62],但是软件本身不提供行程规划;Skyscanner 是一款免费的 WindowsPhone 版应用程序,主要提供最低消费的路线行程推荐服务,运行高效,且提供选择的路线数量众多;东京 Metro,一个地铁网站,为用户提供地铁的运行路线图、票价的计算方式、车票种类、月票销售以及景点指南等信息,方便乘车出行,并且此应用可以使用英文、中文、泰语等多国语言,适合到东京观光的外地游客使用.
国外还有很多综合性自助旅行系统,例如韩国开发的"I Tour Seoul"综合应用系统[63],用户能通过该系统获取到当前位置的旅游信息,了解周围的公交、商 场、酒店等的分布概况,并且它还提供多种语言支持,方便外国用户使用.美国Steamboat 滑雪场开发了一套集定位、路线推荐为一体的滑雪软件,它具有自我定位、推荐合适的滑雪路线等功能[64];这些旅游信息化的建设展示了旅游过程中的智能化和便捷化[65].
国内自助旅游系统的起步要晚于国外发达国家,但是发展迅速.目前国内的自助旅行系统的应用主要分为三种类型:第一类是提供景点讲解和旅行路线服务的旅游应用;第二类是提供酒店、餐饮以及车票销售为主要服务的旅游应用;最后一种是为特定景点设计的提供综合服务的自助旅行系统.目前,前面两类,在市场中占有较大份额且已有在使用的系统,第三类软件目前市场较为稀缺,且发展潜力较大.
第一类应用结合了当代电子商务的优势与传统旅行社服务的特点,它可以针 对景区和用户的需求改进旅行产品,并通过互联网技术基本实现用户游览和电子导游讲解的完美同步.目前市面上比较成熟,受众率较高的提供旅游景点和旅游路线服务的旅游应用主要有百度地图 APP、高德地图 APP、链景旅行 APP、荔枝 FM--同里时光等.用户准备出行时可提前购买该类产品,获得随身电子导游服务.以链景旅行 APP 为例,产品核心功能主要分为三个模块.模块一是景点推荐,该软件利用自身强大的景点库基于全球过十万旅游目的地为游客分类推荐景点,例如历史人文、自然风光、娱乐休闲等;模块二是景点讲解,对于景区内较着名的景点可以为用户提供景点信息的语音讲解,部分软件可以根据游客目前位置提供自动讲解的服务;模块三是地图导航,主要提供景区基础电子地图导览,防止游客在面积较大的景区内迷路.该类软件目前最大的优势就是可以给用户提供景点的语音讲解等类似真人导游的服务,但是景区内可讲解景点的覆盖率不高,且由于软件总体数据量较大,讲解内容不够具体,且信息更新也比较缓慢.
第二类应用是传统旅游和互联网完美结合的产物,是线上到线下(Online ToOffline,OTO)模式的代表.应用开发商为游客和商家提供了一个可以直接交流的服务平台,并通过为游客提供餐饮和各类票务销售服务获取中间利润.这类应用包括大众点评、去哪儿、百度糯米和携程等软件.以去哪儿 APP 为例,去哪儿网是全球最大的中文在线旅游网站,它可以通过其自有的技术平台,通过大量的调研和数据挖掘高效的实现旅游业供需的准确匹配,同时满足旅游服务供应商和自助旅行者的旅游需求.对于商家客户,去哪儿网为旅游产品供应商提供了线上经营的基础设施和运行渠道,拓宽其发展层面;对于普通旅行者,去哪儿网针 对用户使用终端不同既可以提供在线网站服务,也可以满足移动客户端用户需求,随时随地为其提供酒店、票务、路线攻略及其他旅行信息的深度搜索.通过该平台用户可以轻松的找到满意度较高的产品、较优质的旅行服务信息以及各类团购优惠渠道,智能的安排旅行中的食宿和票务事宜[66].该类应用的票务及用户论坛服务都很成熟,普通用户可以轻松在平台上找到最优惠的团购服务以及排名最高的景点.但是,该类网站的信息十分纷杂,用户可能需要花费很大的时间和精力进行总结归纳才能形成旅游攻略,并且无法根据个人需求快速规划旅游路线.
第三类是单景点的自助旅行移动终端软件,这类应用一般为特定景点量身定做,功能更合理、内容更丰富,并且人性化的设计更能满足游客的旅游需求.目前市面上已经有很多类似的智能软件,例如智慧夫子庙,智慧五台山、张家界旅游等应用,既可以为首次前来的外地游客提供旅游指导,也可以为本地人们的生活带来较大的便利.以智慧夫子庙 APP 为例,该应用将传统的旅游线下运营与目前十分流行的网络营销有机结合.游客可以在到达目的地景区前安装此软件,通过软件内容就能够大致了解夫子庙的景点概况.并且软件提供的景区内的旅游路线攻略、美食推荐、以及地图等服务也为用户的行程安排提供了很多方便.对 于夫子庙内部的小吃街,停车场,公厕等的分布下载一个 APP 就能全部了解.因此,该类应用既实现了景区的线上推广,也为景区游客提供了更多的便利,并且与前两类相比,应用的内容更加细致且贴近当地人文,景区内部数据的更新和管理也更加方便.
近年来,自助旅行系统[67]已经得到了快速发展和重视,在未来的旅游市场中进步潜力较大.国内目前虽然已有不少成熟的旅游产品和解决方案,但是这些软件在功能人性化设计、路线智能推荐等问题上还有所欠缺.因此紧跟信息技术发展的脚步,研究并实现的真正满足游客个性化需求的高质量自助旅行软件产品十分必要.
…………由于本文篇幅较长,部分内容省略,详细全文见文末附件
5 结论与展望
5.1 结论
随着经济的发展,人们文化水平的日益提高,当下的旅游消费观念和需求都发生了较大的变化.与传统的跟团旅行相比,越来越多的游客选择自助旅游.但是,对于自助旅行者而言,到一个陌生的景区游玩时,对于景区内各个景点的具体情况以及景区交通等并不了解,很有可能会迷路或者在景区内"漫游",很难达到游玩目的.针对这种情况,本文以云龙湖景区为应用实例,对旅游路线规划问题进行研究,并基于 Android 平台开发了一款自助旅行系统.用户在到达目的地景区前可根据系统提供的景点推荐、食宿推荐、经典路线及个性化旅游路线的推荐等功能了解景区概况并制定自己的旅游行程,旅行途中可根据系统提供的地图定位、路线规划、景点位置显示等功能随时定位个人位置,查看下一景点的位置和简单信息,并规划自己的游览路线.本文实现的主要工作总结如下:
(1)与一般的寻路问题不同,旅游路线的规划除了需要考虑景点间的交通时间,还需要考虑景点的热度以及总时间约束等环境因素.因此,本文针对旅游路线规划问题的特点,综合考虑旅游环境的特殊性,通过对经典的路线规划问题模型的目标函数和约束条件进行研究,选择定向问题作为基础模型,设定合理假设,建立了基于定向问题的旅游路线规划数学模型.
(2)结合问题特点和模型求解的目标,改进了传统的 A*算法的启发式规则,提出一种以最大化路线收益为目标,同时满足旅游时间约束限制的路线规划算法.实验证明,与传统 A*算法仅考虑最小化距离或者时间权重相比,改进后的算法考虑了更多实际环境信息且结果更为合理,更适用于旅游路线规划问题的求解.
(3)以云龙湖景区作为应用实例,根据旅游路线规划问题模型要求,将景区内的景点和道路抽象为无向图.使用爬虫、人工搜索等技术收集景区数据并合理量化,得到景区内景点得分、游览时间,路径交通时间,景点泊车时间等模型参数.利用改进后的 A*算法,结合已知数据,实现了云龙湖景区的旅游路线规划,为自助旅行系统的旅游路线推荐功能提供算法与理论支撑.
(4)根据云龙湖景区的特点分析游客对系统的功能需求,设计并实现基于Android 平台的自助旅行系统.系统分为景点服务、路线规划、旅行安全三个模块,可以为用户提供景点、食宿、旅游路线的推荐,紧急求救等多种功能,并结合百度地图 SDK 实现用户定位、路线规划、景点显示等功能,为用户的自助旅行提供了极大的便利.经测试,系统的功能和性能均能满足用户基本需求.
5.2 展望
本系统旨在为云龙湖景区内自助旅行的游客提供景区介绍、路线规划以及旅行安全等功能服务,但在实际应用的过程中,仍然存在一些不足,可以在后续的研究中进一步改进:
(1)旅游路线的动态规划.本文对路线规划进行建模求解时,仅考虑了景点泊车时间的时变特性,下一步可利用数据挖掘等技术精细化模型,在路线规划时考虑各景点的游客拥堵情况对时间的依赖性,以及景点间路径交通的动态变化情况对结果路线的影响.
(2)增加景点语音讲解的功能.本系统目前仅提供了景区内景点的文字和图片信息,但是实际旅行过程中,景点信息的语音讲解可以帮助用户更快的了解景点内容.后续会增加语音讲解功能,使得系统更加人性化.
(3)数据来源多样化.本文进行路线规划使用的原始数据均来源于去哪儿网和百度地图搜索引擎,未来的研究中可以增加大众点评、途牛网等其他旅游网站的数据,进一步保证模型参数量化的合理性.
参考文献
[1] 徐依娜. 国家旅游局局长李金早出席会议并演讲 2018 年全国旅游工作会议在厦门召开[J]. 中国会展, 2018(2):17-17.
[2] 刘士润, 崔忠伟, 韦萍萍,等. 基于 Android 的"智慧旅游"手机 APP 开发[J]. 电子技术与软件工程, 2015(8):85-86.
[3] 高莉, 方尹卉. 大数据时代自助游消费需求探析[J]. 知识经济, 2018(10).
[4] 曹阳. 城市旅游规划行程链的模型构建及其应用研究[D]. 南京师范大学, 2014.
[5] Liu H, Jin C, Zhou A. Popular Route Planning with Travel Cost Estimation[M]// DatabaseSystems for Advanced Applications. 2016.
[6] 王懿雯. 基于热点空间网络建模的个性化旅游行程规划[D]. 东南大学, 2017.
[7] 安旭, 赵巾帼. 面向智慧旅游的自助导游系统设计[J]. 产业与科技论坛, 2018,v.17(13):79-80.
[8] Zheng W, Liao Z, Jing Q. Using a four-step heuristic algorithm to design personalized day tourroute within a tourist attraction[J]. Tourism Management, 2017, 62:335-349.
[9] 乔天斐. 基于 Android 平台的自助旅游系统研究与实现[D]. 电子科技大学, 2016.
[10] 李德仁. 中国科学院 中国工程院院士李德仁谈发展空间信息产业的市场前景[J]. 学习与实践, 1998(11):64-65.
[11] 邵猛. 基于 Android 的自助游移动平台应用设计与开发[D]. 南京邮电大学, 2016.
[12] 王向辉, 张国印, 赖明珠. Android 应用程序开发.第 2 版[M]. 清华大学出版社, 2012.
[13] You D H, Noh B N. Android platform based linux kernel rootkit[C]// InternationalConference on Malicious & Unwanted Software. 2011.
[14] Friesen G. Learn Java for Android development[J]. Springer Berlin, 2010.
[15] Shan L, Duan X, Bai Y, et al. Development and Application of Intelligent Tour Guide Systemin Mobile Terminal[C]// Seventh International Conference on Measuring Technology &Mechatronics Automation. 2015.
[16] Dechter R, Pearl J. Generalized best-first search strategies and the optimality of A*[J].Journal of the Acm, 1985, 32(3):505-536.
[17] Sturm B. Demonstration of Astar (A*)[J]. Conservator, 1999, 23(1):77-82.
[18] 陈素琼, 王惠来, 向天雨. 基于改进 A~*算法的地图游戏寻径研究[J]. 重庆师范大学学报:自然科学版, 2017(4):75-78.
[19] Fernandes E, Costa P, Lima J, et al. Towards an orientation enhanced astar algorithm forrobotic navigation[C]// IEEE International Conference on Industrial Technology. 2015.
[20] 张超超, 房建东. 基于定向加权 A*算法的自主移动机器人路径规划[J]. 计算机应用,2017(a02):77-81.
[21] 黄冬梅, 杨建, 何盛琪,等. 基于权重的改进A*算法航线规划研究[J]. 海洋信息, 2018(2).
[22] 史辉, 曹闻, 朱述龙,等. A*算法的改进及其在路径规划中的应用[J]. 测绘与空间地理信息, 2009, 32(6):208-211.
[23] Ichimura T, Tanabe K, Tachibana I. Tourist navigation in Android smartphone by usingEmotion Generating Calculations and Mental State Transition Networks[C]// JointInternational Conference on Soft Computing & Intelligent Systems. 2018.
[24] Sabatucci L, Cavaleri A, Cossentino M. Adopting a Middleware for Self-adaptation in theDevelopment of a Smart Travel System[M]// Intelligent Interactive Multimedia Systems andServices 2016. 2016.
[25] Cheverst K, Davies N, Mitchell K, et al. Developing a context-aware electronic tourist guide:some issues and experiences[J]. Proceeding of Chi, 2000:17--24.
[26] Ku?en E. Tourism Attraction System[M]// Evolution of Destination Planning and Strategy.2017.
[27] 佘新伟. 在线旅游行程规划系统关键技术研究与实现[D]. 西安电子科技大学, 2013.
[28] 楚义芳.关于旅游线路设计的初步研究[J].旅游学刊,1992(02):9-13+57-60.
[29] Ayala I , Mandow L , Amor M , et al. An Evaluation of Multiobjective Urban Tourist RoutePlanning with Mobile Devices[C]// Proceedings of the 6th international conference onUbiquitous Computing and Ambient Intelligence. Springer-Verlag, 2012.
[30] Sunita, Garg D. Dynamizing Dijkstra: A Solution to Dynamic Shortest Path Problem throughRetroactive Priority Queue[J]. Journal of King Saud University - Computer and InformationSciences, 2018:S1319157817303828.
[31] Hasuike T , Katagiri H , Tsubaki H , et al. Route planning problem with groups of sightseeingsites classified by tourist's sensitivity under Time-Expanded Network[C]// IEEE InternationalConference on Systems. IEEE, 2014.
[32] Cenamor I , de la Rosa, Tomás, Nú?ez, Sergio, et al. Planning for tourism routes using socialnetworks[J]. Expert Systems with Applications, 2017, 69(Complete):1-9.
[33] Du P , Hu H . Optimization of tourism route planning algorithm for forest wetland based onGIS[J]. Journal of Discrete Mathematical Sciences and Cryptography, 2018, 21(2):283-288.
[34] Wan L , Hong Y , Huang Z , et al. A hybrid ensemble learning method for tourist routerecommendations based on geo-tagged social networks[J]. International Journal ofGeographical Information Science.
[35] 曹旭. 旅游线路优化设计研究[D]. 西北民族大学, 2012.
[36] 张子寒, 张落成. 基于多种模型的旅游线路规划探讨--以南京主要景区游览为例[J].计算机应用, 2016(S1):278-280.
[37] Koca G O, Dogan S, Yilmaz H. A multi-objective route planning model based on geneticalgorithm for cuboid surfaces[J]. Automatika, 2018, 59(1):120-130.
[38] 李渊, 丁燕杰, 王德. 旅游者时间约束和空间行为特征的景区旅游线路设计方法研究[J].旅游学刊, 2016, 31(9):50-60.
[39] 吴清霞, 周娅, 文缔尧, 贺正红. 基于用户兴趣和兴趣点流行度的个性化旅游路线推荐[J].计算机应用, 2016,36(06):1762-1766.
[40] 吴燕琴. 个性化旅游线路搜索系统的设计与实现[D]. 大连理工大学, 2016.
[41] Liao Z , Zheng W . Using a heuristic algorithm to design a personalized day tour route in atime-dependent stochastic environment[J]. Tourism Management, 2018, 68:284-300.
[42] Saaty T L, Vargas L G. Models, Methods, Concepts & Applications of the Analytic HierarchyProcess[M]. 2012.
[43] 冀紫菁. 基于层次分析法和时间窗的个性化定制旅游行程模型[J]. 中国商论, 2018(8).
[44] Vansteenwegenaaba P. The orienteering problem: A survey[J]. European Journal ofOperational Research, 2011, 209(1):1-10.
[45] Tsiligirides T. Heuristic Methods Applied to Orienteering[J]. Journal of the OperationalResearch Society, 1984, 35(9):797-809.
[46] Golden B L, Levy L, Vohra R. The orienteering problem[J]. Naval Research Logistics, 2015,34(3):307-318.
[47] Souffriau W, Vansteenwegen P, Vertommen J, et al. A personalized tourist trip designalgorithm for mobile tourist guides[J]. Applied Artificial Intelligence, 2008, 22(10):964-985.
[48] 李全. 游客行程多目标智能规划算法研究[D].电子科技大学,2017.
[49] Chao I M, Golden B L, Wasil E A. The team orienteering problem[J]. European Journal ofOperational Research, 2007, 88(3):464-474.
[50] Keller C P. Algorithms to solve the orienteering problem: A comparison *[J]. EuropeanJournal of Operational Research, 1989, 41(2):224-231.
[51] Chao I M, Golden B L, Wasil E A. The team orienteering problem. Eur J Oper Res[J].European Journal of Operational Research, 1996, 88(3):464-474.
[52] Karimi A, Bashiri M. The bi-team orienteering problem with time window[J]. InternationalJournal of Services & Operations Management, 2018.
[53] Archetti C, Carrabs F, Cerulli R. The Set Orienteering Problem[J]. European Journal ofOperational Research, 2018, 267(1).
[54] Vansteenwegen P, Souffriau W, Berghe G V, et al. The City Trip Planner: An expert systemfor tourists[J]. Expert Systems with Applications, 2011, 38(6):6540-6546.
[55] Gionis A, Lappas T, Pelechrinis K, et al. Customized tour recommendations in urban areas[J].Social Science Electronic Publishing, 2014:313-322.
[56] Jossé, Gregor, Lu Y , Emrich T , et al. Scenic Routes Now: Efficiently Solving theTime-Dependent Arc Orienteering Problem[J]. 2016.
[57] Gavalas D, Konstantopoulos C, Mastakas K, et al. Efficient Heuristics for the TimeDependent Team Orienteering Problem with Time Windows[M]// Applied Algorithms.Springer International Publishing, 2014:152-163.
[58] Gavalas D, Kasapakis V, Konstantopoulos C, et al. Scenic route planning for tourists[J].Personal & Ubiquitous Computing, 2017, 21(1):1-19.
[59] ?a?la Cergibozan, Tasan A S. Tourist Route Planning with a Metaheuristic Approach[J].2018.
[60] 程卫军, 邵燕, 张玉军,等. 基于 ARM+GPS+GSM 的智能电子导游系统的设计与实现[J].中央民族大学学报(自然科学版), 2011, 20(1):61-66.
[61] Hubbard A E, Hughes J W, Lipschultz B, et al. I-mode: an H-mode energy confinementregime with L-mode particle transport in Alcator C-Mod[J]. Nuclear Fusion, 2010,50(10):105005-105015(11).
[62] 雷俊丽. 易逝品尾货不同分销模式的价格策略[D]. 北京理工大学, 2014.
[63] 李勇. 基于移动互联网的智慧旅游导览系统的设计与实现[D]. 2017.
[64] 庄立汉. 智慧旅游系统研究与设计[D]. 上海交通大学, 2014.
[65] 张顺亮. 智慧旅游系统的设计与实现[D]. 电子科技大学, 2014.
[66] 文忠, 袁禄军. 基于移动互联网的景区自助旅游系统及方法:, CN104680440A[P]. 2015.
[67] 郝波. 基于 Android 的海南自助旅游系统开发[J]. 中国新通信, 2015(24):74-75.
[68] 刘舟瑫. 基于 android 平台的旅游攻略 APP 的设计与实现[D]. 北京交通大学, 2015.
[69] 肖泽宇. 基于百度地图 API 的旅游景点查询系统开发[J]. 电脑编程技巧与维护,2017(4):35-37.
[70] 张赞. 基于大数据的智慧旅游系统设计与实现[D]. 东北大学, 2016.
[71] Tsiligirides T . Heuristic Methods Applied to Orienteering[J]. The Journal of the OperationalResearch Society, 1984, 35(9):797-809.
[72] 王新红, 崔玉泉. 城市道路定向问题及其算法[J]. 山东大学学报( 理学版), 2004,39(1):21-28.
[73] Wang W, Lau H C, Cheng S F. Exact and heuristic approaches for the multi-agentorienteering problem with capacity constraints[C]// Computational Intelligence. 2018.
[74] Kantor M G, Rosenwein M B. The Orienteering Problem with Time Windows[J]. Journal ofthe Operational Research Society, 1992, 43(6):629-635.
[75] Lu Y , Shahabi C . An arc orienteering algorithm to find the most scenic path on a large-scaleroad network.[J]. 2015.
[76] Ghobber I, Tlili T, Krichen S. Partition Crossover Evolutionary Algorithm for the TeamOrienteering Problem with Time Windows[C]// International Conference on Industrial. 2018.
[77] Dolinskaya I, Shi Z, Smilowitz K. Adaptive orienteering problem with stochastic traveltimes[J]. Transportation Research Part E Logistics & Transportation Review, 2018, 109:1-19.
[78] Mirjalili S, Saremi S, Mirjalili S M, et al. Multi-objective grey wolf optimizer: A novelalgorithm for multi-criterion optimization[J]. Expert Systems with Applications, 2016,47:106-119.
[79] Alaya I, Solnon C, Ghedira K. Ant Colony Optimization for Multi-Objective OptimizationProblems[C]// IEEE International Conference on Tools with Artificial Intelligence. 2017.
[80] Gong D, Sun J, Miao Z. A Set-Based Genetic Algorithm for Interval Many-ObjectiveOptimization Problems[J]. IEEE Transactions on Evolutionary Computation, 2018,22(1):47-60.
[81] Hu P, Chen G, Wang Z. Research for path planning based on improved astart algorithm[C]//International Conference on Information. 2017.
[82] ZHANG Zi-cheng, Han W, Mao B. Adaptive Discrete Cuckoo Algorithm Based on SimulatedAnnealing for Solving TSP[J]. Acta Electronica Sinica, 2018.
[83] 李云岘. 景观配置与文化建设的和谐--以徐州云龙湖风景区规划为例[J]. 林业工程学报, 2007, 21(2):101-104