第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·