第1期 常亮，等：旅游路线规划研究综述 ·85· 性地访问整个节点集合，而是在访问节点时收集 多不同。首先，由于旅游活动是一个动态的过 利润，且利润的收集分布在具有有限容量的几辆 程，有很多不确定的因素，无法进行准确建模，而 车上。团队定向问题是该问题的一个变型，多用 恰是这些不确定因素可能对路线预测的准确性起 于旅游路线规划问题的多路线求解，其目标是找 着决定性的作用2。此外，在对旅游路线规划问 到在最大长度限制条件下的k条路径（其中每个 题的建模求解时，基于兴趣点的考虑，只是将兴 节点最多访问一次)，并且具有最大的总收益。 趣点作为一个点，并没有考虑到兴趣点的实际大 带时间窗口的团队定向问题中加入了对POI 小，因此这种方法只适用于博物馆、公园、小广场 在特定的时间窗口进行访问的限制，从而可以适 等有固定出口且范围较小的景点，对于相对较大 应更多场景。Lin等提出了一个基于模拟退火 的景点，这种方法就会与实际情况有较大出入， 算法的启发式算法，在每次迭代中，通过对当前 如在游览一条观光河道时，兴趣点的起点和终点 解以相等的概率应用移动交换，插入或倒置其中 可能相差很远，这时再从起点进行路线规划就变 的一个节点来获得相邻解，如果它比当前最佳找 得不切实际。 到的解决方案更具有收益，则新的解决方案被采 3.2基于用户生成内容的求解 用并成为当前的解决方案，这个概率会随着损失 近些年，由于信息的传播和共享越来越便捷， 的增加而减少，应用上述方法进行一定数量的迭 互联网上积累了大量的集体智慧相关数据，影响 代之后，就会进一步优化用局部搜索方法找到目 着人类生活的许多领域，尤其是旅游业和旅游行 前最佳解。 为。研究表明，超过87%的客户依靠集体智慧为 带时间依赖和时间窗口的团队定向问题是 旅行做出决定，例如旅行者在预订住宿之前通常 指：给出一组节点和每对节点之间的旅行时间， 会查看相关的评分和评论。虽然许多旅游网站 其中每个节点与利润、访问时间和时间窗口相关 提供关于目的地和旅行路线的信息，但是整合和 联，目的是找到从起始节点到目的节点间的固定 比较来自海量用户的不同类型信息需要大量时间 数量且不相交的路径，每条路径不超过给定的时 和精力。 间限制，在不违反其时间窗口的情况下通过访问 在旅游领域中，用户在进行一次旅行后，通常 所有路径中的节点来最大化收集总利润。Gar- 会分享自己的经验和评论，形成了包括用户评 cia等2提出了2种不同的方法来解决上述问题： 论、照片、签到数据、旅游游记和GPS轨迹等信 1)利用预先计算，得到所有POI对之间的平均旅 息的大量用户生成内容，这些数据为便利行程计 行时间，约减掉时间依赖限制；2)在旅行时间上 划提供了极大的机会m。虽然一个单独的评论或 加入时间依赖，但是该方法是基于周期性服务时 者旅游游记中可能存在噪声或者偏见，但是将来 间的简化假设，不符合现实中城市的交通网络。 自大量用户的贡献的内容作为一个整体可以有效 此外还有一些用于模拟旅游路线规划问题 地抓住一个景点的本质。因此，越来越多的研究 的TOP变型，考虑到问题的更多属性或对不同属 利用空间分析和数据挖掘等技术对这些内容进行 性的多个约束，Luo等2引入了一种用于T0P变 分析，得到用户的相关偏好和历史轨迹信息，发 型的启发式算法，该方法在旅行中插入节点时应 现游客间的相似性，实现旅游路线的推荐2。 用2种不同的优先级规则，算法在解决方案的质 3.2.1利用用户GPS轨迹进行求解 量和执行时间方面优于其他启发式算法，能够在 随着配备GPS功能的设备数量不断增加，越 较短时间内得到由精确算法求解实例中的最优 来越多的轨迹被连续地产生和分享，也正在改变 解；Li等2制定了带容量约束和时间窗口的团队 着人们与网络的交互方式。基于这些轨迹信息， 定向问题，增加了服务节点在有限时间可用性的 一些应用问题变得可行，例如旅游路线规划问 约束，并使用整数线性规划求解方法获得了精确 题，GPS轨迹中包含丰富的信息，可以挖掘用户 的解，然而这种方法不适合进行实时应用。 在一个位置花费的时间和对不同位置的访问顺序 综上所述，利用OP的多种变型对旅游路线 等，这些信息可以被用来挖掘指定区域中的热门 规划问题进行建模求解的方法，可以准确建模旅 景点和一般的旅行路线，从而进一步改进路线推荐。 游路线规划问题中多方面的因素，如用户约束」 Cui等Bo使用用户历史GPS信息挖掘用户的 景点开放时间和出行交通方式等，能得到一个或 旅行习惯，提出了2种个性化的旅游路线推荐算 多个满足用户约束的精确路线规划结果，但是这 法，能够在推荐时考虑用户的个人偏好，提高推 种方法与现实生活中的旅游路线规划问题还有很 荐结果的个性化程度。)首先使用协同过滤技术性地访问整个节点集合，而是在访问节点时收集 利润，且利润的收集分布在具有有限容量的几辆 车上。团队定向问题是该问题的一个变型，多用 于旅游路线规划问题的多路线求解，其目标是找 到在最大长度限制条件下的 k 条路径 (其中每个 节点最多访问一次)，并且具有最大的总收益。 带时间窗口的团队定向问题中加入了对 POI 在特定的时间窗口进行访问的限制，从而可以适 应更多场景。Lin 等 [20]提出了一个基于模拟退火 算法的启发式算法，在每次迭代中，通过对当前 解以相等的概率应用移动交换，插入或倒置其中 的一个节点来获得相邻解，如果它比当前最佳找 到的解决方案更具有收益，则新的解决方案被采 用并成为当前的解决方案，这个概率会随着损失 的增加而减少，应用上述方法进行一定数量的迭 代之后，就会进一步优化用局部搜索方法找到目 前最佳解。 带时间依赖和时间窗口的团队定向问题是 指：给出一组节点和每对节点之间的旅行时间， 其中每个节点与利润、访问时间和时间窗口相关 联，目的是找到从起始节点到目的节点间的固定 数量且不相交的路径，每条路径不超过给定的时 间限制，在不违反其时间窗口的情况下通过访问 所有路径中的节点来最大化收集总利润。Gar￾cia 等 [21]提出了 2 种不同的方法来解决上述问题： 1) 利用预先计算，得到所有 POI 对之间的平均旅 行时间，约减掉时间依赖限制；2) 在旅行时间上 加入时间依赖，但是该方法是基于周期性服务时 间的简化假设，不符合现实中城市的交通网络。 此外还有一些用于模拟旅游路线规划问题 的 TOP 变型，考虑到问题的更多属性或对不同属 性的多个约束，Luo 等 [22]引入了一种用于 TOP 变 型的启发式算法，该方法在旅行中插入节点时应 用 2 种不同的优先级规则，算法在解决方案的质 量和执行时间方面优于其他启发式算法，能够在 较短时间内得到由精确算法求解实例中的最优 解；Li 等 [23]制定了带容量约束和时间窗口的团队 定向问题，增加了服务节点在有限时间可用性的 约束，并使用整数线性规划求解方法获得了精确 的解，然而这种方法不适合进行实时应用。 综上所述，利用 OP 的多种变型对旅游路线 规划问题进行建模求解的方法，可以准确建模旅 游路线规划问题中多方面的因素，如用户约束、 景点开放时间和出行交通方式等，能得到一个或 多个满足用户约束的精确路线规划结果，但是这 种方法与现实生活中的旅游路线规划问题还有很 多不同。首先，由于旅游活动是一个动态的过 程，有很多不确定的因素，无法进行准确建模，而 恰是这些不确定因素可能对路线预测的准确性起 着决定性的作用[24]。此外，在对旅游路线规划问 题的建模求解时，基于兴趣点的考虑，只是将兴 趣点作为一个点，并没有考虑到兴趣点的实际大 小，因此这种方法只适用于博物馆、公园、小广场 等有固定出口且范围较小的景点，对于相对较大 的景点，这种方法就会与实际情况有较大出入， 如在游览一条观光河道时，兴趣点的起点和终点 可能相差很远，这时再从起点进行路线规划就变 得不切实际。 3.2 基于用户生成内容的求解 近些年，由于信息的传播和共享越来越便捷， 互联网上积累了大量的集体智慧相关数据，影响 着人类生活的许多领域，尤其是旅游业和旅游行 为。研究表明，超过 87% 的客户依靠集体智慧为 旅行做出决定，例如旅行者在预订住宿之前通常 会查看相关的评分和评论[25]。虽然许多旅游网站 提供关于目的地和旅行路线的信息，但是整合和 比较来自海量用户的不同类型信息需要大量时间 和精力[26]。 在旅游领域中，用户在进行一次旅行后，通常 会分享自己的经验和评论，形成了包括用户评 论、照片、签到数据、旅游游记和 GPS 轨迹等信 息的大量用户生成内容，这些数据为便利行程计 划提供了极大的机会[27]。虽然一个单独的评论或 者旅游游记中可能存在噪声或者偏见，但是将来 自大量用户的贡献的内容作为一个整体可以有效 地抓住一个景点的本质。因此，越来越多的研究 利用空间分析和数据挖掘等技术对这些内容进行 分析[28] ，得到用户的相关偏好和历史轨迹信息，发 现游客间的相似性，实现旅游路线的推荐[29]。 3.2.1 利用用户 GPS 轨迹进行求解 随着配备 GPS 功能的设备数量不断增加，越 来越多的轨迹被连续地产生和分享，也正在改变 着人们与网络的交互方式。基于这些轨迹信息， 一些应用问题变得可行，例如旅游路线规划问 题，GPS 轨迹中包含丰富的信息，可以挖掘用户 在一个位置花费的时间和对不同位置的访问顺序 等，这些信息可以被用来挖掘指定区域中的热门 景点和一般的旅行路线，从而进一步改进路线推荐。 Cui 等 [30]使用用户历史 GPS 信息挖掘用户的 旅行习惯，提出了 2 种个性化的旅游路线推荐算 法，能够在推荐时考虑用户的个人偏好，提高推 荐结果的个性化程度。1) 首先使用协同过滤技术 第 1 期 常亮，等：旅游路线规划研究综述 ·85·