引言

旅游在日常生活中已经变得越来越普遍。然而据统计，游客大多数时间都花在路上或者走马观花上，只有20%的时间花在游览景点上，而且大多数游客对景区的环境、布局不清楚，游览时间有限。因此合理规划旅游路径^[1-3]很有必要。

传统的迪杰斯特拉算法被广泛应用在路径推荐中，但其无法应用在离散型问题的求解上；一些被业内广泛接受的智能算法如A^*算法、遗传(genetic algorithm, GA)算法^[4]、粒子群(particle swarm optimization, PSO)算法^[5]等在优化方面都有不错的表现，但都没有具体针对的应用场景。目前国内外关于景区路径推荐的研究主要集中在提高游客满意度^[6-8]和游览效率^[9-10]这两方面，具体做法分为三类：一是在评价路径好坏的计算中考虑景点流行程度或者景点热门程度等因素，将流行程度高和热门程度高的景点推荐给游客；二是以景点类别来计算路径的收益，将包含更多游客喜爱的景点类别的路径推荐给游客；三是采用动态规划的方式实时调整游览路径，借以提高路径的游览效率来满足游客的需求。但是以上方法都没有精确地推荐游客喜爱的景点，而且动态规划的计算过程较为复杂，对设备的要求比较高。文献[11]采用大数据分析的方法，能根据历史数据较准确地推荐游览效率高的路径，但是这种方法存在历史数据少和获取困难等问题。

针对以上旅游路径推荐中存在的问题，本文在离散PSO算法的基础上提出了一种新的景区路径推荐算法(selective tour for route recommendation，STRR)，来帮助游客在满足个性化需求的同时选择游览效率最高的路径。本算法首先通过对景区进行离散化建模，并利用弗洛伊德(Floyd)算法获得最短距离的邻接矩阵；再根据游客输入想要游览的景点来构建以离散景点序列为优化对象的优化模型，以满足游客的个性化需求；最后采用优先级规则改进离散PSO算法中粒子更新的方式，用以快速优化景点序列，得到最短路径。通过仿真实验和与其他算法对比，验证了本文算法的优越性。

1 模型建立 1.1 景区离散化建模

景区由景点和道路组成，大部分景区中没有很大的活动空间，而且更多景区的道路狭窄，游客只能在固定的空间内进行活动。游客游览时与景点的位置、方位以及景区的出入口等有直接联系，且需将游客想要游览的景点转化成计算机识别的模型，因此本文采用了对景区进行离散化建模。

景区离散化建模的过程包括3个步骤。

(1) 根据景区的空间模型图建立景区的平面图如图 1所示。

(2) 选择合适的粒度将景区的道路分解成不重叠的n个区域(图 2)，以确保每个景点的出入口唯一对应一个区域。

(3) 将由编号的小区域组成的路网分离出来，区域作为节点，相邻的区域之间用无向边连接，则路网可表示成一个无向图。将相邻区域之间的距离设成一个单位；没有直接相连的区域之间需要经过中间节点后才能到达，因此将没有直接相连区域之间的初始距离设置成无穷。

1.2 最短游览路径的模型优化

本文算法根据游客自己输入想要游览的景点自动生成离散的景点序列，用以满足游客的个性化需求；为了推荐一条从景区入口开始，经过游客想要游览的景点，抵达景区出口的游览效率最高的路径，本文提出了以自动生成的景点序列为优化对象的最短游览路径的模型优化。

假如游客想要游览景区中的n个景点，利用景区空间模型图，将这n个景点与景区空间模型图上的空白小区域进行对应，可以得到n个区域即n个节点，将这些节点表示成集合N={v_i|i∈[1, n]}。用G=＜V, E＞表示景区空间模型图，其中V表示该模型中所有节点的集合，E表示该模型中所有无向边的集合；用节点v₀表示游客游览景区的入口节点，v_n+1表示游客游览景区的出口节点，则集合L=N∪{v₀, v_n+1}表示通过景区入口节点、经过游客想要游览景点的节点、最终抵达出口节点的路径的集合；用R={v₀, …, v_i, …, v_n+1|v_i∈N}表示一条经过景区入口节点v₀、经过游客想要游览的n个节点、再到出口节点v_n+1的路径。由弗洛伊德算法可以得到无向图中任意两点之间的最短距离d和最短路径s，其中路径R={v₀, …, v_i, …, v_n+1|v_i∈N}代表路径集合L中的一条路径，那么最短路径^[12-13]的优化问题可以表示为：

$\begin{array}{l} {\rm{min}}:D = \left( {\sum \;d({v_i},{v_{i + 1}})} \right)\\ \quad {\rm{s}}{\rm{.t}}.:\\ \quad \quad {v_i} \in R\\ \quad \quad {v_{i + 1}} \in R\\ \quad \quad 0 ＜ d({v_i},{v_{i + 1}}) ＜ \left| V \right|\\ \quad \quad i = 0,1, \cdots ,n + 1 \end{array}$

(1)

其中，D作为优化目标，表示从入口v₀经过游客想要游览的节点集合N后，抵达出口v_n+1的所有路径中最短的距离；d(v_i, v_i+1)表示节点v_i到节点v_i+1之间的距离；|V|表示节点集合V中节点的个数。该问题在本质上等同于TSP^[14-15]问题，本文利用STRR算法进行求解。

2 利用STRR算法求解

由于本文所解决的路径优化问题是离散的节点，传统的连续型PSO算法并不能很好地解决该问题，因此本文提出改进的离散PSO算法即STRR算法对该问题进行求解。STRR算法基于离散型PSO的原理，利用优先级规则改进粒子的更新过程，其计算流程如图 3，主要包括离散编码、粒子群的初始化、适应度函数、最短距离、基于优先级规则的更新操作5个步骤。

2.1 离散编码

将游客想要游览的景点与景区离散化空间图进行映射，可得到与景点对应的节点集合，集合中节点组成的每一个序列都是一种游览方案。例如，游客想要游览的景点得到节点的集合{v₁, v₂, v₃, v₄, v₅, v₆, v₇, v₈, v₉, v₁₀}，且入口和出口分别是节点v₀和节点v_n+1，则序列{v₀, v₁, v₂, v₃, v₄, v₅, v₆, v₇, v₈, v₉, v₁₀, v_n+1}表示游客从v₀进入，按顺序经过想要游览的节点，再从v_n+1离开的一个游览方案。

2.2 粒子群的初始化

离散编码后需要确定一定数量的粒子加入初始种群，初始种群的大小根据问题的复杂程度来确定。例如当游客想游览的景点数量为8个时，总的游览方案就有40 320种，选择100个粒子作为初始种群；而景点数量为10个时，总的游览方案就有3.63×10⁶种，则选择1000个粒子作为初始种群。

2.3 适应度函数

在获得游客想要游览的景点之后，接下来就是找到游览效率最高的路径，即找到穿过所有游客想要游览景点的最短路径。适应度函数是衡量路径优劣的标准，本文利用高斯函数构造了如式(2) 所示的适应度函数：

$f = \frac{1}{{\delta \sqrt {2{\rm{ \mathsf{ π} }}} }}{\rm{exp}}\left( { - \frac{{{{\left( {\left( {1 - \frac{{{l_x} - {l_{\rm{b}}}}}{{{l_{\rm{a}}} - {l_{\rm{b}}}}}} \right) - \mu } \right)}^2}}}{{2{\delta ^2}}}} \right)$

(2)

其中，l_b表示当前粒子群中所有路径长度的最小值，l_a表示最大值，l_x表示当前计算适应度值的路径长度。当l_x=l_b时， $\frac{{{l_x} - {l_{\rm{b}}}}}{{{l_{\rm{a}}} - {l_{\rm{b}}}}}$ =0，此时适应度为最优。

2.4 最短距离

适应度函数的计算过程中需要求解路径的长度，因此需要求解任意两点之间的最短距离。本文采用Floyd算法对任意两点之间最短距离进行求解，该算法是通过如式(3) 所示的邻接矩阵来计算的。

$\begin{array}{l} \quad \;\;\;{v_1}\quad {v_2}\quad \cdots \quad {v_{n - 1}}\quad {v_n}\\ \begin{array}{*{20}{l}} {{v_1}}\\ {{v_2}}\\ {\; \vdots }\\ {{v_{n - 1}}}\\ {{v_n}} \end{array}\left[ {\begin{array}{*{20}{l}} 0 & 1 & \cdots & \infty & \infty \\ 1 & 0 & \cdots & \infty & 1\\ {\; \vdots } & {\; \vdots } & {} & {\, \vdots } & {\; \vdots }\\ \infty & \infty & \cdots & 0 & 1\\ 0 & 1 & \cdots & 1 & 0 \end{array}} \right] \end{array} $

(3)

其中v₁，…，v_n表示节点，矩阵中的元素表示节点之间的距离。

首先，根据离散路网图构建邻接矩阵D，如公式(3)，作为初始邻接矩阵D⁽⁰⁾；其次，利用初始邻接矩阵D⁽⁰⁾，通过迭代计算求得D⁽¹⁾…D⁽ⁿ⁾；最后，当遍历完所有节点时，得到最短距离矩阵D⁽ⁿ⁾。为了记录任意两点之间的最短路径，用矩阵S保存任意两点之间路径的第一条弧的结束节点。当邻接矩阵D更新时，矩阵S也作相应的更新。利用Floyd算法求解任意两点之间最短距离和最短路径的步骤如下。

1) 初始化D⁽⁰⁾、S⁽⁰⁾。设D⁽⁰⁾=D，S⁽⁰⁾=(s_ij⁽⁰⁾)_n×n，其中n为节点数，s_ij⁽⁰⁾=－1，1≤i, j≤n。

2) 计算D⁽²⁾, D⁽³⁾, …, D^(n－1), D⁽ⁿ⁾; S⁽²⁾, S⁽³⁾, …, S^(n－1), S⁽ⁿ⁾。假设迭代过程中第k个矩阵为D^(k)=(d_ij^(k))_n×n，S^(k)=(s_ij^(k))_n×n，第k-1个矩阵为D^(k－1)=(d_ij^(k－1))_n×n，S^(k－1)=(s_ij^(k－1))_n×n，则迭代过程的具体关系如式(4)、(5)。

$d_{ij}^{\left( k \right)} = \left\{ {\begin{array}{*{20}{l}} {d_{ij}^{\left( {k - 1} \right)},} & {d_{ij}^{\left( {k - 1} \right)} \le d_{ik}^{\left( {k - 1} \right)} + d_{kj}^{\left( {k - 1} \right)}}\\ {d_{ik}^{\left( {k - 1} \right)} + d_{kj}^{\left( {k - 1} \right)},} & {d_{ij}^{\left( {k - 1} \right)} > d_{ik}^{\left( {k - 1} \right)} + d_{kj}^{\left( {k - 1} \right)}} \end{array}} \right.{\rm{ }}$

(4)

$s_{ij}^{\left( k \right)} = \left\{ {\begin{array}{*{20}{l}} {s_{ij}^{\left( {k - 1} \right)},} & {d_{ij}^{\left( {k - 1} \right)} \le d_{ik}^{\left( {k - 1} \right)} + d_{kj}^{\left( {k - 1} \right)}}\\ {s_{ik}^{\left( {k - 1} \right)},} & {d_{ij}^{\left( {k - 1} \right)} > d_{ik}^{\left( {k - 1} \right)} + d_{kj}^{\left( {k - 1} \right)}} \end{array}} \right.$

(5)

3) 得到D⁽ⁿ⁾和S⁽ⁿ⁾。当n个节点遍历结束时，得到表示最短距离的矩阵D⁽ⁿ⁾和表示最短路径的矩阵S⁽ⁿ⁾。

2.5 基于优先级规则的更新操作

离散粒子群算法作为常用的智能优化算法之一，通常采用粒子元素的替换和粒子元素位置的交换两种方式来更新粒子，其中粒子更新的标准公式如式(6)、(7)。

$v_{im}^{k + 1} = wv_{im}^k + {c_1}(p_{im}^k - x_{im}^k) + {c_2}(g_{im}^k - x_{im}^k)$

(6)

$x_{im}^{k + 1} = x_{im}^k + v_{im}^{k + 1}$

(7)

其中，k表示迭代次数，c₁和c₂是加速系数，r₁和r₂是[0, ∞)之间的随机数，w是惯性权重。

粒子元素的替换可能会导致粒子中出现重复元素，从而破坏了解的AllDifferent规则，因此更多离散粒子群算法在粒子更新的操作过程中采用元素位置交换的方式。然而粒子元素交换位置会导致解的更新速度变慢，容易陷入局部最优等问题。基于优先级规则的更新操作采用了粒子元素替换的策略，并通过优先级规则对重复元素重新排序的方式来解决元素重复的问题。粒子元素替换的策略包括位置减位置操作、速度加速度操作、系数乘速度操作、位置加速度操作。

a) 位置减位置操作Θ：位置相减操作会得到一个新速度。假定x, y分别代表两个粒子，X, Y分别表示两个位置，且x∈X, y∈Y，则操作xΘy会得到一个新速度v

$v = ({y_i} \to {x_i}),i \in 1,n]$

(8)

其中，n表示粒子的维度。

b) 速度加速度操作⊕：速度相加操作会得到一个新速度。假定v=bΘa，w=yΘx，则u=v⊕w表示速度v与速度w相加得到的新速度，速度u可表示为

$u = \left\{ {\begin{array}{*{20}{l}} {({a_i} \to {y_i}),{b_i} = {x_i}}\\ {({x_i} \to {b_i}),{a_i} = {y_i},i \in \left[ {1,n} \right]}\\ {({a_i} \to {b_i}),{\rm{其他}}} \end{array}} \right.$

(9)

c)系数乘速度操作⊗：系数乘速度操作会得到一个新速度。假定v=xΘy，系数为c，则u=c⊗v表示系数c与速度v相乘得到的新速度，速度u可表示为

$u = \left\{ {\begin{array}{*{20}{l}} {({x_i} \to {y_i}),} & {c \in \left[ {0,1} \right]}\\ {({x_i} \to {x_i}),} & {c \in \left( {1,\infty } \right)} \end{array}} \right.{\rm{ }}$

(10)

d)位置加速度操作⊕：与连续PSO算法一样，位置加速度操作会得到一个新位置。假定x表示一个粒子，X表示一个位置，且x∈X，v=zΘy表示一个速度，则p=priority(x⊕v)是一个新的位置，具体形式如式(11)：

$p=\text{priority}\left( p{}^\circ \right)~$

(11)

其中， $p{}^\circ =\left\{ \begin{array}{*{35}{l}} {{z}_{i}},\text{ }{{x}_{i}}={{y}_{i}} \\ {{x}_{i}},\text{ }{{x}_{i}}\ne {{y}_{i}} \\ \end{array} \right.\text{ ,}i\in \left[ 1,n \right]$ 。

本文设置的优先级规则是离终点越远的节点优先级更高，优先级的计算如式(12)

$f = {\rm{ln}}(1 + {{\rm{e}}^{{l_x}}})$

(12)

其中l_x是当前节点到终点的最短距离，由于距离l_x是正值，所以l_x值越大f的值越小。

粒子更新的过程如下。设粒子a的序列是{v₁, v₂, v₃, v₄, v₅, v₆, v₇, v₈, v₉, v₁₀}，速度v是[v₂→v₈, v₃→v₉, v₆→v₈, v₇→v₅]，则粒子a经过速度v的变化后得到新粒子b的序列{v₁, v₈, v₉, v₄, v₅, v₈, v₅, v₈, v₉, v₁₀}，而新粒子b中出现了重复的元素{v₅, v₈, v₉}，如图 4(a)所示。含有重复元素说明粒子b破坏了元素的AllDifferent规则，因此采用优先级规则对粒子进行去重：首先将粒子b中的重复元素去掉，得到序列c，如图 4(b)；然后将粒子b中重复的元素所对应于粒子a中的元素取出，得到序列d{v₂, v₃, v₅, v₆, v₇, v₈, v₉}，如图 4(c)；将序列d按照优先级大小重新排序，假设序列d经过优先级规则排序后得到的新序列e为{v₃, v₆, v₇, v₂, v₅, v₈, v₉}，如图 4(d)；最后，将序列e按顺序插回图 4(b)中重复的位置，得到新粒子f的序列为{v₁, v₃, v₆, v₄, v₇, v₂, v₅, v₈, v₉, v₁₀}，即粒子a由速度v变化后，再经过优先级规则处理后得到新的粒子e，如图 4(e)。

经过优先级规则处理后的粒子更新公式变为：

$v_{im}^{k + 1} = w \otimes v_{im}^k \oplus {c_1} \otimes (p_{im}^k\mathit{\Theta }x_{im}^k) \oplus {c_2} \otimes (g_{im}^k\mathit{\Theta }x_{im}^k)$

(13)

$x_{im}^{k + 1} = {\rm{priority}}(x_{im}^k \oplus v_{im}^{k + 1})$

(14)

其中，v表示粒子更新的速度，x表示粒子的位置，p表示粒子当前最好的位置，g表示整个粒子群最好的位置，w是防止陷入局部最优而设置的惯性权重，c是为了加快迭代效率而设置的加速系数，m代表粒子群中粒子的个数。通常，加速系数c₁，c₂都设置成2，惯性权重w设为0.7。

3 实例分析及仿真

为了验证算法的有效性和高效性，以北京化工大学东校区为例进行实例验证。图 5是北京化工大学的平面图，按照景区离散化的方法处理后得到的离散化空间图如图 6所示。

根据游客的需求从不同维度进行多组实验，分别设置游客想游览的景点数为5、8、10、11、12、15、16、18、20个(每组实验中的景点都是随机生成的)，并通过与离散化空间图中的路网区域映射得到游客想要游览的节点，再加上入口节点和出口节点，便构成游客需要参观的节点集合；其次，利用STRR算法进行计算，得到游览路线。每组实验随机选取一定数量的粒子作为初始种群进行迭代，若达到最大迭代次数或满足要求(与最优适应度的误差为1×10^-5内)便停止迭代，每组实验重复进行10次。

由于初始种群粒子数超过1×10⁶时，迭代过程会变得复杂，因此为了简化计算，节点数超过15时初始种群的粒子数都选择1×10⁶。实验中选取的节点数与初始种群的粒子数之间关系如表 1。

根据景区的离散化空间图来计算任意两节点之间的最短距离和最短路径，以便适应度值和优先级的计算。以图 6的离散化空间图计算，得到158×158的最短距离矩阵D。

$\mathit{\boldsymbol{D = }}{\left[ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{l}} 0 & 1 & 2 & 3 & 4 & 4 & 5 & 6\\ 1 & 0 & 1 & 0 & 3 & 3 & 4 & 5\\ 2 & 1 & 0 & 1 & 2 & 2 & 3 & 4\\ 3 & 2 & 1 & 0 & 1 & 1 & 2 & 3\\ 4 & 3 & 2 & 1 & 0 & 2 & 3 & 4\\ 4 & 3 & 2 & 1 & 2 & 0 & 1 & 2\\ 5 & 4 & 3 & 2 & 3 & 1 & 0 & 1\\ 6 & 5 & 4 & 3 & 4 & 2 & 1 & 0 \end{array}} & \cdots \\ \vdots&\ddots \end{array}} \right]_{158 \times 158}}$

以序列{30, 46, 50, 80, 105, 110, 120, 130, 140, 150}为例进行仿真。假设游客选择入口为南门(节点14)，出口为北门(节点151)。利用STRR算法进行计算，在选取的20组样本中，最少需要迭代6次、最多15次便可得到最优解，生成的最短距离是67，最短路径是序列t:{14, 30, 46, 50, 80, 110, 105, 120, 130, 140, 150, 151}。计算结果意味着游客想要游览这10个景点，需要走过的最短距离是67；最短路径是按照t序列游览生成的路径，其中连续两个节点之间的路径由Floyd算法得到的最短路径进行填充。

使用Matlab进行平面仿真，将需要访问的节点用黑色标识，路径上经过的节点用灰色标识，得到一条完整的连接入口、访问节点及出口的最短路径，结果如图 7所示。

为了验证STRR算法的优势，将STRR算法与GA、离散PSO、GA-PSO进行了对比。实验中GA和PSO算法的参数设置如表 2、3所示，得到的实验结果如图 8所示。

由图 8可以看出，与PSO、GA、GA-PSO算法相比，节点数为5、8、10、11、12、15、16、18、20时，STRR算法的迭代次数比其他3种方法都要少，选择20个以内节点时STRR算法只需要少于50次的迭代便可得到最优路径；同时根据折线走势看出，STRR算法在计算效率上也都优于其他3种方法。

4 结束语

针对当前旅游推荐系统推荐路线单调，很少考虑到游客的个性化需求以及游览的效率的问题，本文提出了面向选择性游览的景区路径推荐算法。本算法能根据游客的个性化需求，自动生成一条始于景区入口，历经感兴趣的景点，终止于景区出口的最短路径。仿真实验结果表明，STRR算法能够得到一条既满足游客个性化需求且游览效率最高的路径，并在计算效率方面优于其他算法。