旅游路线规划研究综述（桂林电子科技大学：常亮、孙文平、张伟涛、宾辰忠、古天龙）

第14卷第1期 智能系统学报 Vol.14 No.I 2019年1月 CAAI Transactions on Intelligent Systems Jan.2019 D0:10.11992/tis.201804005 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180523.1350.002.html 旅游路线规划研究综述 常亮，孙文平，张伟涛，宾辰忠，古天龙 (桂林电子科技大学广西可信软件重点实验室，广西桂林541004) 摘要：旅游业的快速发展和用户分享内容的激增使得旅游领域的信息过载问题日益突出，如何帮助游客在快 速制定个性化游览路线的同时提升旅行体验，成为当前旅游路线规划问题研究的关键。首先，给出旅游路线规 划问题的形式化定义：然后，将文献中的旅游路线规划求解方法分为基于精确数学建模的求解、基于用户生成 内容的求解两大类，对各类方法的关键技术和存在的主要问题进行了较为详细的考察：最后，给出一个旅游路 线规划系统整体架构，对其中存在的重点和难点问题进行了分析，为旅游路线规划问题的研究提供理论支持的 同时指明了下一步的研究方向。 关键词：旅游路线规划；位置服务；轨迹挖掘：个性化推荐；上下文感知；定向问题；用户生成数据；全域旅游 中图分类号：TP301 文献标志码：A文章编号：1673-4785(2019)01-0082-11 中文引用格式：常亮，孙文平，张伟涛，等.旅游路线规划研究综述J1.智能系统学报，2019,14(1)：82-92 英文引用格式：CHANG Liang,SUN Wenping,ZHANG Weitao,.etal.Review of tourism route planning J.CAAI transactions on intelligent systems,2019,14(1):82-92. Review of tourism route planning CHANG Liang,SUN Wenping,ZHANG Weitao,BIN Chenzhong,GU Tianlong (Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China) Abstract:With the rapid development of tourism and surge in user sharing,information overload in tourism has be- come an increasing problem.Currently,the key issue in tourism route planning is how to help tourists to develop person- alized travel routes and enhance their travel experiences.In this paper,we first provide a formal definition of the tour- ism route planning problem..Then,we sort the methods used to solve this problem into two categories,i.e.,those based on exact mathematical modeling and those based on user-generated content.We then present a detailed survey of the key technologies and difficulties of these methods.Lastly,we propose an overall framework for the tourism route planning system,analyze the key difficulties of the system,provide theoretical support for the study of tourism route planning, and suggest a future research direction. Keywords:tourism route planning;location-based service;trajectory mining;personalized recommendation;context- aware;orientation problem;user-generated data;all-for-one tourism 在当前稳定的宏观经济和社会环境下，国民 着可选地点的急剧增加，如何根据用户需求帮助 旅游需求不断增加，旅游活动持续升温，“全域旅 用户快速进行旅行路线规划，成为全域旅游中亟 游”的发展战略突破了传统景区与景点的资源观 待解决的难点问题，使得相关旅游路线规划方法 念，延伸到农耕民俗、工业遗产等社会资源，对旅 的研究成为当前旅游领域的研究前沿。 目前，虽然旅行者在进行旅行规划时可以在 游业的服务质量也提出了更高的要求。然而，随 互联网上方便地查看相关信息，但仍然需要花费 收稿日期：2018-04-04.网络出版日期：2018-05-24. 基金项目：国家自然科学基金项目(61572146，U1501252, 大量时间和精力四。经常出现的现象是，许多旅 U1711263):广西创新驱动重大专项项目(AA17202024): 广西自然科学基金项目(2016 GXNSFDA380006). 行者在事先花费了很多时间制定旅行路线，但最 通信作者：宾辰忠.E-mail:binchenzhong@guet.edu.cn. 终却又不得不选择跟团的形式进行旅行，因此旅

DOI: 10.11992/tis.201804005 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180523.1350.002.html 旅游路线规划研究综述 常亮，孙文平，张伟涛，宾辰忠，古天龙 （桂林电子科技大学 广西可信软件重点实验室，广西 桂林 541004） 摘 要：旅游业的快速发展和用户分享内容的激增使得旅游领域的信息过载问题日益突出，如何帮助游客在快 速制定个性化游览路线的同时提升旅行体验，成为当前旅游路线规划问题研究的关键。首先，给出旅游路线规 划问题的形式化定义；然后，将文献中的旅游路线规划求解方法分为基于精确数学建模的求解、基于用户生成 内容的求解两大类，对各类方法的关键技术和存在的主要问题进行了较为详细的考察；最后，给出一个旅游路 线规划系统整体架构，对其中存在的重点和难点问题进行了分析，为旅游路线规划问题的研究提供理论支持的 同时指明了下一步的研究方向。 关键词：旅游路线规划；位置服务；轨迹挖掘；个性化推荐；上下文感知；定向问题；用户生成数据；全域旅游 中图分类号：TP301 文献标志码：A 文章编号：1673−4785(2019)01−0082−11 中文引用格式：常亮, 孙文平, 张伟涛, 等. 旅游路线规划研究综述[J]. 智能系统学报, 2019, 14(1): 82–92. 英文引用格式：CHANG Liang, SUN Wenping, ZHANG Weitao, et al. Review of tourism route planning[J]. CAAI transactions on intelligent systems, 2019, 14(1): 82–92. Review of tourism route planning CHANG Liang，SUN Wenping，ZHANG Weitao，BIN Chenzhong，GU Tianlong (Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China) Abstract: With the rapid development of tourism and surge in user sharing, information overload in tourism has be￾come an increasing problem. Currently, the key issue in tourism route planning is how to help tourists to develop person￾alized travel routes and enhance their travel experiences. In this paper, we first provide a formal definition of the tour￾ism route planning problem.. Then, we sort the methods used to solve this problem into two categories, i.e., those based on exact mathematical modeling and those based on user-generated content. We then present a detailed survey of the key technologies and difficulties of these methods. Lastly, we propose an overall framework for the tourism route planning system, analyze the key difficulties of the system, provide theoretical support for the study of tourism route planning, and suggest a future research direction. Keywords: tourism route planning; location-based service; trajectory mining; personalized recommendation; context￾aware; orientation problem; user-generated data; all-for-one tourism 在当前稳定的宏观经济和社会环境下，国民 旅游需求不断增加，旅游活动持续升温，“全域旅 游”的发展战略突破了传统景区与景点的资源观 念，延伸到农耕民俗、工业遗产等社会资源，对旅 游业的服务质量也提出了更高的要求。然而，随 着可选地点的急剧增加，如何根据用户需求帮助 用户快速进行旅行路线规划，成为全域旅游中亟 待解决的难点问题，使得相关旅游路线规划方法 的研究成为当前旅游领域的研究前沿。 目前，虽然旅行者在进行旅行规划时可以在 互联网上方便地查看相关信息，但仍然需要花费 大量时间和精力[1]。经常出现的现象是，许多旅 行者在事先花费了很多时间制定旅行路线，但最 终却又不得不选择跟团的形式进行旅行，因此旅 收稿日期：2018−04−04. 网络出版日期：2018−05−24. 基金项目：国家自然科学基金项 目 (61572146， U1501252， U1711263)；广西创新驱动重大专项项目 (AA17202024)； 广西自然科学基金项目 (2016GXNSFDA380006). 通信作者：宾辰忠. E-mail：binchenzhong@guet.edu.cn. 第 14 卷第 1 期 智 能 系 统 学 报 Vol.14 No.1 2019 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2019

第1期 常亮，等：旅游路线规划研究综述 ·83· 行者对于旅行路线规划相关服务的需求日益迫切。 terest,.POI)感兴趣的情况下，如何按照游客的相 关约束以及对POI的兴趣度得到适合的旅行路 1旅游路线规划理论 线。尽管现阶段互联网中存在大量与旅游相关 科学的旅游路线规划不仅有助于旅行者根据 的信息，但对于一个访问陌生城市的游客来说， 自己的时间和经费预算制定适合自己的游览路 这仍然是一项具有挑战性的任务，尤其是其涉及 线，还能够提升旅行者的旅行体验，使得旅行者 的因素很多，例如每个景点所需的游览时间、景 在旅行中有更多的时间和精力放在游览过程中。 点的开放时间和景点之间的旅行距离等。旅游路 在旅游路线规划问题的研究工作中，较早的 线规划问题的关键是：在满足游客时间和花费的 约束下选择更多匹配游客偏好的POI进行游览， 工作大多集中在利用OP问题(orienteering prob- lem)作为基本问题，通过不同的变型对旅游路线 最大化游客的满意度。在进行旅行规划时，要得 规划问题进行建模求解。这类工作的重点是准确 到高质量的解决方案，除了需要考虑多方面的因素， 建模旅游路线规划问题中的多方面因素，比如用 还需要根据不同标准建立相应的评价模型5。 户约束、景点开放时间和出行交通方式等，最终 本文将典型的旅游路线规划问题定义为5元 能得到一个或多个满足用户约束的精确路线规划 P=(POIs,TrafficCost,Profit,TConstraint,FCon- 结果。但是，这类工作无法对现实生活中旅游 straint),其中： 路线规划问题的各种因素进行完全建模。一方 1)POIs表示所有候选的POI,每个POI又具 面，由于旅游活动是一个动态的过程，在这个过 有多个属性，包括类型、位置、门票价格、开放时 程中有很多不确定的因素；另一方面，当兴趣点 间等： 的地理范围较大时，不能再将兴趣点仅仅当作一 2)TrafficCost表示在各个POI之间采用各种 个点进行建模，如一条观光河道，兴趣点的起点 不同的交通方式所需要的旅行时间和费用，主要 和终点可能相差很远。 的交通方式包括公共交通、骑行、步行等； 随着互联网的飞速发展，与日常信息相关的 3)Profit表示游客游览每个POI所能获得的 各类用户生成内容迅速增多。在旅游领域中，形 “收益”，通过对每个POI的客观打分以及游客的 成了多种形式的旅游时空轨迹数据，例如：GPS 主观感受进行加权计算而得，其中游客的主观感 轨迹、北斗导航信息、签到记录等。这些数据与 受又主要取决于游客的个人偏好： 用户分享的大量旅游经历和旅行照片等数据，共 4)TConstraint表示游客用于该次旅行的时间 同形成了旅游大数据。合理地利用这些数据进行 预算，包括游客该次旅行的总天数以及每天用于 旅游路线规划，是近期研究工作的一个热点。这 游览的时间数等； 类工作的优点是能够快速地得到符合现实情况的 5)FConstraint表示游客用于该次旅行的费用 可行解，帮助用户进行旅行规划，但难点在于合 预算。 理利用多源数据准确地挖掘用户的历史行为轨迹。 对于天气状况这种影响旅行的因素，我们将 其归类到POI的开放时间这个属性中。对于其他 2旅游路线规划问题描述 未考虑的因素，可以相应地对5元组进行扩展。 给定一个旅游路线规划问题之后，对该问题 游客到一个地方进行旅行时通常面临以下两 的求解是指找到关于各个POI访问日程和访问顺 个问题：首先是决定访问哪些景点，从而使自己 序的一套或多套方案，使得在满足游客的时间预 的旅行变得更加有趣；其次是确定每个旅行日的 算和费用预算等约束的前提下，游客所能获得的 路线，即确定对每个景点的访问顺序。这个过程 收益达到最大或者最佳。 需要考虑到多个参数和约束，如门票价格、天气 条件等。 3旅游路线规划问题求解方法 基于当前用户在进行旅行规划时所遇到的问 题，旅游路线规划问题便应运而生。其实旅游规 目前，相关文献中存在许多对旅游路线规划 划问题并不是一个新的问题，最早可追溯到旅行 问题进行求解的方法。本文将这些方法分为两大 商问题(traveling salesman problem,TSP)。由于 类：1)对旅游路线规划问题进行精确的数学建 TSP属于NP-Complete问题，大量研究工作主要 模，通过规划求解得到较为精确的规划方案； 集中在如何进行启发式求解。 2)利用用户生成内容(user generated content,.UGC) 个性化旅游路线规划问题比TSP问题更加复 进行路线挖掘，并结合用户的喜好和相关约束得 杂。总体上是指游客在对多个兴趣点(point of in- 到一条或多条可行路线

行者对于旅行路线规划相关服务的需求日益迫切。 1 旅游路线规划理论 科学的旅游路线规划不仅有助于旅行者根据 自己的时间和经费预算制定适合自己的游览路 线，还能够提升旅行者的旅行体验，使得旅行者 在旅行中有更多的时间和精力放在游览过程中。 在旅游路线规划问题的研究工作中，较早的 工作大多集中在利用 OP 问题 (orienteering prob￾lem) 作为基本问题，通过不同的变型对旅游路线 规划问题进行建模求解。这类工作的重点是准确 建模旅游路线规划问题中的多方面因素，比如用 户约束、景点开放时间和出行交通方式等，最终 能得到一个或多个满足用户约束的精确路线规划 结果[2]。但是，这类工作无法对现实生活中旅游 路线规划问题的各种因素进行完全建模。一方 面，由于旅游活动是一个动态的过程，在这个过 程中有很多不确定的因素；另一方面，当兴趣点 的地理范围较大时，不能再将兴趣点仅仅当作一 个点进行建模，如一条观光河道，兴趣点的起点 和终点可能相差很远。 随着互联网的飞速发展，与日常信息相关的 各类用户生成内容迅速增多。在旅游领域中，形 成了多种形式的旅游时空轨迹数据，例如：GPS 轨迹、北斗导航信息、签到记录等。 这些数据与 用户分享的大量旅游经历和旅行照片等数据，共 同形成了旅游大数据。合理地利用这些数据进行 旅游路线规划，是近期研究工作的一个热点。这 类工作的优点是能够快速地得到符合现实情况的 可行解，帮助用户进行旅行规划，但难点在于合 理利用多源数据准确地挖掘用户的历史行为轨迹[3]。 2 旅游路线规划问题描述 游客到一个地方进行旅行时通常面临以下两 个问题：首先是决定访问哪些景点，从而使自己 的旅行变得更加有趣；其次是确定每个旅行日的 路线，即确定对每个景点的访问顺序。这个过程 需要考虑到多个参数和约束，如门票价格、天气 条件等。 基于当前用户在进行旅行规划时所遇到的问 题，旅游路线规划问题便应运而生。其实旅游规 划问题并不是一个新的问题，最早可追溯到旅行 商问题 (traveling salesman problem，TSP)。由于 TSP 属于 NP-Complete 问题，大量研究工作主要 集中在如何进行启发式求解。 个性化旅游路线规划问题比 TSP 问题更加复 杂。总体上是指游客在对多个兴趣点 (point of in￾terest，POI) 感兴趣的情况下，如何按照游客的相 关约束以及对 POI 的兴趣度得到适合的旅行路 线 [4]。尽管现阶段互联网中存在大量与旅游相关 的信息，但对于一个访问陌生城市的游客来说， 这仍然是一项具有挑战性的任务，尤其是其涉及 的因素很多，例如每个景点所需的游览时间、景 点的开放时间和景点之间的旅行距离等。旅游路 线规划问题的关键是：在满足游客时间和花费的 约束下选择更多匹配游客偏好的 POI 进行游览， 最大化游客的满意度。在进行旅行规划时，要得 到高质量的解决方案，除了需要考虑多方面的因素， 还需要根据不同标准建立相应的评价模型[5-6]。 ⟨ ⟩ 本文将典型的旅游路线规划问题定义为 5 元 组 P= POIs，TrafficCost，Profit，TConstraint，FCon￾straint ，其中： 1)POIs 表示所有候选的 POI，每个 POI 又具 有多个属性，包括类型、位置、门票价格、开放时 间等； 2)TrafficCost 表示在各个 POI 之间采用各种 不同的交通方式所需要的旅行时间和费用，主要 的交通方式包括公共交通、骑行、步行等； 3)Profit 表示游客游览每个 POI 所能获得的 “收益”，通过对每个 POI 的客观打分以及游客的 主观感受进行加权计算而得，其中游客的主观感 受又主要取决于游客的个人偏好； 4)TConstraint 表示游客用于该次旅行的时间 预算，包括游客该次旅行的总天数以及每天用于 游览的时间数等； 5)FConstraint 表示游客用于该次旅行的费用 预算。 对于天气状况这种影响旅行的因素，我们将 其归类到 POI 的开放时间这个属性中。对于其他 未考虑的因素，可以相应地对 5 元组进行扩展。 给定一个旅游路线规划问题之后，对该问题 的求解是指找到关于各个 POI 访问日程和访问顺 序的一套或多套方案，使得在满足游客的时间预 算和费用预算等约束的前提下，游客所能获得的 收益达到最大或者最佳。 3 旅游路线规划问题求解方法 目前，相关文献中存在许多对旅游路线规划 问题进行求解的方法。本文将这些方法分为两大 类 ：1) 对旅游路线规划问题进行精确的数学建 模，通过规划求解得到较为精确的规划方案； 2) 利用用户生成内容 (user generated content，UGC) 进行路线挖掘，并结合用户的喜好和相关约束得 到一条或多条可行路线[7]。 第 1 期 常亮，等：旅游路线规划研究综述 ·83·

84 智能系统学报 第14卷 3.1基于精确数学建模的求解 历史、休闲、购物等，并且为每个类别提供不同的 从建模角度进行求解时，关键是对旅游路线 收益，在不违反最大旅行成本限制的情况下找到 规划问题进行精准建模，可以通过对T$P模型加 所有的高效解决方案。Schilde等I通过对多目 入不同参数和约束进行扩展得到不同的求解模型。 标OP问题在城市旅游中的运用进行研究，开发 这类工作又可以按照路线数量分为2类：1)求解 和应用了2种用于多目标定向问题的启发式解决 出单条路线，找到能够满足用户旅行约束和用户 方法，这2种方法考虑到了每个旅游者在选择和 对POI的偏好并且利润最大化的单程旅游线路； 访问兴趣点（例如博物馆、教堂）时对不同的类别 2)求解出多条路线。 可能有不同偏好的情况，使用帕累托蚁群优化算 3.11单路线求解方法 法将可变邻域搜索方法扩展到多目标情况。通过 旅游路线规划问题的单路线求解，可以利用 来自现实世界中几个城市的实例对2种算法进行 单一目标旅行商问题增加收益目标进行变型建 了测试，结果表明，2种方法对解决多目标定向问 模，将节点之间的连接与收益和旅行成本相关 题都有很好的效果，能够根据不同游客对不同景 联。其目标是：在所有节点的子集上找到一条回 点的偏好程度设计出使游客满意度最大的个性化 路，使得收益最大化，同时旅行成本最小化」 旅游路线。 OP问题是上述模型的一个变型，通常用于寻 弧定向问题将传统OP中的收益不再放在节 找在给定旅行花费的条件下使得总收益最大的路 点中，而是放在边上，其中每条边只能访问一次， 线。例如，Souffriau等提出了OP问题在城市旅 用边上的取值来表示景点的得分或者道路的状 游中的应用，给出了一个综合人工智能和元启发 况。Lu等将目标放在寻找风景最优美的路线 式的方法。在已有的关于旅游路线规划的研究中 上而不是距离最短的路线上，将道路网络视为空 绝大多数使用OP及其扩展建模不同变型。 间网络，利用空间数据领域中的椭圆修剪和空间 具有时间窗口的OP变型是目前的一个研究 索引技术，提出了一系列元启发式算法来解决大规 热点。在该变型中考虑了对于图中的每个节点可 模道路网络中快速响应的问题；实验表明，该方 能在不同的时间窗口内访问的情况，因此能够在 法在推荐结果的准确性和效率上都有很大的提 建模时加入兴趣点的开放时间因素。例如，Gun- awan等.1o提出了一种迭代本地搜索算法，使用 升。而在之后的工作中，该作者进一步提出了具 有时间依赖的弧定向问题模型，在道路网络的边 贪心方法生成初始可行解，基于轮盘选择的方法 插入非计划节点。在之后的工作，Gunawan等 中同时融合旅行花费和吸引力值，在满足用户时间 约束的前提下得到用户最喜欢的路线规划结果。 进一步引入模拟退火算法，以较小的概率接受较 通过上述工作可以发现，在建模时考虑到多 差的解决方案，在一定程度上解决陷入局部最优 的问题。时间窗对传统OP问题的性质及其解决 方面因素能够提高路线规划结果的准确性，如表1 算法有很大的影响。然而，因为不同景点可能在 所示。此外，还有一些OP变型可用于建模旅游 路线规划问题中更加具体的内容61)，如可能需 开放时间上有所不同，例如，大型灯光演出时间 为夜晚，公园开放时间在白天，所以传统OP中通 要多次访问或长时间访问一个POL,这些变型对 过重新对访问点排序来减少旅行时间的方法在这 于提高具体问题推荐结果的准确性有很大帮助。 里并不适用。 表1建模因素对比 具有时间依赖的OP问题在进行路线规划时 Table 1 Modeling factors'comparison 将时间因素加入边的代价中，从而可以对旅行中 文献 开放时间 交通时间 景点类型 道路状况 在景点之间采用不同交通方式的情况进行建模。 [10] 在此基础上，Verbeeck等提出了一种基于蚁群 [12] 算法的快速本地搜索元启发式方法，将蚁群算法 的原理与包含时间依赖的本地搜索方法相结合， [13] 快速给出有效解决方案。通过实验表明，该算法 [14] 能够在花费很少计算时间的情况下获得高质量的 [15] 路线规划结果，保证在出现新的可用交通信息时 快速更新路线，帮助游客快速到达目的地。 3.1.2多路线求解方法 多目标OP问题是OP的多目标变型，每个节 用双目标TSP求解多路线的扩展变型被称为 点（即PO)可以被分配给不同的类别，例如文化、 带利润的车辆路由问题。该问题中，不再是强制

3.1 基于精确数学建模的求解 从建模角度进行求解时，关键是对旅游路线 规划问题进行精准建模，可以通过对 TSP 模型加 入不同参数和约束进行扩展得到不同的求解模型。 这类工作又可以按照路线数量分为 2 类：1) 求解 出单条路线，找到能够满足用户旅行约束和用户 对 POI 的偏好并且利润最大化的单程旅游线路； 2) 求解出多条路线。 3.1.1 单路线求解方法 旅游路线规划问题的单路线求解，可以利用 单一目标旅行商问题增加收益目标进行变型建 模，将节点之间的连接与收益和旅行成本相关 联。其目标是：在所有节点的子集上找到一条回 路，使得收益最大化，同时旅行成本最小化[8]。 OP 问题是上述模型的一个变型，通常用于寻 找在给定旅行花费的条件下使得总收益最大的路 线。例如，Souffriau 等 [8]提出了 OP 问题在城市旅 游中的应用，给出了一个综合人工智能和元启发 式的方法。在已有的关于旅游路线规划的研究中 绝大多数使用 OP 及其扩展建模不同变型。 具有时间窗口的 OP 变型是目前的一个研究 热点。在该变型中考虑了对于图中的每个节点可 能在不同的时间窗口内访问的情况，因此能够在 建模时加入兴趣点的开放时间因素。例如，Gun￾awan 等 [9-10]提出了一种迭代本地搜索算法，使用 贪心方法生成初始可行解，基于轮盘选择的方法 插入非计划节点。在之后的工作，Gunawan 等 [11] 进一步引入模拟退火算法，以较小的概率接受较 差的解决方案，在一定程度上解决陷入局部最优 的问题。时间窗对传统 OP 问题的性质及其解决 算法有很大的影响。然而，因为不同景点可能在 开放时间上有所不同，例如，大型灯光演出时间 为夜晚，公园开放时间在白天，所以传统 OP 中通 过重新对访问点排序来减少旅行时间的方法在这 里并不适用。 具有时间依赖的 OP 问题在进行路线规划时 将时间因素加入边的代价中，从而可以对旅行中 在景点之间采用不同交通方式的情况进行建模。 在此基础上，Verbeeck 等 [12]提出了一种基于蚁群 算法的快速本地搜索元启发式方法，将蚁群算法 的原理与包含时间依赖的本地搜索方法相结合， 快速给出有效解决方案。通过实验表明，该算法 能够在花费很少计算时间的情况下获得高质量的 路线规划结果，保证在出现新的可用交通信息时 快速更新路线，帮助游客快速到达目的地。 多目标 OP 问题是 OP 的多目标变型，每个节 点 (即 POI) 可以被分配给不同的类别，例如文化、 历史、休闲、购物等，并且为每个类别提供不同的 收益，在不违反最大旅行成本限制的情况下找到 所有的高效解决方案。Schilde 等 [13]通过对多目 标 OP 问题在城市旅游中的运用进行研究，开发 和应用了 2 种用于多目标定向问题的启发式解决 方法，这 2 种方法考虑到了每个旅游者在选择和 访问兴趣点 (例如博物馆、教堂) 时对不同的类别 可能有不同偏好的情况，使用帕累托蚁群优化算 法将可变邻域搜索方法扩展到多目标情况。通过 来自现实世界中几个城市的实例对 2 种算法进行 了测试，结果表明，2 种方法对解决多目标定向问 题都有很好的效果，能够根据不同游客对不同景 点的偏好程度设计出使游客满意度最大的个性化 旅游路线。 弧定向问题将传统 OP 中的收益不再放在节 点中，而是放在边上，其中每条边只能访问一次， 用边上的取值来表示景点的得分或者道路的状 况。Lu 等 [14]将目标放在寻找风景最优美的路线 上而不是距离最短的路线上，将道路网络视为空 间网络，利用空间数据领域中的椭圆修剪和空间 索引技术，提出了一系列元启发式算法来解决大规 模道路网络中快速响应的问题；实验表明，该方 法在推荐结果的准确性和效率上都有很大的提 升。而在之后的工作中，该作者进一步提出了具 有时间依赖的弧定向问题模型，在道路网络的边 中同时融合旅行花费和吸引力值，在满足用户时间 约束的前提下得到用户最喜欢的路线规划结果[15]。 通过上述工作可以发现，在建模时考虑到多 方面因素能够提高路线规划结果的准确性，如表 1 所示。此外，还有一些 OP 变型可用于建模旅游 路线规划问题中更加具体的内容[16-19] ，如可能需 要多次访问或长时间访问一个 POI，这些变型对 于提高具体问题推荐结果的准确性有很大帮助。 3.1.2 多路线求解方法 用双目标 TSP 求解多路线的扩展变型被称为 带利润的车辆路由问题。该问题中，不再是强制 表 1 建模因素对比 Table 1 Modeling factors’ comparison 文献 开放时间 交通时间 景点类型 道路状况 [10] √ [12] √ [13] √ [14] √ [15] √ √ ·84· 智 能 系 统 学 报 第 14 卷

第1期 常亮，等：旅游路线规划研究综述 ·85· 性地访问整个节点集合，而是在访问节点时收集 多不同。首先，由于旅游活动是一个动态的过 利润，且利润的收集分布在具有有限容量的几辆 程，有很多不确定的因素，无法进行准确建模，而 车上。团队定向问题是该问题的一个变型，多用 恰是这些不确定因素可能对路线预测的准确性起 于旅游路线规划问题的多路线求解，其目标是找 着决定性的作用2。此外，在对旅游路线规划问 到在最大长度限制条件下的k条路径（其中每个 题的建模求解时，基于兴趣点的考虑，只是将兴 节点最多访问一次)，并且具有最大的总收益。 趣点作为一个点，并没有考虑到兴趣点的实际大 带时间窗口的团队定向问题中加入了对POI 小，因此这种方法只适用于博物馆、公园、小广场 在特定的时间窗口进行访问的限制，从而可以适 等有固定出口且范围较小的景点，对于相对较大 应更多场景。Lin等提出了一个基于模拟退火 的景点，这种方法就会与实际情况有较大出入， 算法的启发式算法，在每次迭代中，通过对当前 如在游览一条观光河道时，兴趣点的起点和终点 解以相等的概率应用移动交换，插入或倒置其中 可能相差很远，这时再从起点进行路线规划就变 的一个节点来获得相邻解，如果它比当前最佳找 得不切实际。 到的解决方案更具有收益，则新的解决方案被采 3.2基于用户生成内容的求解 用并成为当前的解决方案，这个概率会随着损失 近些年，由于信息的传播和共享越来越便捷， 的增加而减少，应用上述方法进行一定数量的迭 互联网上积累了大量的集体智慧相关数据，影响 代之后，就会进一步优化用局部搜索方法找到目 着人类生活的许多领域，尤其是旅游业和旅游行 前最佳解。 为。研究表明，超过87%的客户依靠集体智慧为 带时间依赖和时间窗口的团队定向问题是 旅行做出决定，例如旅行者在预订住宿之前通常 指：给出一组节点和每对节点之间的旅行时间， 会查看相关的评分和评论。虽然许多旅游网站 其中每个节点与利润、访问时间和时间窗口相关 提供关于目的地和旅行路线的信息，但是整合和 联，目的是找到从起始节点到目的节点间的固定 比较来自海量用户的不同类型信息需要大量时间 数量且不相交的路径，每条路径不超过给定的时 和精力。 间限制，在不违反其时间窗口的情况下通过访问 在旅游领域中，用户在进行一次旅行后，通常 所有路径中的节点来最大化收集总利润。Gar- 会分享自己的经验和评论，形成了包括用户评 cia等2提出了2种不同的方法来解决上述问题： 论、照片、签到数据、旅游游记和GPS轨迹等信 1)利用预先计算，得到所有POI对之间的平均旅 息的大量用户生成内容，这些数据为便利行程计 行时间，约减掉时间依赖限制；2)在旅行时间上 划提供了极大的机会m。虽然一个单独的评论或 加入时间依赖，但是该方法是基于周期性服务时 者旅游游记中可能存在噪声或者偏见，但是将来 间的简化假设，不符合现实中城市的交通网络。 自大量用户的贡献的内容作为一个整体可以有效 此外还有一些用于模拟旅游路线规划问题 地抓住一个景点的本质。因此，越来越多的研究 的TOP变型，考虑到问题的更多属性或对不同属 利用空间分析和数据挖掘等技术对这些内容进行 性的多个约束，Luo等2引入了一种用于T0P变 分析，得到用户的相关偏好和历史轨迹信息，发 型的启发式算法，该方法在旅行中插入节点时应 现游客间的相似性，实现旅游路线的推荐2。 用2种不同的优先级规则，算法在解决方案的质 3.2.1利用用户GPS轨迹进行求解 量和执行时间方面优于其他启发式算法，能够在 随着配备GPS功能的设备数量不断增加，越 较短时间内得到由精确算法求解实例中的最优 来越多的轨迹被连续地产生和分享，也正在改变 解；Li等2制定了带容量约束和时间窗口的团队 着人们与网络的交互方式。基于这些轨迹信息， 定向问题，增加了服务节点在有限时间可用性的 一些应用问题变得可行，例如旅游路线规划问 约束，并使用整数线性规划求解方法获得了精确 题，GPS轨迹中包含丰富的信息，可以挖掘用户 的解，然而这种方法不适合进行实时应用。 在一个位置花费的时间和对不同位置的访问顺序 综上所述，利用OP的多种变型对旅游路线 等，这些信息可以被用来挖掘指定区域中的热门 规划问题进行建模求解的方法，可以准确建模旅 景点和一般的旅行路线，从而进一步改进路线推荐。 游路线规划问题中多方面的因素，如用户约束」 Cui等Bo使用用户历史GPS信息挖掘用户的 景点开放时间和出行交通方式等，能得到一个或 旅行习惯，提出了2种个性化的旅游路线推荐算 多个满足用户约束的精确路线规划结果，但是这 法，能够在推荐时考虑用户的个人偏好，提高推 种方法与现实生活中的旅游路线规划问题还有很 荐结果的个性化程度。)首先使用协同过滤技术

性地访问整个节点集合，而是在访问节点时收集 利润，且利润的收集分布在具有有限容量的几辆 车上。团队定向问题是该问题的一个变型，多用 于旅游路线规划问题的多路线求解，其目标是找 到在最大长度限制条件下的 k 条路径 (其中每个 节点最多访问一次)，并且具有最大的总收益。 带时间窗口的团队定向问题中加入了对 POI 在特定的时间窗口进行访问的限制，从而可以适 应更多场景。Lin 等 [20]提出了一个基于模拟退火 算法的启发式算法，在每次迭代中，通过对当前 解以相等的概率应用移动交换，插入或倒置其中 的一个节点来获得相邻解，如果它比当前最佳找 到的解决方案更具有收益，则新的解决方案被采 用并成为当前的解决方案，这个概率会随着损失 的增加而减少，应用上述方法进行一定数量的迭 代之后，就会进一步优化用局部搜索方法找到目 前最佳解。 带时间依赖和时间窗口的团队定向问题是 指：给出一组节点和每对节点之间的旅行时间， 其中每个节点与利润、访问时间和时间窗口相关 联，目的是找到从起始节点到目的节点间的固定 数量且不相交的路径，每条路径不超过给定的时 间限制，在不违反其时间窗口的情况下通过访问 所有路径中的节点来最大化收集总利润。Gar￾cia 等 [21]提出了 2 种不同的方法来解决上述问题： 1) 利用预先计算，得到所有 POI 对之间的平均旅 行时间，约减掉时间依赖限制；2) 在旅行时间上 加入时间依赖，但是该方法是基于周期性服务时 间的简化假设，不符合现实中城市的交通网络。 此外还有一些用于模拟旅游路线规划问题 的 TOP 变型，考虑到问题的更多属性或对不同属 性的多个约束，Luo 等 [22]引入了一种用于 TOP 变 型的启发式算法，该方法在旅行中插入节点时应 用 2 种不同的优先级规则，算法在解决方案的质 量和执行时间方面优于其他启发式算法，能够在 较短时间内得到由精确算法求解实例中的最优 解；Li 等 [23]制定了带容量约束和时间窗口的团队 定向问题，增加了服务节点在有限时间可用性的 约束，并使用整数线性规划求解方法获得了精确 的解，然而这种方法不适合进行实时应用。 综上所述，利用 OP 的多种变型对旅游路线 规划问题进行建模求解的方法，可以准确建模旅 游路线规划问题中多方面的因素，如用户约束、 景点开放时间和出行交通方式等，能得到一个或 多个满足用户约束的精确路线规划结果，但是这 种方法与现实生活中的旅游路线规划问题还有很 多不同。首先，由于旅游活动是一个动态的过 程，有很多不确定的因素，无法进行准确建模，而 恰是这些不确定因素可能对路线预测的准确性起 着决定性的作用[24]。此外，在对旅游路线规划问 题的建模求解时，基于兴趣点的考虑，只是将兴 趣点作为一个点，并没有考虑到兴趣点的实际大 小，因此这种方法只适用于博物馆、公园、小广场 等有固定出口且范围较小的景点，对于相对较大 的景点，这种方法就会与实际情况有较大出入， 如在游览一条观光河道时，兴趣点的起点和终点 可能相差很远，这时再从起点进行路线规划就变 得不切实际。 3.2 基于用户生成内容的求解 近些年，由于信息的传播和共享越来越便捷， 互联网上积累了大量的集体智慧相关数据，影响 着人类生活的许多领域，尤其是旅游业和旅游行 为。研究表明，超过 87% 的客户依靠集体智慧为 旅行做出决定，例如旅行者在预订住宿之前通常 会查看相关的评分和评论[25]。虽然许多旅游网站 提供关于目的地和旅行路线的信息，但是整合和 比较来自海量用户的不同类型信息需要大量时间 和精力[26]。 在旅游领域中，用户在进行一次旅行后，通常 会分享自己的经验和评论，形成了包括用户评 论、照片、签到数据、旅游游记和 GPS 轨迹等信 息的大量用户生成内容，这些数据为便利行程计 划提供了极大的机会[27]。虽然一个单独的评论或 者旅游游记中可能存在噪声或者偏见，但是将来 自大量用户的贡献的内容作为一个整体可以有效 地抓住一个景点的本质。因此，越来越多的研究 利用空间分析和数据挖掘等技术对这些内容进行 分析[28] ，得到用户的相关偏好和历史轨迹信息，发 现游客间的相似性，实现旅游路线的推荐[29]。 3.2.1 利用用户 GPS 轨迹进行求解 随着配备 GPS 功能的设备数量不断增加，越 来越多的轨迹被连续地产生和分享，也正在改变 着人们与网络的交互方式。基于这些轨迹信息， 一些应用问题变得可行，例如旅游路线规划问 题，GPS 轨迹中包含丰富的信息，可以挖掘用户 在一个位置花费的时间和对不同位置的访问顺序 等，这些信息可以被用来挖掘指定区域中的热门 景点和一般的旅行路线，从而进一步改进路线推荐。 Cui 等 [30]使用用户历史 GPS 信息挖掘用户的 旅行习惯，提出了 2 种个性化的旅游路线推荐算 法，能够在推荐时考虑用户的个人偏好，提高推 荐结果的个性化程度。1) 首先使用协同过滤技术 第 1 期 常亮，等：旅游路线规划研究综述 ·85·

·86· 智能系统学报 第14卷 估计用户的旅行行为频率，然后基于朴素贝叶斯 将该照片的拍摄者认定为本地居民，否则认为是 模型生成一个符合用户旅行习惯的路线。2)在路 游客拍摄的照片。最后利用DBSCAN算法从照 线生成的过程中考虑了用户冷启动问题，利用所 片数据中识别出地标建筑，并按照流行度进行排 有用户的隐含因子向量的平均值作为未挖掘出用 序。实验数据表明，该方法能够给用户推荐一个 户旅行习惯的用户的隐含因子向量；此外，该方 包括合适景点且路线长度适中的旅游路线，但这 法还融合了用户旅行习惯中的最大可能出行距 种方法存在一定的缺点，主要体现在计算兴趣点 离，能够更好地限制生成路线的长度来满足用户 流行度时并没有考虑游客的经验和知识。 的历史出行习惯。实验结果表明，这2种方法在 wei等提出了基于集体知识的路线推理框 召回率和准确率上均有更好的表现，但这两种方 架。首先给定一个位置序列和时间跨度，通过以 法在处理用户旅行习惯时，并没有考虑用户旅 相互加强的方式聚合用户照片数据，得到流行的 行习惯的序列性，也没有考虑用户旅行时的动 路线信息，之后路线算法根据用户指定的查询来 态性，在生成路线结果的合理性上存在一定的 构造top-k路线。算法可以在0.5s内找到前3个 偏差。 路线，与其相应的地理实况相比，距离误差小于 32.2利用带地理标签的照片进行求解 300m。 目前，社交网站中存在大量带地理标签的照 Tai等B使用关联规则挖掘和序列模式挖掘 片数据，从这些照片数据中分析历史用户位置在 从用户带地理标签的照片中提取用户对热门景点 地理空间中的分布特征和用户位置随时间的变化 的访问序列，从而进一步得到流行路线信息，之 特征可以挖掘出用户的行进路线，这些路线可以 后基于用户的历史访问信息，从这些路线中挑选 加入到用于路线推荐的知识库中，通过这些挖掘 出最适合该用户的路线推荐给用户：Lu等B使用 出的路线帮助新用户进行旅游路线规划.可以提 从Panoramio中收集的大量带地理标签的照片， 高路线规划的准确度和个性化程度。 提出一个旅行路线生成算法，该方法考虑到在每 利用带地理标签的用户照片进行旅游路线规 个位置花费的时间、总旅行时间和用户偏好。 上述工作并没有将用户行为习惯、兴趣偏好 划的工作是当前旅游路线规划问题研究领域中的 和路线的流行度进行结合，路线规划结果的个性 一大热点。其中一类工作的重点是从地理标签照 化程度不高。此外，在对用户进行路线规划时并 片中挖掘出隐含信息，进而得到用户的旅行习 没有过多地考虑上下文信息，如天气、访问时间、 惯、移动模式或兴趣偏好等信息为用户进行路线 季节等，而这些因素往往影响了旅行者的访问习 规划。而另一类将重点放在从照片中挖掘序列特 惯，进而使得推荐结果的准确性大大降低。文 性，之后利用挖掘到的序列特性结合概率模型， 献[35-36]基于以上不足出发，在利用用户照片数 得到从一个景点最有可能去往的下一个景点信 据的同时加入更多的上下文信息来提高路线推荐 息，最终生成路线规划结果，这类工作的推荐结 结果的准确性。例如，Arain等Bm利用带地理标签 果更倾向于路线的流行程度。 的照片提取旅游景点语义信息的同时挖掘用户喜 Sun等B将重点放在挖掘旅游路线中的道路 好信息，在进行推荐时考虑到用户的当前上下文 片段信息上，而不是挖掘用户相关信息，通过计 信息，包括时空上下文信息、社交上下文信息和 算得到道路片段的流行度进行两个景点间的道路 天气上下文信息。Huang基于游客对景点进行 推荐。首先利用空间聚类对照片进行分类，而在 访问时在上下文存在相似性的原理出发，提出一 噪音数据的处理上，提出一种熵过滤方法从照片 种基于启发式的上下文相似度的计算方法，能够 数据中去除掉与旅行无关的照片，具体实现如式 准确刻画用户间的上下文相似性，从而在对用户 (1)、式(2)： 进行路线推荐的过程中加入上下文信息，给用户 Mon(ar） 提供更加准确的推荐；这种方法不但能够用于照 E(w=- P(u)log P(u) (1) 片数据，同样可以在用户GPS轨迹、签到信息等 D.(u) 数据中使用，提供具有上下文感知的推荐结果。 P(W)= (2) 3.2.3利用用户签到数据进行求解 ΣD.m 随着基于位置的服务的兴起，Facebook等社 式中：D()是在目标区域用户u在第i个月的拍 交网络提供了用户“签到”的服务，用户通过该服 照天数；Mon(u)是用户u在目标区域拍照的月 务可以将自己当前的访问地点与时间信息展现在 数，作者使用一个阈值E(),当超过这个值时，就 自己的主页上。基于签到数据进行路线规划是近

估计用户的旅行行为频率，然后基于朴素贝叶斯 模型生成一个符合用户旅行习惯的路线。2) 在路 线生成的过程中考虑了用户冷启动问题，利用所 有用户的隐含因子向量的平均值作为未挖掘出用 户旅行习惯的用户的隐含因子向量；此外，该方 法还融合了用户旅行习惯中的最大可能出行距 离，能够更好地限制生成路线的长度来满足用户 的历史出行习惯。实验结果表明，这 2 种方法在 召回率和准确率上均有更好的表现，但这两种方 法在处理用户旅行习惯时，并没有考虑用户旅 行习惯的序列性，也没有考虑用户旅行时的动 态性，在生成路线结果的合理性上存在一定的 偏差。 3.2.2 利用带地理标签的照片进行求解 目前，社交网站中存在大量带地理标签的照 片数据，从这些照片数据中分析历史用户位置在 地理空间中的分布特征和用户位置随时间的变化 特征可以挖掘出用户的行进路线，这些路线可以 加入到用于路线推荐的知识库中，通过这些挖掘 出的路线帮助新用户进行旅游路线规划，可以提 高路线规划的准确度和个性化程度。 利用带地理标签的用户照片进行旅游路线规 划的工作是当前旅游路线规划问题研究领域中的 一大热点。其中一类工作的重点是从地理标签照 片中挖掘出隐含信息，进而得到用户的旅行习 惯、移动模式或兴趣偏好等信息为用户进行路线 规划。而另一类将重点放在从照片中挖掘序列特 性，之后利用挖掘到的序列特性结合概率模型， 得到从一个景点最有可能去往的下一个景点信 息，最终生成路线规划结果，这类工作的推荐结 果更倾向于路线的流行程度。 Sun 等 [31]将重点放在挖掘旅游路线中的道路 片段信息上，而不是挖掘用户相关信息，通过计 算得到道路片段的流行度进行两个景点间的道路 推荐。首先利用空间聚类对照片进行分类，而在 噪音数据的处理上，提出一种熵过滤方法从照片 数据中去除掉与旅行无关的照片，具体实现如式 (1)、式 (2)： E(u) = − Mon( ∑u) i Pi(u)logPi(u) (1) Pi(u) = Di(u) Mon( ∑u) i Di(u) (2) 式中：Di (u) 是在目标区域用户 u 在第 i 个月的拍 照天数；Mon(u) 是用户 u 在目标区域拍照的月 数，作者使用一个阈值 E(u)，当超过这个值时，就 将该照片的拍摄者认定为本地居民，否则认为是 游客拍摄的照片。最后利用 DBSCAN 算法从照 片数据中识别出地标建筑，并按照流行度进行排 序。实验数据表明，该方法能够给用户推荐一个 包括合适景点且路线长度适中的旅游路线，但这 种方法存在一定的缺点，主要体现在计算兴趣点 流行度时并没有考虑游客的经验和知识。 Wei 等 [32]提出了基于集体知识的路线推理框 架。首先给定一个位置序列和时间跨度，通过以 相互加强的方式聚合用户照片数据，得到流行的 路线信息，之后路线算法根据用户指定的查询来 构造 top-k 路线。算法可以在 0.5 s 内找到前 3 个 路线，与其相应的地理实况相比，距离误差小于 300 m。 Tai 等 [33]使用关联规则挖掘和序列模式挖掘 从用户带地理标签的照片中提取用户对热门景点 的访问序列，从而进一步得到流行路线信息，之 后基于用户的历史访问信息，从这些路线中挑选 出最适合该用户的路线推荐给用户；Lu 等 [34]使用 从 Panoramio 中收集的大量带地理标签的照片， 提出一个旅行路线生成算法，该方法考虑到在每 个位置花费的时间、总旅行时间和用户偏好。 上述工作并没有将用户行为习惯、兴趣偏好 和路线的流行度进行结合，路线规划结果的个性 化程度不高。此外，在对用户进行路线规划时并 没有过多地考虑上下文信息，如天气、访问时间、 季节等，而这些因素往往影响了旅行者的访问习 惯，进而使得推荐结果的准确性大大降低。文 献[35-36]基于以上不足出发，在利用用户照片数 据的同时加入更多的上下文信息来提高路线推荐 结果的准确性。例如，Arain 等 [37]利用带地理标签 的照片提取旅游景点语义信息的同时挖掘用户喜 好信息，在进行推荐时考虑到用户的当前上下文 信息，包括时空上下文信息、社交上下文信息和 天气上下文信息。Huang[38]基于游客对景点进行 访问时在上下文存在相似性的原理出发，提出一 种基于启发式的上下文相似度的计算方法，能够 准确刻画用户间的上下文相似性，从而在对用户 进行路线推荐的过程中加入上下文信息，给用户 提供更加准确的推荐；这种方法不但能够用于照 片数据，同样可以在用户 GPS 轨迹、签到信息等 数据中使用，提供具有上下文感知的推荐结果。 3.2.3 利用用户签到数据进行求解 随着基于位置的服务的兴起，Facebook 等社 交网络提供了用户“签到”的服务，用户通过该服 务可以将自己当前的访问地点与时间信息展现在 自己的主页上。基于签到数据进行路线规划是近 ·86· 智 能 系 统 学 报 第 14 卷