基于改进变邻域搜索的个性化旅游套餐推荐算法

《Electronic Commerce Research and Applications》：Personalized travel package recommendation algorithm based on improved variable neighborhood search

　　

•采用改进的变邻域搜索算法获取候选旅游套餐。
•通过考虑随机交通时间提出优化模型。
•样本均值逼近法得出可处理的优化模型。
•实验表明，推荐系统在精准度、多样性和时间可靠性之间取得了平衡。

## 引言

旅游业作为全球最蓬勃发展的行业之一，不仅创造了数以百万计的就业机会，还对全球经济发展作出了重大贡献。旅游既是休闲和娱乐的方式，也为人们提供了体验多元文化的机会。根据世界旅游城市联合会（WTCF）发布的《2023年全球旅游经济趋势报告》，2022年全球国内游客总数达到86.7亿人次，同比增长14.2%。随着COVID-19大流行的逐步消退，旅游业经历了强劲复苏，并与文化、娱乐、餐饮等行业深度融合，形成了综合性产业链，同时促进了文化交流，支持了自然与文化遗产的保护。

随着旅游需求的不断增长，选择合适目的地和规划合理行程已成为游客面临的一大挑战。为个体游客推荐合适的景点是一项复杂任务，因为游客的偏好各异且受资源约束，需要针对不同行程时长制定定制化旅行方案。尽管互联网提供了丰富的旅游信息，但也带来了"信息过载"问题（Andjelkovic等人，2019），使游客难以选择合适的景点和行程。特别是，随着城市景点数量持续增加，在线旅游平台日益需要高效方法来识别符合游客兴趣的景点。个性化推荐服务有助于识别用户偏好，并在时间和预算约束下提供定制化旅行行程，从而提升用户体验，同时有望提高平台收入和用户留存率。

个性化旅行推荐研究大致可分为三类：（1）基于景点的推荐，即系统分析用户的历史访问记录以评估其偏好，随后对景点进行排序以满足其需求（Liang和Chen，2020）；（2）基于路线的推荐，平台采用路径规划算法将景点组织成连贯的旅行路线，适用于单日和多日行程（Bin等人，2019）（Guillermo等人，2022）；以及（3）旅游套餐推荐，可进一步细分为两类：一类聚焦于综合套餐，包括景点、餐饮和住宿（Nurbadi等人，2019）；另一类侧重于旅行套餐，其中套餐被定义为具有精心规划参观顺序的一组高质量景点（Kolahkaj等人，2020，Yu等人，2015）。

与基于景点的推荐相比，旅行套餐推荐更强调景点之间的关联。这些套餐不仅符合游客的个性化偏好，还预先规划了参观顺序和时长，非常适合单日游览。虽然旅行套餐推荐与基于路线的推荐有相似之处，但也存在显著差异。基于路线的推荐侧重于优化景点之间的路径以满足时间或预算约束，通常从热门景点出发规划路线。然而，这种方法往往只能生成有限数量的路线，难以满足用户的个性化需求，可能导致推荐缺乏多样性和新颖性。相比之下，旅行套餐推荐优先优化景点的组合，着重使景点与用户偏好相匹配，并确保套餐内的多样性以增强整体旅行体验。因此，本研究聚焦于旅行套餐推荐，旨在提供多个符合用户偏好的套餐，从而提供更灵活、更多样化的个性化旅行推荐。

在旅行套餐推荐中，核心问题在于选择和优化景点组合。这一过程通常考虑两个关键因素：首先，景点是否与用户的个性化偏好相匹配，因为高度匹配可以提升旅行满意度和推荐准确性。其次，推荐景点的多样性对游客体验有显著影响（Lee等人，2022a）。不同景点对应不同的旅行主题，如自然景观或历史文化，各提供独特体验。一些研究表明，过度关注准确性可能导致内容同质化，降低推荐新颖性并限制潜在偏好的发现（Kim等人，2021）。因此，平衡准确性和多样性是推荐系统面临的重要挑战（Jiao等人，2020）。本研究提出了一种推荐多个旅行套餐的方法，既考虑单个套餐内的主题多样性，也考虑不同套餐之间的多样性。该方法旨在提供更丰富、更多样的旅行选择，从而更好地满足个性化需求并增强整体旅行体验。

此外，旅行套餐推荐的一个重要方面是规划套餐内景点的参观顺序，确保包括参观时间和交通时间在内的总时长在预期范围内。交通时间是影响总行程时长的关键因素，然而现有系统往往忽视了交通不确定性带来的影响。天气和路况等因素会显著影响交通时间，增加行程超时风险，尤其是在拥堵时段和旅游旺季。超时可能降低游客满意度，严重时还会打乱后续旅行计划，如错过航班或延误归程。因此，如何提高行程推荐中路线的可靠性是旅游平台面临的关键问题。因此，在推荐旅行套餐时显式考虑交通时间的不确定性，对于提升行程可靠性具有重要的理论意义和实践价值。

基于上述分析，本文开发了一个名为TPRIVNS的两阶段个性化旅行套餐推荐框架。第一阶段采用一种改进的变邻域搜索算法（QT_VNS），将景点质量和主题多样性纳入套餐生成过程。具体而言，该算法引入两个惩罚因子（分别针对景点质量评分和主题相似度），并定义五个邻域算子以迭代调整和精化套餐，旨在平衡套餐质量与套餐内多样性。第二阶段，我们建立了一个随机优化模型，不仅捕捉用户偏好和套餐间多样性，还通过机会约束显式考虑交通时间的随机性。该模型随后使用样本均值逼近（SAA）方法进行求解，从而实现有效的套餐选择和个性化推荐。本文的主要贡献有三：第一，我们提出了一种新型两阶段个性化旅行套餐推荐框架，名为TPRIVNS，在统一架构下共同解决候选套餐构建和可靠套餐推荐的挑战。第二，我们开发了一种改进的变邻域搜索算法（QT_VNS），包含五个邻域算子和优化搜索策略。通过引入景点质量和主题相似度的惩罚因子，该算法高效生成在行程质量和套餐内多样性之间取得良好平衡的旅行套餐。第三，我们建立了考虑游客偏好、套餐间多样性和交通时间固有随机性的随机优化模型。该模型实现了旅行套餐的有效筛选和推荐，确保最终推荐集合既具有高度多样性又具备强可靠性。

本文其余部分组织如下：第2节综述相关领域的研究现状。第3节介绍两阶段个性化旅行套餐推荐框架TPRIVNS的实现细节，包括QT_VNS算法以及随机优化模型的构建与求解。第4节在真实数据集上进行实验，验证所提出的TPRIVNS框架的性能。最后，第5节给出结论和未来工作展望。

## 节选片段

### 个性化旅行推荐

通常，现有的个性化旅行推荐研究可归纳为三大类型：景点推荐、旅行路线推荐和旅行套餐推荐。景点推荐是在线旅游平台最常用的方法，通常提供单个或多个景点的旅行建议。基于内容的推荐方法（McAuley和Leskovec，2013）（Yeh和Cheng，2015）从景点相关的信息中提取属性……

### 建模

在本节中，我们提出了一种基于改进变邻域搜索的旅行套餐推荐框架（TPRIVNS）。在第一阶段，我们提出了一种算法，通过将景点质量评分和主题多样性纳入其中来构建和优化候选旅行套餐池。定义了五个邻域算子（1-1交换、1-添加、1-删除-添加、2-删除-添加-移动和抖动）来调整和改进套餐，优化质量、多样性和行程时长。在……

### 实验与结果

本章的结构安排如下。首先，我们详细介绍了数据收集和预处理过程，包括景点和游客主题向量分布的推导，以及用于评估实验结果的绩效指标和比较基准方法的介绍。其次，我们评估了基于质量评分和主题多样性的改进变邻域搜索算法（QT_VNS）的实际性能……

### 结论

随着旅游业的快速发展和旅游市场的日益繁荣，个性化旅行推荐系统已成为满足游客多样化需求的重要工具。本文提出了一个名为TPRIVNS的两阶段个性化旅行套餐推荐框架。首先，我们提出了一种基于质量评分和主题的变邻域搜索（QT_VNS）算法来生成旅行套餐，该算法将评分和主题多样性整合为……

### CRediT作者贡献声明

Chao Huang：撰写——审阅与编辑、监督、方法论、经费获取、概念构思。
Xian Li：撰写——审阅与编辑、验证、调查研究。
Yifan Zhang：撰写——原稿、验证、软件、方法论、数据整理。
Yuzi Zhou：撰写——审阅与编辑、软件、方法论。

### 利益冲突声明

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：Chao Huang报告获得了江苏省哲学社会科学高校重大项目提供的资金支持。Chao Huang报告获得了国家自然科学基金提供的资金支持。如果有其他作者，他们声明没有已知的竞争性财务利益或个人……

### 致谢

本研究得到了国家自然科学基金[编号71671038和72091213]、江苏省哲学社会科学高校重大项目（项目编号2021SJZDA126）的支持。

Chao Huang | Xian Li | Yifan Zhang | Yuzi Zhou