基于回溯蚁群-粒子群混合算法的多点路径规划

刘丽珏，罗舒宁，高琰，陈美妃

（中南大学信息科学与工程学院，湖南 长沙 410083）

1 引言

随着智慧旅游的兴起，为了向游客提供更精准的导游服务，不少景区推出了官方App。单一基于道路网的导航方式已经难以满足游客对精准化、个性化导航寻径的需求。针对旅游景区个性化导航需求，不少论文提出了路径规划算法。文献[1]通过改进A*算法，融合多维动态环境信息，提出了景点间动态路径规划的解决方案。文献[2]以鼓浪屿景区为例，改进Dijkstra算法，实现了对该景区旅游线路的规划。文献[3]考虑了景区路径的复杂性，将景区路径分为全景区图和子景区图，改进蚁群算法实现了景区路径规划。文献[4]运用混合密度聚类方法识别景点热度，改进传统蚁群算法，提出了一种新型的热门游览景点路径规划方法。这些算法和模型仅仅解决了从起点到终点之间的最优路径规划问题。但在实际的旅游需求中，游客或旅游大巴进行路径规划时，更希望能得到一条从起点出发，经过某些必去的景点（必经点）的最短规划路线，以便游客无遗漏且更省时间地进行游览。

鉴于此问题，本文参考TSP（traveling salesman problem）问题解决方法，提出了一种回溯蚁群-粒子群混合算法（BAPM，backtracking ant colonyparticle swarm method），可用于解决景区中从某个旅游景点开始经过一些特定旅游点的多点路径规划问题，该问题的解决对旅游景区多点路径规划具有一定的参考价值。

本文将景区景点抽象为点，将景区路径抽象为有向线段，将景区图抽象为非完全有向图，从而对该图模型进行描述，并且利用该图模型，实现本文提出的BAPM算法。

2 基本知识

2.1 最大最小蚁群系统

最大最小蚁群系统（MMAS，max-min ant system）[5]是目前众多蚁群算法中效率较高的算法之一，它模拟了蚂蚁在觅食过程中寻找路径的场景，对当前路径不断地进行优化，从而找到最短觅食路线。该算法中，节点i到节点j路径上的启发因子记作ηij；在第t次迭代中，节点i到节点j路径上的信息素记作τij（t）；ηij与τij（t）的占比将会成为第t次迭代中蚂蚁k站在节点i选择下一个节点j所走路径的重要因素，记作（t），该因素值越大，选择该值对应的节点的概率就越高。反复迭代该算法，最终可以得到一条近似最短路径。在迭代过程中，信息素τij（t）根据蚂蚁寻找到的最优权值变化进行更新。信息素τij（t）将会被限制在最大最小信息素范围之间，使该方法不会在短时间内快速收敛陷入局部最优。

2.2 粒子群优化算法

粒子群优化（PSO，particle swarm optimization）算法[6]模拟鸟群或鱼群的觅食方法，不断地更新当前位置及下一时刻的方向及速度，使其不断逼近目标。在PSO算法中，每个粒子通过不断的自我学习与向迭代最优粒子学习来改进自身的速度及位置，从而达到一个最优结果。

MMAS算法相对于传统的蚁群算法来说，极大程度地避免了局部最优情况的发生，并且增加了该模型找到最优值的概率，但是在节点数量非常多的情况下，MMAS仍然容易陷入局部最优，它的最大最小值的限制在避免算法快速陷入局部最优的同时，也降低了其寻找到最优路径的可能性，即忽略了信息素中的优越因子。为了增强算法寻找最优路径的能力，本文结合PSO算法和MMAS算法，对信息素τij（t）进行局部及全局更新，突出了对优越路段的标记，实现了对多点路径规划问题的有效处理。

3 回溯蚁群-粒子群混合算法

本文提出运用回溯蚁群-粒子群混合算法（BAPM）解决旅游景区中的多点路径规划问题。该算法结合了MMAS算法和PSO算法，增强了路径寻优能力，避免了算法过早陷入局部最优，并改善了算法寻优能力弱的问题，在对比实验部分，也达到了较为理想的测试结果。该算法如算法1所示。

算法1回溯蚁群-粒子群混合算法

1）使用Floyd-Warshall算法将图G转换成，更新权值，用city表示中节点个数

2）建立的权值矩阵，如果两点之间没有路径，则=-1

3）设置迭代次数num和蚂蚁数量m

4）初始化信息素τ、启发因子η、信息素和启发因子的相关重要性参数α与β、学习因子中的可调参数ω、衰减因子ρ、最小信息素可调参数pbest、迭代代数i=1、全局最优路径 pathgb、局部最优路径pathlb及蚂蚁所处当前节点startpoint

5）whilei≤num

6）初始化path记录每只蚂蚁走过的路径

7）forj=1:m

8）startpoint=s

9）设置 city×city的矩阵 tabu_arc，如果=-1，那么tabu_arc（i,j）=-1，设置邻接表tabu_node用于存放蚂蚁当前到达点的可行路段，设置不定长数组node记录pathj中经过的所有不重复节点

11）if count（tabu_node（startpoint））＞0

12）计算 tabu_node（startpoint）中的所有路段的被选择概率

14）更新变量,startpoint=b、ifb∉node,node={n ode,b}

15）else

16）回溯到tabu_arc的上个状态, 删除pathj中的最后一条路段,更新startpoint、node,并在tabu_node中对当前不可行路段进行标记

17）end if

18）end while

20）用改进PSO算法局部更新信息素τ

21）end for

22）对全局最优路径 pathgb进行更新

23）对信息素τ进行全局更新

24）i=i+1

25）end while

本文所提 BAPM 算法中关键的几个部分为：原始图G转换成完全图；寻找可行路径，包括路径的编码、计算路径的被选择概率；信息素的局部更新和全局更新。下面分别对这几个部分进行详细说明。

3.1 图模型转换

从景区地图中抽象获得的图G是一个非完全有向图，它存在以下2种特殊情况：1）2个节点之间没有一条直接连接的路径，2）直接连接路径的权值比间接路径的权值大。因此在处理图G之前，本文重新构建图模型，以便更好地计算出多点最短路径。

假设N为非完全连通图G=（V,A）中所有节点的个数，其中有n（n≤N-1）个节点为必经节点，从节点s出发，寻找一条经过这n个必经节点一次且仅一次，再返回起始节点s的最短路径。将起始点s看作固定点，s∈V，必经点集为M⊆V-{s} 。本文通过以下步骤实现问题的转换。

步骤 1生成新的顶点集合显然是V的子集。

步骤 2生成新的边集合且i,j在G中存在路径} ，显然，由于G是一个连通图，G中任意两点间都有路径，则）是一个完全图。

步骤 3计算图中每条边的长度，令中的任意两点i、j之间的距离为图G中i、j之间最短路径的长度，由于G是连通图，图中任意两点间都有路径，即该长度不会等于无穷大。在图G中求i、j两点之间的最短距离使用了Floyd-Warshall[7]算法。

很明显，通过以上3个步骤建立了一个完全图，其点集合只包含G中的起始点s和必经点集合M，边的长度则对应边的2个端点在G中的最短路径长度，则原问题转换为在完全图中找寻一个最短Hamilton圈的TSP问题。

图1 多点路径规划原问题

图2 多点路径规划转换后

图1所示为非完全连通图。需要从点1出发，前往点2、点3、点4、点5、点6进行游览，之后回归点1，起始点s=1，M={ 2 ,3,4,5,6}。将图1中必经点提取出来构成图2，运用Floyd算法计算集合M中每两点之间最短路径长度，将其作为图2中的边长。

斯坦纳旅行商问题[8]（STSP，Steiner traveling salesman problem）与本文所述问题相似，都是解决经过必经点的路径规划问题，并且必经点可以重复使用。不同之处点在于STSP有固定的起始点和终点，而本文所述问题仅需要固定起始点。由于必经点可以重复使用，为了让该问题在定义上更加准确，引入引理1[8]。

引理1在 STSP最佳解决方案中，任何一条有向边仅能遍历一次。

也就是说，在图的最优路径中，点集中的节点可以重复使用，但边集中的有向边不能重复使用。本文基于此规则实现了BAPM算法对最小权值路径的搜索。

3.2 寻找可行路径

3.2.1 路径编码

将景区地图按照3.1节步骤1～步骤3进行转换后，问题转变为从转换后的图中给定的起始点s出发，需要找到一条经过所有必经点的可行路径。

由3.1节可知，为转换图的有向边集合。从节点i出发到达节点j的有向边记作（i,j）。本文用图中的边构成的位串对路径进行编码，将蚂蚁a寻找到的路径patha表示为

将路径patha中包含的所有不重复节点的集合记作node；使用禁忌表tabu_arc对有向边集合进行管理，保证在patha中的有向边不会重复出现；使用邻接表tabu_node来记录路径patha当前到达节点的可选路段；startpoint记录路径当前到达的节点，当路径patha经过（i,j）时，可以说当前路径patha到达了节点j，此时startpoint=j。

3.2.2 可行路径的寻找与路段的选择

根据图 2，初始化的权值矩阵和禁忌表tabu _ arc为

其中，存放路段的权值，tabu_arc表示路径段的使用状态，“0”表示该路径可行，“-1”表示该路径不可行。

寻找一条可行路径的方法如下。蚂蚁a从起始点startpoint=s开始寻找路径，根据tabu_node（startpoint）得到下一时刻的所有可选路段，选择其中一条路段（s,j），在tabu_arc中将已走过的路段标记为“-1”，同时，将路段（s,j）存入patha中，并且startpoint=j。为了减少算法的时间复杂度，tabu_node使用散列表进行存储。当执行到某个没有可行边的节点，即可行路段tabu_node（startpoint）为空或者均已被标记时，证明该路径不可行，则使用回溯方法，最终找到一条可行路径。

上述寻找可行路径的过程可简化表示为图3。

图3 寻找可行路径的迭代过程

在非完全有向图中，运用回溯方法查询路径可以避免产生非可行性路径，提高选择路径的效率。

Tabu_node表中，确定可选路段是该算法中的一个重要环节。在第k次迭代中，蚂蚁a在寻找路径时，会根据startpoint对应的tabu_node（startpoint）中每条路段的可行概率（k）,i∈,j∈，i≠j，选择概率大的路段，并根据已选择的路段到达下个节点d，startpoint=d。若tabu_node不存在可行路段，即 count（tabu_node（startpoint））=0，则删除patha中startpoint所对应路段，将蚂蚁到达的当前节点赋值给startpoint，释放tabu_arc中该路段的标记，继续寻找下一个可行路段，以此类推，直到所有必经点都包含在该蚂蚁的所行路径当中，即node=，此路径patha则为一条可行路径。这种寻路方式适应本文模型要求，使寻找路径更加灵活并且保证了每条路径的可行性，避免了非可行解的产生。

选择路段的概率计算式如式（1）所示。

3.3 更新信息素

3.3.1 信息素的全局更新

根据上述寻路方法，可以得到所有蚂蚁的可行路径path，找出其中权值最小的路径，记作 pathgb，并且记录每只蚂蚁的可行路径，记作 pathlb。在迭代过程中，找出权值最小的路径并且将其权值与pathgb的权值进行比较，将 pathgb替换成权值最小的路径，本文将 pathgb称作全局最优路径，同理，将pathlb替换成每只蚂蚁寻找到的权值最小的路径，称作局部最优路径。

当所有蚂蚁均寻找到一条可行路径后，需要更新图中每个路段对应的信息素。信息素τij（t）描述了蚂蚁经过各个路段所留下的痕迹，本文将τij（t）值较大的路段称为优越路段，信息素更新如式（2）所示。

其中，参数ρ（0≤ρ≤1）为衰减因子，用于冲淡信息素的浓度；为全局最优路径 pathgb的信息素增量，计算式如式（3）所示。

为了避免信息素过快地陷入局部最优，设置最大信息素τmax和最小信息素τmin，如式（4）和式（5）所示，则信息素更新范围为τmin≤τij（t）≤τmax。

其中，city表示点集的大小；pbest表示一个可调参数，本文取值为0.005。

3.3.2 信息素的局部更新

设置最大最小信息素后，随着迭代次数的增多，优越路段得不到有效的突出，使算法容易陷入局部最优，造成最终得到的最短路径与期望路径存在较大差距。本文结合改进后的PSO算法，突出路径中较优路段的信息素，以保证算法能产生更为接近最短路径的结果。

基本的 PSO算法通常用于连续函数寻找最优解的问题，粒子从随机的初始位置出发，不断改变自身的速度和位置，每次迭代均飞向自身最优和全局最优位置的加权中心，以达到自我认知和信息共享的目的。本文建立了所讨论问题和PSO算法之间的映射关系，将问题空间映射到粒子空间，将问题离散化。

将每只蚂蚁a的可行路径patha看作一个粒子，将当前的信息素τ看作粒子的当前位置，将信息素的增量看作PSO算法中的速度变化量。

本文定义了 2个变量——全局最优路径片段pgb和局部最优路径片段plb，用于计算粒子的运动速度。全局最优路径片段为蚂蚁当前找到的路径与全局最优路径中相同的路径片段集合，局部最优路径片段为蚂蚁当前找到的路径与其自身曾找到的最优路径中相同的路径片段集合。若蚂蚁a找到当前路径为patha，其计算式为

全局最优路径为

局部最优路径为

则全局最优路径片段为

局部最优路径片段为

在蚂蚁a寻找到可行路径patha后，得到pgb和plb，增加pgb、plb对应路段的信息素，信息素增长式如式（6）～式（9）所示。

在迭代过程中，不断地更新 pathlb和 pathgb，从而更新plb和pgb对应的信息素，使信息素不断地向有益于获取最优路径的方向增长，从而使算法能够更加快速有效地得到图中的最短路径。

4 实验结果与分析

本文的实验主要分为4个部分。第一部分将本文所提BAPM算法与MMAS算法、遗传算法（GA，genetic algorithm）进行比较，展示BAPM算法在精确度上的优越性，本文选择了TSPLIB数据库中的数据进行实验。第二部分为仿真实验，运用BAPM算法寻找包含多点的最短路径，然后运用分支定界法[9-10]找出这个图中的精确最短路径，验证 BAPM算法寻找最短路径的正确性。第三部分为景区地图实际规划结果，展示了BAPM算法在一个实际的景区地图数据上的实验结果。第四部分对上述实验进行总结。

4.1 TSPLIS数据库实验

为了验证 BAPM 算法有效地改进了局部最优问题并且能找到更为接近的最短路径，本文使用MMAS算法和GA算法作为对比算法，3种算法均在 MATLAB（R2014a）上进行实现，且迭代次数相同。BAPM算法的参数设置如表1所示。

表1 BAPM算法参数

分别运用BAPM算法、MMAS算法和GA算法对TSPLIS数据库中提供的14组数据进行实验，每种算法各运行10次，获取每组数据在不同算法中运行得到的最大路径长度、最小路径长度以及10组数据值与精确解之间的平均偏差百分比，如表2所示。

表2 TSPLIB数据库对比实验

4.2 仿真实验

为验证BAPM算法的正确性，本文建立了一个仿真系统。该系统可随机构建不同的图。这些图都可以看作景区地图的抽象图结构，图中的顶点对应景区的景点，边则表示景点之间的路径。假设必经节点数量为 9，寻找图中从某一起始点出发经过这些点的最短路径，就对应为从景区的当前位置出发，规划一条包含9个游览景点的最短路径问题。第一种情况，随机构建一个包括100个随机生成的节点的图，任意两节点之间均有路径。在产生的路径中随机删除4 000条路径，将其转换为一个稀疏图，从而模拟景区路线网络的布局，然后在图中选择10个必经点（包含起点），如图4所示。第二种情况，随机产生 10个点及其之间的路径，构成一个有向非完全图，随机选择一个起始点，寻找经过这10个点的最短路径，如图5所示。

图4 第一种情况

图 4（a）展示了通过 Floyd-Warshall算法变换后的路线图，由选定的这 10个点构成的图，图4（b）是运用BAPM算法经过这10个点寻找的最短路径。

图 5（a）为由 Floyd-Warshall算法进行重组的有向图，图5（b）表示由BAPM算法产生的最短路径。

图5 第二种情况

以上2种情况下本文方法得到的结果与分支定界法找到的路径相同。

4.3 橘洲景区游览路线规划

橘洲景区是长沙的著名旅游景区，本文算法被应用于橘洲景区智能导览系统中。该系统中的橘洲地图是借助GPS设备、GOOGLE卫星地图等，通过实地打点，遍历景区道路并测量记录后自行建立的电子地图，橘洲景区景点的位置信息如表3所示。

以表3中标注*的6个景点为实验1必经景点，采用BAPM算法规划出的最佳路径为：枕江观光车售票处—沁园春诗词碑—毛泽东青年艺术雕像—望江亭—指点江山石碑—问天台，全程645 m，为最短游览路径。

以表3中标注#的10个景点为实验2必经景点，采用BAPM算法规划出的最佳路径为：地铁站西站口—原长沙海关旧址—婚庆园—橘子洲古董钢琴博物馆—沁园春·长沙橘洲 1925 —橘子洲人行入口—美孚洋行旧址—财神古殿—游客服务中心西站点—橘子洲西大门，全程1 218 m，为最短游览路径。

表3 橘子洲景区景点信息

实验1与实验2均找到了包含必经景点的最短游览路径。

4.4 实验总结

本文使用了3组实验，验证了提出的BAPM算法的有效性及优越性。在第一组实验中，选用了TSPLIB数据库中的TSP数据，将本文提出的BAPM算法与MMAS算法及GA算法进行了比较，结果显示BAPM算法可以在数据量较大的条件下，找出更接近最小路径的结果。在第二组实验中，随机生成点和路径，模拟景区地图和景点，该组实验的必经点数设置较小（10个必经点），验证了在点数较少的情况下，BAPM算法可以有效地找到准确的最短路径。第三组实验对实际的景区景点进行规划，所有景点位置和景点间路径长度均为实测数据，验证了算法在景点路径规划中的有效性。

通过实验验证了BAPM算法的有效性。实验结果表明，BAPM算法可以处理非完全图问题和完全图问题，并且在必经点个数较小的情况下，可以准确并且快速地寻找到最短路径。

5 结束语

本文针对旅游景区场景下，旅游者对多景点游览路径的规划需求，提出了一种基于回溯蚁群-粒子群混合算法的旅游景点路径规划模型，用于解决从起始点出发，经过若干必经点的景区景点路线规划的问题。通过实验，证明了BAPM算法可解决上述多点景点路径规划问题。由于BAPM算法实际上是一种多点路径规划算法，在复杂网络分析与设计、机器人路径规划[11]、路由复杂网络[12]等方面同样具有一定的实用价值。