2021年5月计算机工程与设计May2021第42卷第5期COMPUTER ENGINEERING AND DESIGN Vol.42No.5
李旭X李景文12+，俞娜1
（1.桂林理工大学测绘地理信息学院，广西桂林541006；
2.桂林理工大学广西空间信息与测绘重点实验室，广西桂林541006）
摘要：为解决旅游路线推荐中个性化程度不高的问题，提出一种基于用户需求的旅游路线推荐方法。通过获取用户分享的景点照片与游玩时间，综合考虑景点热度、用户偏好和访问时间等用户需求，为用户推荐得分最高的景点，在此基础上建立融合时间与费用约束的旅游路线推荐模型，针对该模型设计内嵌混沌扰动和方差判定准则的模拟退火求解算法。实验结果表明，该方法满足了不同用户的旅行需求，提高了旅游景点推荐的准确性，为实现旅游路线个性化推荐服务提供了一种技术和方法。
关键词：用户需求；景点评分方法；旅游路线推荐模型；模拟退火算法；景点流行度
中图法分类号：TP391文献标识号：A文章编号：1000-7024（2021）05-1339-07
doi：10.16208/j.issn1000-7024.2021.05.020
Tourist route recommendation method based on user needs
LI Xi,LI Jing-wen1,+,YU Na1
(1.Co l egeofGeomaticsandGeoinformation,GuilinUniversityofTechnology,Guilin541006,China；
2.GuangxiKeyLaboratoryofSpatialInformationandGeomatics，GuilinUniversityofTechnology，Guilin541006，China) Abstract：To solve the problem of the low degree of personalization in the recommendation of travel routes,a method of travel route recommendation based on user needs was proposed,The photos of scenic spots and play time shared by users were obtained,user needs such as popularity of attractions,user preferences and access time were comprehensively considered,and the highest-scoring attractions for users were recommended,On this basis,a tourism route recommendation model integrating time and cost constraints was established,and for the model,a simulated annealing algorithm with embedded chaotic disturbance and variance criterion was designed,Experimental results show that the proposed method meets the travel needs of different users,improves the accuracy of tourist attractions recommendation,and provides technologies and methods for realizing personalized recommendation services for tourist routes,
Key words：user needs；sights scoring method；tourist route recommendation model；simulated annealing；sights popularity
0引言
随着智能移动设备和信息技术的飞速发展，使得过去求量型旅游方式转向为求质型旅游方式，在用户游玩过程中越来越注重个性化旅行体验。因此体现用户需求的旅游路线推荐技术成为了研究热点⑴2」。如何根据用户需求智能设计个性化旅游路线，为用户提供精准旅游信息服务，为旅游企业创造岀更大的旅游经济价值已成为智慧旅游建设的重点任务之一［」。Han等［4」根据旅行者的历史旅行轨迹，建立了地标推荐模型，以帮助旅行者制定旅行计划。林青 等［」根据时间地理学理论，计算时空可达性好的景点组合，提岀了一种考虑游客时间成本的旅游线路推荐算法，提升了用户旅游的满意度。刘艳秋等［」根据用户的评论和景点评分信息，提岀了一种基于Word2vec和LDA的推荐模型，并将该模型用于旅游路线推荐中。Salas-Olmedo等7利用Foursquare（观光）、Panoramio（消费）和Twitter（社交 活动）数据，研究了游客的旅行轨迹，验证了不同景点情境特征下游客的旅游活动存在差异。
收稿日期：2020-07-09；修订日期：2021-02-08
基金项目：国家自然科学基金项目（41961063）；国家文化和旅游科技创新工程基金项目（2（1901
1）
作者简介：李旭（1995-），男，湖南常德人，硕士研究生，研究方向为智慧旅游；+通讯作者：李景文（1971-），男，内蒙古赤峰人，博士，教授，博士生导师，研究方向为GIS理论与研究；俞娜（1994），女，宁夏中卫人，硕士研究生，研究方向为图像识别。
E-mail：lixu2021@163
•1340•计算机工程与设计2021年
虽然以上研究都取得了一定的进展，但研究角度单一，缺乏对用户需求及其关联因素的统一分析，不能最大程度体现个性化推荐结果。基于此，本文提岀一种基于用户需求的旅游路线推荐方法，通过景点评分方法实现基于用户需求的景点推荐，在此基础上根据旅行时间、费用等约束条件建立旅游路线推荐模型，并利用嵌入混沌扰动和方差判定准则的模拟退火算法求解该模型，从而为用户推荐科学合理的旅游路线，满足其在不同情境下的旅游需求」。
1理论基础
1.1问题分析
轨迹/由一系列具有时序的GPS点组成f—(p, p,…p-。其中，n表示GPS点数量,p=(lat,lng,tk,lat, /"g为该点的纬度和经度，t为该点的时间戳。定义scr(sk 为景点s的得分，景点及景点间轨迹片段构成有向景区图G=(S,F)其中，S为景点集合，F为连接景点的轨迹集合。
旅游景点将旅游轨迹分割成若干轨迹片段，并通过用户需求、约束条件将其连接起来。记景点s和s的轨迹段为fj,fr(表示不同的轨迹段，上角标score()表示根据景点的得分选择景点s和s的不同轨迹路径。因此，旅游路线strip可表示为
f loe(p-f sore(q-
s1A s i A s j…*S”,s1G S sat,G S ed
()其中，f r(k表示q个不同的景点将景点s i和S2连接起来 所形成的轨迹段，S t”表示旅游开始的景点集合，S ed表示旅游目的地的景点集合。
基于以上分析，旅游路线定制问题可表述为在轨迹集合F中发现得分最高的旅游路线，其中，景点得分是基于景点流行度、用户偏好和景点游玩时间等这些用户个人需求的。因此，为了解决该问题，构建体现用户偏好的景点评分方法与包含约束条件的旅游路线定制模型成为旅游路线定制的关键。
1.2基于用户需求的景点评分方法
基于用户需求的景点评分方法主要包括3个方面的内容：一是基于景点流行度的评分；二是基于用户游玩时间的评分；三是基于景点游玩时间的评分。从这3个方面对景点和用户需求进行分析，既能给用户推荐符合个人喜好且热度较高的景点，又能将景点最合适的游玩时间推荐给用户。
1.2.1基于景点流行度的评分
用户在某个地区旅游时，该地区的热门景点是最先吸引用户关注的(例如，桂林的漓江、象鼻山等)，因此，针对热门景点对用户的影响，本文提岀景点流行度的概念。
基于景点流行度的评分与用户上传关于景点s的照片数量有关，该景点用户上传照片数量的多少能在一定程度上反映该景点的受欢迎程度。但是，通过用户上传照片来判断景点的受欢迎程度也存在着一些问题，比如漓江和象
鼻山这两个景点都有100张用户分享的照片，但是漓江的100张照片是20个用户分享的，而象鼻山的100张照片是5个用户分享的，显然漓江比象鼻山更受用户欢迎。因此，针对这个问题，本文采用对数函数log Q+1)来对某一用户分享的照片数量进行加权，以抑制单个用户上传的某一景点图片数量对景点流行度计算结果的影响。根据以上分析，景点s的流行度s p p的计算公式为
s o=》log(N U+1)⑵
s GU u
式中：N U表示用户u分享的景点i的照片数量，U u表示去过景点s的用户集合。
1.2.2基于用户游玩时间的评分
不同的用户都有自己偏好的景点类型，对于自己喜欢的景点，游玩的时间就会相对长一些，而用户对于自己不感兴趣的景点，游玩的时间就会相对短一些。因此，本文基于用户游玩时间的评分来判断用户对该景点的喜好。
设景点s的平均游玩时间为T i，其公式为
T g=丄丫丫(t d—t y—s—s)(3)
n u G U G”P u
其中，n表示去过景点s?的用户数量，trip u表示用户的旅游路线序列，U表示所有用户的集合t丄表示用户在每个景点游玩的结束时间，s X”表示用户在每个景点游玩的开始时间，工=s-=
j1,s工=Si
(0，其它
由景点平均游玩时间得到游客对于某类型景点的个人偏好，其公式为
v(u,c)=丫S——C)(]
SxGtPu
式中：=ck表示景点s的类型属性。=ck=
(1,Cut s c
〔0，其它。
1.2.3基于景点游玩时间的评分
实际旅行过程中，大部分景点的游玩时间都有限制和规定，并且，每个景点的最佳游玩时间也不同。比如，桂林的独秀峰王城景区的游玩时间为8:00〜18:00，在这个时间段用户能够进入景区游玩，超岀这个时间范围则不能游玩该景区。因此，针对景点游玩时间的问题，本文提岀 了基于景点最佳游玩时间的评分。
定义基于景点最佳游玩时间的评分为Xs),t表示用户游玩景点的某个时间点，X主要包括两个方面的内容：一是该景点允许游玩的时间段；二是在这个时间段内该景点的最佳游玩时间区间是多少。对于景点的允许游玩时间,
第42卷第5期李旭，李景文，俞娜：基于用户需求的旅游路线推荐方法・1341・
我们可以从旅游网站上获取，对于某个景点的最佳旅行时
间，我们做岀如下规定：越靠近景点的开始游玩时间和关
闭游玩时间，则越不适合游玩该景点；当游玩时间为该景
点开放时间与关闭时间的中间区段时，认为这是该景点的
最佳游玩时间段。因此，对X(t给岀如下定义
2t■—2t n
t mnx t nin X(s,)=』2t x—2t 2
(5)
0,t t m j n^或t t>t ax
式中：t x表示景点关闭时间，t mm表示景点开始游玩的时间。
13旅游路线推荐模型
在景点评分方法挖掘岀符合用户需求的景点的基础上，充分考虑旅行时间和旅行费用等约束条件对旅行的影响，建立时间和旅行费用约束下的旅游路线定制模型［10」，使得推荐的旅游路线更加符合生活实际。
根据1.2节中的景点评分方法可以得到景点s的评分为
scoreCs,)=(w X s pp+(1—w)X v(u,Q)X X(s,)
(6)
式中：w取0.4，让用户偏好占更大比重，凸显用户需求。
因此，旅游路线得分为
score(trip)=score(s)(7)根据以上分析，旅游路线定制模型及其约束条件如下
Max丫丫xj score(s)(8)
i=2j=2
空y x=1⑼
k=1j=2
y y述=1(10)
k=1i=1
y X,=y x£1,V k=2,…,n—1(11)
i=1j=2
y t+y y t£T max(12,
,=1,=1j=1
y e+y y e£E max(13)其中，式(7)是旅游路线定制模型的目标函数，定制的旅
游路线为得分最高的旅游路线，X，是决策变量，当景点s 是景点s，的下一个游玩景点，则x,=1，否则为0。式⑼-式(10)保证定制的旅游路线的起点是s】，终点是s n。式(11)确保定制的旅游路线连贯且景点不重复。式(12)-式(13)表示定制旅游路线的旅行时间和花费必须在用户允许的最大旅行时间和花费之内，t和e表示景点内游玩时间和门票费用，t，和e，表示景点s?和s之间的行驶时间和花费，对于两个景点之间的距离，本文利用Haversine公式［1］来计算
d i,=
2r rcsiii(Jsir2(K J')+cosC j cos(K)sin2("'2)
(14)式中：K和k表示景点s，和s的纬度，"和"表示景点s，和s的纬度。
2改进SA的旅游路线定制算法
2.1改进SA算法
模拟退火算法(simulated amiealing,SA)［12J是旅游路线规划中最常用的算法之一，但是极易受到降温策略的影响，导致收敛速度下降，影响算法效率［13」。因此，为了提高SA算法的全局搜索能力，加快算法的收敛速度，本文将改进SA算法用于旅游路线定制模型中。本文对SA算法进行以下2个方面的改进：
()通过混沌扰动确定搜索范围，防止算法陷入局部最优。混沌具有初值敏感性、遍历性及貌似随机的规律性。在模拟退火算法中嵌入混沌扰动能动态调节搜索步长，更准确岀最优解，从而定制岀更准确合理的旅游路线。本文利用一维logistic映射产生混沌扰动对解空间进行搜索的公式如下
D+1=ftD k(1—D k)(=0,1,2,…)(15)式中：D为当前最优解，"为混动调节参数，根据一维logistic映射产生的混沌状态特点，当“=4时，混沌产生的效果最佳。
()利用方差判定准则作为终止搜索条件，防止冗余迭代，提高SA算法的运行效率。方差判定公式如式(16)所示
k
y DL)<e(16)式中：e为方差判定因子，”为搜索向量数量，k为迭代次数，D(L)为方差。
2.2改进SA算法步骤
基于时间和旅行费用约束下的SA算法推荐旅游路线的具体步骤如下：
输入：旅游景点数据、用户需求以及时间和费用约束。
输出：符合用户需求的最优旅游路线。
步骤1设置模型参数。设置e,k,Q…(初始温度)，D)(混沌向量)。
步骤2根据景点评分机制算岀景点得分score(.Si)，并挑选岀”个得分最高的旅游景点。
步骤3计算景点之间的两两距离d j，根据选择的景点初始化一条满足模型约束条件的旅游路线rp1= Initial(s：)。
步骤4计算新的旅游路线tp w。当用户游玩路线的时间与消费满足最大旅行时间与旅行消费限制时，按混沌
・1342・计算机工程与设计2021年
扰动方式D+l=pD k(1—D k｛在解空间进行最优解搜索rip e=NewAnswer(trip、)。
步骤5接受新的旅游路线rpnw。当score(ripe:> score(rip1｛时，接受新解tripe，当score(rip nw)< score tipl)时，按Metropolic准则接受新解tripe。计算新旅游路线tie的旅行时间Tw与花费Enw。
步骤6温度更新。按指数下降公式Q+l=Qk进行温度更新，若满足方差判定准则，循环终止，进行步骤7，否则，转到步骤4。
步骤7输出最优旅行路线trips和游玩时间Tbs与花费Ebst。
3实验结果与分析
3.1实验设置
本文实验数据来自于去哪儿网攻略库(桂林)，通过对 数据集进行预处理：①删除分享照片数量少于5张的用户；
②删除重复多余的照片；③删除用户评论数少于2条的用户。最终得到的数据集包含了338名用户对156个景点分享的9275张图片，景点的经纬度坐标、照片拍摄时间、人均费用、游玩时间、景点类型和带有用户情感的评论信息等。
除了从去哪儿网获取到实验数据外，本文设置改进SA 算法中初始温度Q o=2O0；方差判定因子£=0.01，降温速率入=0.95，也对评分方法中涉及到的初始值进行了设定(见表1)，表中与时间有关的单位是min，与花费有关的单位是元。并且将用户的初始位置设为桂林理工大学屏风校区，终止位置设为桂林理工大学雁山校区。
表1评分方法参数初始化设置
参数参数描述默认值
n数据集中景点总数136
c，数据集中照片总数13275
L景点门票价格范围0-260
L t景点游玩时间范围15-120
L wt景点间行驶时间范围5-60
L we景点间行驶花费范围0-90
X景点最佳游玩时间评分范围0-1刘亦菲的胸
3.2基于用户需求的景点评分方法评估
3.2.1景点得分结果展示
母亲节感恩词为了更好地展示本文提出的景点评分方法，以表2中的s景点为例进行说明。根据1.2节中基于用户需求的景点评分方法，景点s i基于景点流行度的评分为s= log(938+1)=3.0，基于用户游玩时间的评分,)= 58/65=0.9，基于景点游玩时间的评分％(si,,=(X10—2X8)/(7—8)=0.4，因此，由景点评分式()得到景点s i的得分score()=(0.4X3.0+0.6X0.9)X0.4=0.7。表2中景点s2、s3的得分也可由同样的方法求得(见表3)。根据基于用户需求的景点评分方法，求得桂林市景点得分如图1所示。
杨钰莹多大了表2景点数据示例
景点图片
平均时
长/m in
实际时
长/min
开放时间游玩时刻s9*******:00-17:0010:00 s1657901108:00-18:0014:00 S323535406:30-18:308:30
表3景点得分示例
景点s v(u,c)X(s,t)score(Si)
S1 3.00.90.40.7
S2 3.2 1.20.8 1.6
S3 2.4 1.10.30.5
°'°020********* 120140 160
景点
图1桂林市景点得分值
3.2.2景点评分方法合理性分析
为了验证基于用户需求的景点评分方法的合理性，将该方法与文献［14」提出的TRR(three ratios ranking algorithm，算法推荐的景点进行对比。采取在360min、480min和600min这3种不同旅行时间下推荐景点的准确率、召回率和它们的调和值F-Measure来判断推荐效果的优劣，见表4。
准确率的公式如下
precision=：°『(7)
s r
召回率的计算公式为
cl=s*(8)
s©
F-Measure的计算公式为
F-Measure=(⑼
precision+
recall
第42卷第5期李旭，李景文，俞娜：基于用户需求的旅游路线推荐方法・1343・表4推荐效果实验对比
时间/m in方式准确率召回率F-Mesaure
景点评分方法0.760.580.66
360
TRR算法0.650.510.57
景点评分方法0.730.660.69
480
TRR算法0.610.560.58
景点评分方法0.680.700.64
600
TRR算法0.510.580.54
其中，s表示推荐的旅游景点集合，s表示游客去过的旅
游景点集合。
由表4可知，从推荐效果来看，本文提出的景点评分
方法推荐景点的准确率、召回率和F-Measure值都比TRR
算法的高，这是因为TRR算法根据景点热度比（类似本文
的景点流行度）推荐景点，并没有考虑用户偏好和景点的
最佳游玩时间对用户旅行的影响。而从整体情况来看，
3种不同旅行时间下的F-Measure值都在0.6以上，这表明
本文方法推荐的景点能准确地反映用户对景点的喜好，推
荐效果良好。
3.3旅游路线推荐
3.3.1旅游路线推荐界面展示
假若某用户使用共享汽车（1.5元/公里-来游玩桂林
市区的旅游景点，出发地点为桂林理工大学屏风校区，目
的地为南溪山公园，旅行时间约束为480min，旅行花费约
束为500元，且在约束条件内尽可能游玩多的景点，其余
旅行参数见表1。根据景点评分方法挖掘出的景点和旅游路
线定制模型，分别用传统SA和改进SA算法规划旅游路
线。传统SA算法规划旅游路线经过景点为：桂林理工大
学屏风校区一七星景区象山景区a两江四湖a靖江王城
一南溪山公园，改进SA算法规划旅游路线经过景点为：
桂林理工大学屏风校区A七星景区A靖江王城A两江四湖
f象山景区f南溪山公园。传统SA和改进SA算法路线旅
行时间和花费见表5，个性化展示界面如图2所示。
表5旅游路线定制参数
算法参数参数描述数值总和
时间行程54min
479min 景点425min
陈龙妻子传统SA
花费行程61.5元
471.5元景点410元
时间行程47min
472min 景点425min
改进SA
花费行程52.5元
462.5元
景点410元
西山公园
九粛箱小
七是具区
惬院
I曲市水利局
奶茶连锁西山公园
喙山呂区
鹿晗承认喜欢迪丽热巴、桂林医学瞬
⑼传统SA算法定制旅游路线
（b）改进SA算法定制旅游路线
图2旅游路线个性化定制界面
从图2和表5可知，传统SA算法和改进SA算法定制
的旅游路线都在时间和费用预算范围内，但改进SA算法
相比传统SA算法定制的旅游路线节约了7min，节省了9
元。这表明改进SA算法定制的旅游路线更加科学准确,
能为用户推荐更符合生活实际的旅游路线。
3. 3.2改进SA算法性能分析
为了进一步检验嵌入混沌扰动和方差判定准则的模拟
退火算法的优化效果，本文利用3个经典测试函数［5］（见
表6］对嵌入混沌扰动和方差判定准则的模拟退火算法进行
测试（测试结果如图3所示）。
表6测试函数
函数名称测试函数定义域
Resenbrock
E—1
=工［100(x—x+1-2
i—1
+
(—5,5)
X—1—
"12D
Griewank f(x)—)+1(—600,600)
Rastrigin fx，=
D
：工J X一cos(2x z-+10」
i—1
(—5,5)
发布评论