0 引言

近些年, 随着移动通信技术的高速发展和智能设备的普及, 基于位置的服务已经广泛应用于人们的日常生活中.研究人员利用人们随身携带的智能设备, 如智能手机、智能手表和一些具有定位功能的设备等, 获取这些设备生成的位置信息, 提供给携带者所需要的各种基于所在位置的服务^[1-2].在众多服务之中, 旅行规划问题是一个研究热点问题.在决定去往旅游地之前, 人们总是需要作一份旅行规划.由于兴趣点的数量众多、游客的时间有限、对不同的兴趣点类型喜好不同, 游客因此需要从大量的兴趣点集合中选择出自己感兴趣的兴趣点.为此他们需要比较兴趣点的类型、位置信息以及该兴趣点的受欢迎度等, 除此之外, 还要考虑兴趣点的游玩顺序.

在旅行规划中, 游客首先需要考虑的一个问题就是如何选择自己偏爱的兴趣点.目前, 已经有很多工作研究了如何针对不同的游客推荐给他们可能感兴趣的兴趣点.其中, 一些研究使用一片区域内人群和出租车生成的GPS轨迹信息, 发掘出该区域内有意思的地点和交通信息^[3-4].在其他的研究中, 研究人员使用具有定位功能的照片来帮助游客进行兴趣点的选择^[5-6].除此之外, 使用来自基于位置的社交服务所产生的数据也可以给游客推荐合适的信息^[7].因此, 通过以上这些方面的工作, 游客可以获取他们可能感兴趣的地点.在推荐了合适的兴趣点之后, 旅行规划的第二个问题就是找到一条合适的路线遍历这些兴趣点.在这一方面, 同样有不同的工作对此展开研究.在之前的一些研究中, 研究人员在路线兴趣点的添加中主要考虑距离以及交通的影响, 目的是找到一条距离最短路线^[8-10], 或者是在时间限制下游玩更多的景点^[11-12].但是在这一情形下, 旅行规划则忽略了兴趣点本身的质量, 因此很难找到质量高的兴趣点.在其他的一些研究中, 研究人员不仅考虑了兴趣点之间的距离, 也在路线兴趣点的添加中考虑了这些景点的质量, 如评分、受欢迎度等^[13-14].然而, 目前几乎没用相关研究考虑到游客可能在旅游地不止停留一天.在多日旅行规划中, 规划路线的情形将与之前的研究工作有所不同, 我们用图 1示例说明.

如图, 我们假定游客的2 d游行程规划为从$S$点出发, 2 d的兴趣点类型的游玩次序为$\{S, X, Y, S\}$, 令$x_1$, $x_2$, $y_1$, $y_2$的兴趣点评分依次为10, 9, 8, 8.图中的有向线代表两点之间的交通距离.首先, 不同于之前的旅行规划, 多日旅行规划的出发地和目的地应当是同一点, 即为图中$S$.其次, 之前的旅行规划总是逐天规划路线, 我们首先选择规划第一天的线路, 从$x_1$, $x_2$中选择$x_1$, 因为$x_1$和$x_2$的交通距离$S$相同, $x_1$的评分高于$x_2$.接着在$y_1$, $y_2$中选择$y_1$, 因为$y_1$, $y_2$的评分相同而$y_1$的交通距离$x_1$更短.到此, 我们得出第一天的规划线路为$\{S, x_1, y_1, S\}$.接着排除第一天游玩过的兴趣点, 第二天的线路为$\{S, x_2, y_2, S\}$.这样得到的是根据之前的旅行规划方法规划出的2 d游路线.然而我们交换$x_1$和$x_2$的次序, 使得第一天的线路为$\{S, x_2, y_1, S\}$, 第二天的线路为$\{S, x_1, y_2, S\}$, 在此情况下2 d的兴趣点总评分与之前的方式相同, 而第二种路线的交通总耗时低于第一种方式, 因此第二种规划方案优于第一种规划方案.除此之外, 由于之前的研究是按天的顺序规划路线, 所以集中于高评分的兴趣点在第一天更容易被获取, 之后由于兴趣点的选取排除了之前的高评分兴趣点, 导致了之后的规划路线兴趣点质量逐天降低, 然而游客可能更倾向于均衡兴趣点质量的旅行规划.基于以上, 我们认为当前的旅行规划不适用于多日旅行规划.

本文研究了多日的旅行规划问题.游客在规划的开始阶段选择自己的旅行天数、感兴趣的类别, 决定这些兴趣点类别的游玩顺序.多日旅行规划根据游客选择的类别为游客推荐合适的候选兴趣点.为了保证规划路线距离以及线路中兴趣点的质量要求, 我们从这些候选兴趣点中找到最合适的多日旅行路线.本文的主要贡献可以归为以下3点.

(1) 考虑了多日旅行规划问题.当游客在所在城市游玩多日时, 之前的旅行规划方式不适合多日情形下的旅行规划.

(2) 在多日旅行规划中需要考虑多日旅行满意度的稳定性问题.游客在多日的游玩中需要得到均衡的高质量旅行规划路线.

(3) 提出了全新的启发式方法用于规划路线.通过实验证明, 我们的方法可以得到均衡的高质量多日旅行路线.

本文的其他部分结构是:第1节介绍旅行规划的相关工作; 第2节具体描述多日旅行规划问题; 第3节提出3种启发式算法用于得出多日旅行规划路线; 第4节为实验的结果以及分析; 第5节是结论以及未来工作.

1 相关工作

旅行规划问题在近些年已经得到了广泛的研究, 在商业领域也得到充分的发展.在设计旅行规划路线时, 研究人员首先需要为游客推荐他们可能喜爱的兴趣点, 这一部分需要来自游客自身的个性化信息, 以此来分析游客的个人偏好; 然后整合所推荐的兴趣点, 这一部分不仅需要考虑兴趣点的信息还要分析所在地的交通信息, 才能规划出符合条件的旅行路线.

旅行规划的第一步是兴趣点的选择.基于位置的服务的普及为研究人员提供了大量可利用的数据信息.在文献[3]中, Zheng等人利用来自不同移动设备的GPS轨迹信息, 挖掘出在一片区域内有趣的地点并提供给游客.同时, 人们也可以通过出租车的GPS信息来获得旅行推荐^[4].近些年, 更多的研究集中在搜索大量具有地理位置的标签照片来生成有效数据.通过地理标签照片, 研究人员可以挖掘出有兴趣的地点, 并推荐给游客.例如, 在文献[5-6, 15]中, 研究人员收集大量来自社交软件的地理标记照片, 如Foursquare、Gowalla、Flickr等, 在这些社交软件中, 人们通过分享具有地理标记的照片来进行社交联系.从这些照片可以得到充分的关于兴趣点相关信息(位置、人流量、受欢迎度以及合适的停留时间等)的数据, 为游客推荐他们可能喜欢的兴趣点.除此之外, 还有一些研究的推荐兴趣点方法里同时考虑到了人群之间社交关系对兴趣点选择的影响, 如文献[7]中, 研究人员认为游客在选择兴趣点时会更有可能选择自己的好友所分享的兴趣点, 以及在社交软件中关注的人所去过的地方.

在选择了兴趣点之后, 需要考虑如何把这些兴趣点规划成有效的旅行路线, 通过路径搜索算法, 找到最佳的旅行路线.目前已经有研究人员提出了不同的路径搜索算法.在最早的研究中, 研究人员将旅行路线的搜索规划为旅行商问题, 并使用相关的线路搜索算法.之后在研究中, Li等人^[8]研究了一种新的旅行线路类型TPQ (Trip Planning Query), 将所有的兴趣点归到特定的类别, 使用一系列不同近似比的近似算法, 从出发地到目的地, 找到一条至少每个类别兴趣点访问一次的最佳路线.除此之外, 其他研究人员也考虑了兴趣点的访问次序问题.在Sharifzadeh等人提出的OSR (Optimal Sequenced Route)中^[9], 使用轻量级基于阈值的迭代算法用于搜索最佳路线, 不同于文献[8], 他们认为游客在规划路线时可能会以某种次序访问其中的一些兴趣点.在其他的一些研究中^[16-18], 研究人员通过限定部分兴趣点类别的顺序, 并使用不同的启发式算法来进行路线搜索.

除了搜索最短路径, 研究人员在路线规划中还考虑了兴趣点的受欢迎度以及旅行时限问题.通过将受欢迎度转换为评分, 在路径搜索中找到距离和评分都符合条件的兴趣点. Chen等人^[19]根据兴趣点的人流量以及游客对兴趣点类别的主观偏好, 给所有的兴趣点进行评分, 在之后的路线搜索中, 通过启发式算法将其中最符合评分距离比的兴趣点添加到旅行路线中. Dai等人^[13]提出了另外一种旅行规划模型, 在所有兴趣点的平均分大于给定值的情况下, 旅行线路的用时最短, 在搜索兴趣点上, 他们使用3种近似算法并得到了有效的旅行路线.除此之外, 还有一些其他的线路规划则考虑了时间限制. Lu等人^[14]在算法上使用了3种优化机制来提高旅行路线的搜索效率. Bao等人^[20]提出了在特定时间限制下的基于贪心策略的旅行规划算法, 他们研究了在时间条件限制下如何从现有的旅行线路中选择合适的子集路线.不同于以上这些工作, 本文研究的是多日旅行规划问题, 所以以上这些研究并不适用于多日旅行规划的解决, 需要制订多天的旅行线路并且要使多天的旅行线路服务质量保持稳定.

2 问题定义

在本节中, 首先介绍和定义本文研究所需要的一些相关变量, 然后提出研究目标. 表 1总结了本文所用的参数.

定义1  兴趣点集$A=\{a_1, a_2, a_3, \cdots, a_n, \cdots, a_{|A|}\}$代表所有兴趣点的集合, 对于每一个兴趣点$a_i$, 都有它的兴趣点时间信息$t(a_{i})$和它的兴趣点评分信息$s(a_{i})$, 其中时间信息代表游客在该兴趣点所停留的时间, 评分信息则代表该兴趣点的受欢迎度.

定义2  路线集$R=\{r_{1, 2}, r_{1, 3}, r_{1, 4}, \cdots, r_{2, 1}, r_{2, 3}, r_{2, 4}, \cdots, r_{|A|, |A-1|}\}$代表所有路线的集合, 集合$R$中的任意一条路线$r_{i, j}\in R$, $r_{i, j}=(a_i, a_j)$, 其中$i\neq j$, $a_i$和$a_j$表示兴趣点集中任意的两个兴趣点.在本文中, 路线集合中的任意一条线路$r_{i, j}$代表两个兴趣点间的最快路线.同时用时间符号$t(r_{i, j})$表示两个兴趣点最快路线所需要的交通时间.

定义3  单日旅行$ tp=\{a_{k_1}, a_{k_2}, a_{k_3}, \cdots, a_{k_n}\}$代表旅行线路中的兴趣点集合, 集合$tp$中任意的$a_{k_i}$都是集合$A$中的元素.除此之外, 集合$tp$中元素各不相同, 也就是每个兴趣点只去一次.因此可推导出集合$tp$为集合$A$的子集.用$tp_i$表示第$i$天的旅行.

定义4  多日旅行$ TP=\{tp_{1}, tp_{2}, tp_{3}, \cdots, tp_{D}\}$代表多日旅行集合, 其中天数$D$是游客在旅行前所计划的在该城市所游玩的天数, 游客可以指定他们预定的游玩天数, 根据不同的天数安排, 每天旅行线路的选择也会有所不同.

定义5  旅行线路消耗时间指的是1 d的兴趣点游玩所需要的时间, 该时间由所有兴趣点的停留时间之和加上兴趣点之间转移所耗费的交通时间之和组成.用单日旅行时间$t(tp)$表示1 d游玩了该天旅行线路中全部兴趣点所需要的时间.当一条单日旅行线路为$tp=\{a_{k_1}, a_{k_2}, a_{k_3}, \cdots, a_{k_n}\}$时, 有

$ \begin{align*} t(tp)=t(s, a_{k_1})+\sum\limits^{n}_{i=1}t(a_{k_1})+\sum\limits^{n-1}_{i=1}t(r_{k_i, k_{i+1}})+t(a_{k_n}, s), \end{align*} $

其中, $s$用来表示旅行的出发地和目的地, 在多日旅行中, 游客的出发地和目的地为同一点.用$t(tp_i)$表示第$i$天旅行线路总耗时, 旅行天数为$D$, 则总天数旅行兴趣点总时间为

$ \begin{align*} T(tp)=\sum\limits^{D}_{i=1}t(tp_i). \end{align*} $

定义6  旅行线路评分是由该天所有兴趣点的评分之和组成.当一条单日旅行线路为$tp=\{a_{k_1}, a_{k_2}, a_{k_3}, \cdots, a_{k_n}\}$时, 有单日旅行兴趣点评分为

$ \begin{align*} s(tp)=\sum\limits^{n}_{i=1}s(a_{k_i}). \end{align*} $

用$s(tp_i)$表示第$i$天旅行线路兴趣点评分, 旅行天数为$D$, 则总天数旅行兴趣点总评分为

$ \begin{align*} S(tp)=\sum\limits^{D}_{i=1}s(tp_i). \end{align*} $

研究目标:为游客制订多日旅行线路.一个有效的多日旅行规划需要游客预先指定以下信息.

(1) 指定的出发地和目的地.在多日旅行规划中, 出发地和目的地相同.

(2) 游客指定的兴趣点类型游玩顺序$q=\{c_1, c_2, \cdots, c_m\}$.

(3) 游客指定的游玩天数$D$.

为了能够确定多日旅行规划的优劣, 使用旅行效益来衡量多日旅行规划的好坏, 并用符号$U$表示.通过两个指标来计算旅行效益值$U$:第一项为总天数旅行兴趣点总评分$S(tp)$; 第二项为$D$天旅行兴趣点评分标准差$\sigma$.我们认为, 高质量的多日旅行规划不仅具有高评分的兴趣点集, 而且游客每天的旅行满意度趋于稳定.为此有旅行效益值

$ \begin{align} U=S(tp)-\lambda\times \sigma. \end{align} $

(1)

式(1)中$\lambda\geqslant0$, 即多日旅行兴趣点的总评分越高, 旅行效益值越大; 单日旅行兴趣点评分离散程度越低, 旅行效益越高. $\lambda$用来表示旅行满意度的离散程度影响旅行效益的程度. $\lambda$越大, 表示游客越重视旅行满意度的稳定性; $\lambda$越小, 表示旅行满意度的稳定性影响旅行效益的程度越低.特别地, 当$\lambda=0$时, 旅行效益则只与多日旅行兴趣点总评分有关.

3 算法设计

将兴趣点分成不同的类型, 在游客指定完出发点和兴趣点类别的游玩顺序后, 通过游客决定的类别游玩顺序来为游客选择最佳的线路规划.首先计算使用穷举法的问题复杂度.假定在第$i$天中, 游客的指定游玩类型顺序为$q=\{c_1, c_2, \cdots, c_m\}$, 则可能的排列组合方式为$\prod^{m}_{i=1}c_i$, 其中相邻类别之间需要查询兴趣点之间的交通距离, 则查询第$i$天的可能线路一共需要的计算量为$(m+1)\times \prod^{m}_{i=1}c_i$, 当旅行天数为$D$时, 计算量为$D\times(m+1)\times \prod^{m}_{i=1}c_i$.因此, 使用穷举法解决该问题的复杂度为

$ \begin{align*} O=D\times(m+1)\times \prod\limits^{m}_{i=1}c_i. \end{align*} $

由此可知当兴趣点的数量变化时, 需要的计算时间和空间将会呈指数式增长, 所以利用穷举法来解决此问题并不现实.因此我们决定使用其他的方法来解决本问题.在本节中, 我们提出了3种启发式算法用于得到最佳旅行路径.

(1) 评分最高添加算法, 见算法1.首先按照兴趣点的评分高低来选择, 根据游客选择的兴趣点类别和游玩顺序, 再从确定好的兴趣点类别访问顺序中选择合适的兴趣点.在本算法中, 我们逐天完成旅行线路中兴趣点的添加.首先, 初始化行程和每天的起点(行1-4), 之后逐天添加兴趣点(行5-9)在第一天里, 分别选择每一类中评分最高的兴趣点(行7), 添加完成之后作为第一天的旅行线路, 并在候选兴趣点中删除(行9).到了第二天, 从每一类别中选择已经游玩之外的兴趣点中评分最高的兴趣点作为这天的旅行路线.同理, 完成剩余天数的旅行线路添加.最后返回$D$天的旅行线路(行10).

算法1评分最高添加
输入: 出发地点$v_0$, 旅行天数$D$, 兴趣点类别的游玩顺序集合$Seq=\{q_1, q_2, \cdots, q_D\}$, 每一天的游玩顺序$q_i=\{c_1, c_2, \cdots, c_m\}$
输出: $D$天的旅行行程
1.  $TP=\{tp_1, tp_2, \cdots, tp_k, \cdots, tp_D\}$  //初始化多日行程
2.  for$k$:=1 to $D$ do
3.   $tp_k=\{v_0\}$  //初始化每天行程, 行程初始节点为$v_0$
4.  end for
5.  for $k$:=1 to $D$ do
6.   for $i$: =1 to $m$ do
7.    tempPOI$\leftarrow $Find the highest score POI in $c_i$      //将$c_i$中最高评分的兴趣点添加到旅行线路中
8.    $tp_k=tp_k\cup$ tempPOI
9.    Delete tempPOI   //将已经选择的兴趣点排除候选兴趣点集
10.    return $TP$

(2) 同步评分最高添加算法, 见算法2.不同于算法1, 为了保证多日旅行满意度的稳定性, 我们采取同步策略来添加兴趣点.通过游客确定好的兴趣点的类型以及游玩顺序, 同步完成$D$天每一类型兴趣点的添加.首先是初始化行程和每天的起点(行1-4). $D$天第一类的添加, 由于添加之前每天的兴趣点评分都为0, 所以第一类别按照天数从第一天到第$D$天依次添加该类别中没有被访问过的评分最高的兴趣点(行5-10).在$D$天第二类兴趣点的添加中, 首先将$D$天的当前每天兴趣点累积评分之和排序, 按照从低到高, 累积评分低的线路优先(行12), 选择该类兴趣点中没有访问过的最高评分兴趣点添加到线路中, 完成所有天第二类兴趣点的添加.同样地, 依此方法完成接下来所有类型兴趣点的添加(行11-16).最后返回$D$天的旅行线路(行17).

算法2  同步评分最高添加
输入:出发地点$v_0$, 旅行天数$D$, 兴趣点类别的游玩顺序集合$Seq=\{q_1, q_2, \cdots, q_D\}$, 每一天的游玩顺序$q_i=\{c_1, c_2, \cdots, c_m\}$
输出: $D$天的旅行行程
1.  $TP=\{tp_1, tp_2, \cdots, tp_k, \cdots, tp_D\}$  //初始化多日行程
2.  for $k$:=1 to $D$ do
3.   $tp_k=\{v_0\}$  //初始化每天行程, 行程初始节点为$v_0$
4.  end for
5.  while (POIType==$c_1$)
6.   for $k$:=1 to $D$ do
7.    tempPOI$\leftarrow $Find the highest score POI in $s_1$
8.  $tp_k=tp_k\cup$ tempPOI
9.    Delete tempPOI
10.  end while
11.  for $i$:=2 to $m$ do
12.    $TP=TP$.sort() by $s(tp)$       //将$D$天的当前旅行线路中的兴趣点评分之和排序, 线路评分较低的线路优先选择
13.   for $k$:=1 to $D$ do
14.    tempPOI$\leftarrow $Find the highest score POI in $c_i$       //将$c_i$中最高评分的兴趣点添加到旅行线路中
15.   $TP[k]=TP[k]\cup$ tempPOI
16.   Delete tempPOI
17.  return $TP$

(3) 同步评分时间添加算法.通过算法2, 基本可以得到多条满意度均衡的旅行线路.然而, 在添加兴趣点时由于只考虑了兴趣点的评分因素, 导致可能出现游玩该线路兴趣点所耗交通时间过长, 然而游客一般不会选择一条交通时间过长的旅行线路.为了使旅行线路更为优化, 我们通过计算兴趣点的评分和兴趣点之间交通时间的比值来得出最佳的兴趣点添加策略.假设已选择类型$i$中兴趣点$a_i$, 当选择第$(i+1)$类中兴趣点时, 计算第$(i+1)$类所有兴趣点的评分与该类兴趣点距离$a_i$的交通时间的相对比值, 添加比值最高的兴趣点.将此策略作为兴趣点添加的策略, 即将算法2中的行7改为找到相对比值最大的兴趣点, 其余部分与算法2相同.

4 实验评估

通过具体的实验来测试本文所提出的方法, 利用人工数据来验证方法的具体结果.

实验设置.选择上海作为旅游地点, 使用某旅行网中的景点推荐栏目获取游客可能游览的兴趣点集.在本次实验中, 根据兴趣点的性质, 如自然、人文等, 将所有的兴趣点分为10种类型, 在考虑到每种类型中兴趣点的人流量和受欢迎程度后, 去除一些质量较差的兴趣点, 确定每种类型的兴趣点数为20.通过谷歌地图搜索, 可以知道兴趣点之间的交通距离.之后, 对兴趣点进行评分(从0到10), 使用某旅行网中游客兴趣点的签到数据来统计该兴趣点的人流量, 利用游客的评价信息来统计兴趣点的受欢迎度.通过人流量和受欢迎度两项指标计算出每一个兴趣点的评分.在计算多日旅行效益值时, 需要计算旅行兴趣点总评分以及$D$天旅行兴趣点评分的标准差, 其中$D$天旅行兴趣点标准差为衡量游客多日旅行的稳定程度.不同的人对多日旅行的稳定程度要求不同, 通过改变$\lambda$的值可改变旅行稳定度在旅行效益值所占比重.在以下实验的参数中, 令$\lambda$的值为旅行天数$D$.

实验分析.多日旅行规划中3种算法的效果取决于两个因素:首先是兴趣点数量的变化, 当游客选择兴趣点的类型数量不同或者是兴趣点类型中兴趣点的数量变化时, 都会影响候选兴趣点的变化; 其次, 游客选择的旅行天数不同也会使算法选择不同的旅行线路.

首先研究兴趣点数量的变化.为了简化实验, 设置每一类型兴趣点的数量为20, 通过兴趣点类型变化, 来改变整体兴趣点的数量.假设旅行天数$D=3$, 当兴趣点类型数量变化时, 图 2显示了3种算法在兴趣点类型数量变化时旅行效益值的变化, 结果表明, 后两种算法相对于算法1可以得到较高的旅行效益值, 即游客的多日旅行满意度更高, 这是由于后两种算法考虑到了多日旅行的稳定度.同步评分时间添加算法的旅行效益值相比算法2较低, 这是因为同步评分时间添加算法考虑了时间的影响.在图 3中, 显示了3种算法在兴趣点数量变化时平均每天所需要的旅行时间, 结果显示同步评分时间添加算法相比前两种算法更加节省时间, 这是因为该算法在添加兴趣点时考虑了交通时间的影响. 图 4中, 显示了3种算法搜索线路所需时间, 结果显示3种算法都可以在较短的时间里得出旅行路线.

在实验中, 同时研究了旅行天数的变化对旅行效益值的影响.在研究天数变化时, 设定每日旅行兴趣点类别数量为7, 在图 5中, 显示了游客在选择旅行天数从第一天到第五天时, 旅行效益值的变化, 可以看出随着天数增多, 旅行效益值也增大.这是因为在天数增多时游客可以游览更多的兴趣点, 使得旅行效益值更大.算法2和同步评分时间添加算法能够使游客获得更多的旅行效益.在图 6中, 实验显示了3种算法的旅行线路平均每天所需旅行时间, 结果表明同步评分时间添加算法相比前两种算法可以使游客更为节省时间. 图 7则是在旅行天数变化时, 3种算法搜寻旅行线路所需时间.

5 结论以及未来工作

本文研究推导出了一种新的旅行规划方式, 即多日旅行规划.在多日旅行规划中, 考虑了游客在多日旅行中满意度的稳定性问题, 提高了游客多日旅行的旅行质量.在选择旅行线路时, 提出了3种启发式算发, 3种算法都能够在短时间内规划出多日旅行路线, 其中同步评分最高添加算法和同步评分时间添加算法可以得到更高的旅行效益值, 同步评分时间添加算法则可以使游客节省更多的时间.

在以后的工作中, 我们会在多日旅行规划中考虑游客对时间限制的要求, 研究在动态的交通变化中, 如何更好地规划旅行路线.