基于用户需求的旅游路线推荐方法

李 旭，李景文,2+，俞 娜

(1.桂林理工大学 测绘地理信息学院，广西 桂林 541006；2.桂林理工大学 广西空间信息与测绘重点实验室，广西 桂林 541006)

0 引 言

随着智能移动设备和信息技术的飞速发展，使得过去求量型旅游方式转向为求质型旅游方式，在用户游玩过程中越来越注重个性化旅行体验。因此体现用户需求的旅游路线推荐技术成为了研究热点[1,2]。如何根据用户需求智能设计个性化旅游路线，为用户提供精准旅游信息服务，为旅游企业创造出更大的旅游经济价值已成为智慧旅游建设的重点任务之一[3]。Han等[4]根据旅行者的历史旅行轨迹，建立了地标推荐模型，以帮助旅行者制定旅行计划。林青等[5]根据时间地理学理论，计算时空可达性好的景点组合，提出了一种考虑游客时间成本的旅游线路推荐算法，提升了用户旅游的满意度。刘艳秋等[6]根据用户的评论和景点评分信息，提出了一种基于Word2vec和LDA的推荐模型，并将该模型用于旅游路线推荐中。Salas-Olmedo等[7]利用Foursquare(观光)、Panoramio(消费)和Twitter(社交活动)数据，研究了游客的旅行轨迹，验证了不同景点情境特征下游客的旅游活动存在差异。

虽然以上研究都取得了一定的进展，但研究角度单一，缺乏对用户需求及其关联因素的统一分析，不能最大程度体现个性化推荐结果。基于此，本文提出一种基于用户需求的旅游路线推荐方法，通过景点评分方法实现基于用户需求的景点推荐，在此基础上根据旅行时间、费用等约束条件建立旅游路线推荐模型，并利用嵌入混沌扰动和方差判定准则的模拟退火算法求解该模型，从而为用户推荐科学合理的旅游路线，满足其在不同情境下的旅游需求[8,9]。

1 理论基础

1.1 问题分析

轨迹f由一系列具有时序的GPS点组成f=(p1,p2,…pn)。 其中，n表示GPS点数量，p=(lat,lng,t)，lat,lng为该点的纬度和经度，t为该点的时间戳。定义score(s) 为景点s的得分，景点及景点间轨迹片段构成有向景区图G=(S,F)， 其中，S为景点集合，F为连接景点的轨迹集合。

(1)

基于以上分析，旅游路线定制问题可表述为在轨迹集合F中发现得分最高的旅游路线，其中，景点得分是基于景点流行度、用户偏好和景点游玩时间等这些用户个人需求的。因此，为了解决该问题，构建体现用户偏好的景点评分方法与包含约束条件的旅游路线定制模型成为旅游路线定制的关键。

1.2 基于用户需求的景点评分方法

基于用户需求的景点评分方法主要包括3个方面的内容：一是基于景点流行度的评分;二是基于用户游玩时间的评分;三是基于景点游玩时间的评分。从这3个方面对景点和用户需求进行分析，既能给用户推荐符合个人喜好且热度较高的景点，又能将景点最合适的游玩时间推荐给用户。

1.2.1 基于景点流行度的评分

用户在某个地区旅游时，该地区的热门景点是最先吸引用户关注的(例如，桂林的漓江、象鼻山等)，因此，针对热门景点对用户的影响，本文提出景点流行度的概念。

(2)

1.2.2 基于用户游玩时间的评分

不同的用户都有自己偏好的景点类型，对于自己喜欢的景点，游玩的时间就会相对长一些，而用户对于自己不感兴趣的景点，游玩的时间就会相对短一些。因此，本文基于用户游玩时间的评分来判断用户对该景点的喜好。

(3)

由景点平均游玩时间得到游客对于某类型景点的个人偏好，其公式为

(4)

1.2.3 基于景点游玩时间的评分

实际旅行过程中，大部分景点的游玩时间都有限制和规定，并且，每个景点的最佳游玩时间也不同。比如，桂林的独秀峰王城景区的游玩时间为8∶00～18∶00，在这个时间段用户能够进入景区游玩，超出这个时间范围则不能游玩该景区。因此，针对景点游玩时间的问题，本文提出了基于景点最佳游玩时间的评分。

(5)

式中：tmax表示景点关闭时间，tmin表示景点开始游玩的时间。

1.3 旅游路线推荐模型

在景点评分方法挖掘出符合用户需求的景点的基础上，充分考虑旅行时间和旅行费用等约束条件对旅行的影响，建立时间和旅行费用约束下的旅游路线定制模型[10]，使得推荐的旅游路线更加符合生活实际。

根据1.2节中的景点评分方法可以得到景点si的评分为

(6)

式中：ω取0.4，让用户偏好占更大比重，凸显用户需求。

因此，旅游路线得分为

(7)

根据以上分析，旅游路线定制模型及其约束条件如下

(8)

(9)

(10)

(11)

(12)

(13)

其中，式(7)是旅游路线定制模型的目标函数，定制的旅游路线为得分最高的旅游路线，xi,j是决策变量，当景点sj是景点si的下一个游玩景点，则xi,j=1， 否则为0。式(9)-式(10)保证定制的旅游路线的起点是s1，终点是sn。式(11)确保定制的旅游路线连贯且景点不重复。式(12) -式(13)表示定制旅游路线的旅行时间和花费必须在用户允许的最大旅行时间和花费之内，ti和ei表示景点内游玩时间和门票费用，ti,j和ei,j表示景点si和sj之间的行驶时间和花费，对于两个景点之间的距离，本文利用Haversine公式[11]来计算

(14)

式中:κi和κj表示景点si和sj的纬度， φi和φj表示景点si和sj的纬度。

2 改进SA的旅游路线定制算法

2.1 改进SA算法

模拟退火算法(simulated annealing，SA)[12]是旅游路线规划中最常用的算法之一，但是极易受到降温策略的影响，导致收敛速度下降，影响算法效率[13]。因此，为了提高SA算法的全局搜索能力，加快算法的收敛速度，本文将改进SA算法用于旅游路线定制模型中。本文对SA算法进行以下2个方面的改进：

(1)通过混沌扰动确定搜索范围，防止算法陷入局部最优。混沌具有初值敏感性、遍历性及貌似随机的规律性。在模拟退火算法中嵌入混沌扰动能动态调节搜索步长，更准确找出最优解，从而定制出更准确合理的旅游路线。本文利用一维logistic映射产生混沌扰动对解空间进行搜索的公式如下

Dk+1=μDk(1-Dk) (k=0,1,2,…)

(15)

式中：Dk为当前最优解，μ为混动调节参数，根据一维logistic映射产生的混沌状态特点，当μ=4时，混沌产生的效果最佳。

(2)利用方差判定准则作为终止搜索条件，防止冗余迭代，提高SA算法的运行效率。方差判定公式如式(16)所示

(16)

式中：ε为方差判定因子，n为搜索向量数量，k为迭代次数，D(Li)为方差。

2.2 改进SA算法步骤

基于时间和旅行费用约束下的SA算法推荐旅游路线的具体步骤如下：

输入：旅游景点数据、用户需求以及时间和费用约束。

输出：符合用户需求的最优旅游路线。

步骤1 设置模型参数。设置ε，k，Q0(初始温度)，D0(混沌向量)。

步骤2 根据景点评分机制算出景点得分score(si)，并挑选出n个得分最高的旅游景点。

步骤3 计算景点之间的两两距离di,j， 根据选择的景点初始化一条满足模型约束条件的旅游路线trip1=Initial(si)。

步骤4 计算新的旅游路线tripnew。当用户游玩路线的时间与消费满足最大旅行时间与旅行消费限制时，按混沌扰动方式Dk+1=μDk(1-Dk) 在解空间进行最优解搜索tripnew=NewAnswer(trip1)。

步骤5 接受新的旅游路线tripnew。当score(tripnew)>score(trip1) 时，接受新解tripnew，当score(tripnew)

步骤6 温度更新。按指数下降公式Qk+1=λQk进行温度更新，若满足方差判定准则，循环终止，进行步骤7，否则，转到步骤4。

步骤7 输出最优旅行路线tripbest和游玩时间Tbest与花费Ebest。

3 实验结果与分析

3.1 实验设置

本文实验数据来自于去哪儿网攻略库(桂林)，通过对数据集进行预处理：①删除分享照片数量少于5张的用户；②删除重复多余的照片；③删除用户评论数少于2条的用户。最终得到的数据集包含了338名用户对156个景点分享的9275张图片，景点的经纬度坐标、照片拍摄时间、人均费用、游玩时间、景点类型和带有用户情感的评论信息等。

除了从去哪儿网获取到实验数据外，本文设置改进SA算法中初始温度Q0=200；方差判定因子ε=0.01，降温速率λ=0.95，也对评分方法中涉及到的初始值进行了设定(见表1)，表中与时间有关的单位是min，与花费有关的单位是元。并且将用户的初始位置设为桂林理工大学屏风校区，终止位置设为桂林理工大学雁山校区。

表1 评分方法参数初始化设置

3.2 基于用户需求的景点评分方法评估

3.2.1 景点得分结果展示

表2 景点数据示例

表3 景点得分示例

图1 桂林市景点得分值

3.2.2 景点评分方法合理性分析

为了验证基于用户需求的景点评分方法的合理性，将该方法与文献[14]提出的TRR(three ratios ranking algorithm)算法推荐的景点进行对比。采取在360 min、480 min和600 min这3种不同旅行时间下推荐景点的准确率、召回率和它们的调和值F-Measure来判断推荐效果的优劣，见表4。

准确率的公式如下

(17)

召回率的计算公式为

(18)

F-Measure的计算公式为

(19)

其中，sr表示推荐的旅游景点集合，sv表示游客去过的旅游景点集合。

由表4可知，从推荐效果来看，本文提出的景点评分方法推荐景点的准确率、召回率和F-Measure值都比TRR算法的高，这是因为TRR算法根据景点热度比(类似本文的景点流行度)推荐景点，并没有考虑用户偏好和景点的最佳游玩时间对用户旅行的影响。而从整体情况来看，3种不同旅行时间下的F-Measure值都在0.6以上，这表明本文方法推荐的景点能准确地反映用户对景点的喜好，推荐效果良好。

3.3 旅游路线推荐

3.3.1 旅游路线推荐界面展示

假若某用户使用共享汽车(1.5元/公里)来游玩桂林市区的旅游景点，出发地点为桂林理工大学屏风校区，目的地为南溪山公园，旅行时间约束为480 min，旅行花费约束为500元，且在约束条件内尽可能游玩多的景点，其余旅行参数见表1。根据景点评分方法挖掘出的景点和旅游路线定制模型，分别用传统SA和改进SA算法规划旅游路线。传统SA算法规划旅游路线经过景点为：桂林理工大学屏风校区→七星景区→象山景区→两江四湖→靖江王城→南溪山公园，改进SA算法规划旅游路线经过景点为：桂林理工大学屏风校区→七星景区→靖江王城→两江四湖→象山景区→南溪山公园。传统SA和改进SA算法路线旅行时间和花费见表5，个性化展示界面如图2所示。

表5 旅游路线定制参数

图2 旅游路线个性化定制界面

从图2和表5可知，传统SA算法和改进SA算法定制的旅游路线都在时间和费用预算范围内，但改进SA算法相比传统SA算法定制的旅游路线节约了7 min，节省了9元。这表明改进SA算法定制的旅游路线更加科学准确，能为用户推荐更符合生活实际的旅游路线。

3.3.2 改进SA算法性能分析

为了进一步检验嵌入混沌扰动和方差判定准则的模拟退火算法的优化效果，本文利用3个经典测试函数[15](见表6)对嵌入混沌扰动和方差判定准则的模拟退火算法进行测试(测试结果如图3所示)。

表6 测试函数

图3 测试函数迭代曲线

通过图3的Resenbrock函数优化曲线可知，改进SA算法能够能够更快寻得最优解，说明算法运算效率大大提升，能够更快地定制出满足用户需求的景点；Griewank函数和Resenbrock函数的优化曲线表明改进SA算法跳出局部最优的能力大大增强，使得定制的旅游路线更加符合用户需求。

4 结束语

本文针对旅游路线推荐中个性化程度不高的问题，从景点流行度、用户偏好和景点游玩时间这3个角度出发，提出基于用户需求的景点评分方法，在此基础上考虑用户时间与费用等约束条件建立了旅游路线推荐模型，并将嵌入混沌扰动和方差判定准则的模拟退火算法用于该模型求解符合用户需求的旅游路线。最后，通过实例验证本文提出的景点评分方法比TRR算法有着更高的准确率和召回率，改进SA算法比传统SA算法无论是在最优解的搜寻精度还是在收敛速度上都有明显的提升。

用户游玩过程中，城市交通路况复杂，需要用到各种各样的交通出行方式，并且不同的交通方式对旅行体验有着很大的影响。在接下来的工作中，如何量化用户旅游出行方式，考虑用户出行方式对旅游的影响，并运用到旅游路线推荐模型中，是我们需要去重点研究和解决的问题。