旅游线路推荐与优化的研究进展

孟小丁，刘茄琳，骆鹏睿

(河西学院 物理与机电工程学院，甘肃 张掖 734000)

闲暇时节，旅游是人们讨论的热门话题. 去哪儿旅游需要人们作出决策. 线路安排和所需费用则是旅行前需要准游客做出筹划的内容. 但是，人们的思维一般倾向去没有游历过的城市和景点. 然而，对于一个陌生的城市，游客在规划旅游线路的过程中均面临着很多问题，比如对于旅游地不熟悉以及不了解当地的交通出行等问题. 在有限的时间或旅游预算内，游客希望能够有一条理想型的旅游线路. 针对实际生活中人们所面临的困扰，结合“智慧旅游”的概念[1]，国内外学者主要对旅游线路的探讨集中在旅游线路个性化推荐和旅游线路的优化设计两个方面.

1 旅游线路个性化推荐

1.1 基于兴趣点(POI)的研究

Kurashima(倉島健)[2]将带有地理标记的照片，并按时间序列整理形成用户的旅游足迹，利用这些照片提出来一种旅游推荐方法，将马尔可夫(Markov)和主题模型合并提出概率行为模型，获得旅游者在该主题下对下一个旅游观光点的参观概率，求得一组满足用户兴趣和时间约束的旅游线路，但没有考虑用户的游玩起点和终点. Vansteenwegen(彼得·万斯汀韦根)[3]概述了定向问题及其应用领域，在满足旅程约束条件(如时间预算、 起始点的位置)下，向旅行者推荐最佳的且同时能满足用户兴趣和兴趣点(POI)类型的旅游观光线路. Gionis(阿里斯蒂德斯·吉奥尼斯)[4]综合考虑了用户的兴趣点，时间和距离限制等信息，提出了基于递归的动态规划算法(Rel-DP，Cover-DP)，利用Foursquare数据集进行试验，并将不同的算法进行了对比. Brilhante(布里良特)[5]对旅行商问题进行了改进，最大限度地考虑了用户的个人兴趣和参观时间预算，得到了基于兴趣点(POI)流行度和用户兴趣集合的最佳旅游线路. 吴清霞等[6]提出了个性化旅游线路推荐(PTIR)算法，利用Flickr社交网络的真实数据集进行试验，对准确率和召回率两个指标进行对比分析，结果显示所提出的算法相比传统的算法有较大提升. 宋晓宇等[7]结合群体用户的个人偏好，提出了一种群体受益最大且群体用户局部分散的访问路线，较好的解决了群体路线的公平性问题.

1.2 基于协同过滤(CF)算法的研究

朱敬华等[8]提出建立一个基于用户的协同过滤树和基于项目的协同过滤树，并利用消息传递的思想进行深度学习. 徐雅斌等[9]根据用户的签到行为特点、 考虑用户兴趣点的语义特征，将改进的混合协同过滤算法用于个性化位置推荐，对准确率、 召回率、 平均绝对误差(MAE)进行对比分析，相比传统的算法，推荐性能有较大提升. 刘亮亮[10]主要讨论了基于社会网络模型的协同过滤算法，将改进的协同过滤算法应用于旅游景点线路的推荐.

1.3 运用旅游大数据的分析研究

李霞等[11]建立了应用于个性化旅游线路推荐问题中的数学模型，将蚁群算法(AS)和遗传算法(GA)应用于个性化推荐中，爬取互联网中的旅游数据，文中分别对蚁群算法和最大最小优化蚁群算法(MMAS)、 遗传算法和基于贪心解的混合遗传算法(MGGA)进行了参数(包括平均分值、 最优分值、 平均耗时)的对比分析. 孙文平等[12]通过构建旅游图谱信息，结合大量的旅行游记，生成了旅游线路数据库，提出一种基于人物类型的频繁线路序列模式挖掘算法，设计了一种多维度的个性化旅游线路. 尹书华等[13]将大数据信息进行分词，利用余弦相似度方法度量景点之间的相似度，从而为游客提供推荐服务.

1.4 基于贝叶斯(Bayes)方法的研究

陈燕英等[14]利用用户贡献的社区照片提出贝叶斯学习模型，根据用户特征(如性别、 年龄、 种族等)和用户群体旅游方式(如家庭、 朋友、 恋人)为用户推荐个性化的旅游观光线路，但并未考虑用户兴趣或者兴趣点类别. 徐盼等[15]把朴素贝叶斯(Bayes)方法应用于个性化旅游线路推荐系统中，结果显示，可提供与用户需求相符合的旅游线路. 李广丽等[16]采用分层抽样统计(HSS)和贝叶斯个性化排序(BPR)相结合的方法对旅游景点进行推荐，接着在“智能旅行”数据集上进行实验，与分层抽样统计算法和贝叶斯个性化排序算法相比，作者提出的算法在推荐过程中的效果更好.

2 旅游线路优化设计

2.1 求解的问题类型

Dumas(杜马斯)等[17]提出了一种最小化旅行费用的时间窗的旅行商问题(TSPTW)的旅游线路规划. 该模型要求所有的旅游景点必须对其进行访问，因此对于时间有限制、 景点数量多的旅游线路不太适合. 张煜等[18]研究了时间不确定状态下的时间窗的旅行商问题，对研究旅行线路优化问题中涉及时间因素的研究是有可借鉴作用的. Vansteenwegen(范斯滕韦根)等[20]研究了带时间窗的定向问题(TOPTW)，采用迭代局部搜索算法来对带时间窗的定向问题进行求解，该算法能够在较短的时间内计算出一条较优的线路. Gavalas(加瓦拉斯)等[20]采用聚类和迭代搜索相结合的方法应用于带时间窗的定向问题.

2.2 求解的目标函数

在旅游路线的设计过程中，以求解最短路程、 最短时间、 最低费用、 动态环境要素等信息为主要目标. 曹旭[21]从最短路旅游、 旅行商(TSP)问题、 规划问题的旅游线路三个角度讨论旅游线路的优化问题，建立数学模型，借助Lingo和Matlab编程分别解决了提出的问题. 朱庆等[22]针对传统旅游地图静态路网模型的缺陷，建立了多维动态环境要素的导航网格模型，设计实现了动态寻径的A*算法. 侯乐等[23]建立了带时间窗的的旅行商问题的数学模型，提出迭代局部搜索结合布谷鸟搜索(ILS-CS)的优化算法混合算法，具体做法是首先用迭代局部搜索(ILS)算法求解旅游景点及初始化旅游线路，然后采用布谷鸟搜索(CS)算法优化旅游线路的时间花费. 杨艳等[24]设计了基于游客拥挤感知的旅行线路，建立了多目标规划数学模型，借助粒子群优化(PSO)算法对线路完成评价.

2.3 求解方法的选择

求解方法主要包括计算机仿真的方法和算法设计求解.

计算机仿真方面：任竞斐等[25]构建了Logit模型，将游客在不同线路上进行分配，建立了基于游客偏好、 拥挤度、 时间(等待时间和游览时间)等指标的效用函数，通过在多主体平台上的仿真，可根据游客人数和游客等待时间的信息，采用不同的方案. 张笑白等[26]考虑了景区游客高峰期内的旅游线路优化，提出基于改进Logit的高峰期内人流量变换多线路调度的影响，将问题转换为汉密尔顿(Hamilton)最优回路规划问题.

算法求解方面：包括迪杰斯特拉(Dijkstra)算法[21]9、 A*算法[22]、 粒子群优化(PSO)算法[24]、 教与学优化(TLBO)算法、 基于正态分布随机数的遗传算法(ND-GA)等. 具体体现在：王哲河等[27]以三亚旅游线路为研究对象，构建了数学模型，同时结合了数据库技术，使用狄氏最短路算法，可根据起始景点和优化方案(如费用最低)，计算得到旅游线路信息. 何红等[28]设计了改进的教与学优化算法，并对汉中地区的旅行路线进行优化，实际结果表明该算法设计的旅游线路具有一定的可行性和高效性，特别为自驾游或者散客群体可提供参考. 李旭等[29]以合肥市为例，选取14个景点设计了合肥一日游的优化旅游线路，运用了蚁群算法求解. 吴澎等[30]针对全国201个5A级景区，运用基于正态分布随机数的遗传算法(ND-GA)，对改进旅行商(TSP)模型求解了包括201个5A景区的最优旅游线路. 张子寒等[31]以南京主要景区为例，探讨了多种模型的旅游线路规划问题，给出了以旅行商模型和动态规划为基础的解法，利用遗传算法求解.

3 研究水平

结合研究现状，目前国内外的研究水平集中体现在以下五个方面.

其一，从学科特点来看，表现为定性研究，跨学科特征.

其二，从研究方法看，主要有运筹学方法、 个性化推荐的方法等.

其三，从研究对象看，以游客的需求为主的研究较多，包括游客的喜好、 需求，起始点，预算的花费及时间等信息.

其四，从研究范围看，跨区域大尺度，小区域即特定城市的旅游景点的线路均有涉及.

其五，在数据选择方面，主要通过爬取旅游网站数据，选用Flickr、 Daminaos等数据集获取.

4 发展趋势

旅游线路优化设计相对比较成熟，主要体现在研究理论和研究方法上. 相对而言，智慧旅游背景下旅游线路推荐研究呈蓬勃发展之势. 结合已有的文献资料，旅游线路的个性化推荐及旅游线路优化预计在下述四个方面有进一步的研究和探讨.

一是获取较新的旅游大数据并量化分析，从而较好地掌握访客的出行规律.

二是静态的环境信息会向动态的多维环境信息过渡，以满足智慧旅游个性化、 自适应的需求.

三是结合大数据技术等构建个性化推荐系统将更好地解决线路优化问题，比如基于景点热门程度的线路推荐，结合用户需求的线路推荐与搜索，及基于敏感信息的查询(如位置、 时间、 天气等)的线路推荐等.

四是求解旅游线路的混合智能算法会做更进一步的探讨和开发.